2017多校训练赛第三场 HDU 6058 （组合计数+思维）

Kanade's sum

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 417    Accepted Submission(s): 139

Problem Description

Give you an array A[1..n]of length n.

Let f(l,r,k) be the k-th largest element of A[l..r].

Specially , f(l,r,k)=0 if r−l+1<k.

Give you k , you need to calculate ∑nl=1∑nr=lf(l,r,k)

There are T test cases.

1≤T≤10

k≤min(n,80)

A[1..n] is a permutation of [1..n]

∑n≤5∗105

Input

There is only one integer T on first line.

For each test case,there are only two integers n,k on first line,and the second line consists of n integers which means the array A[1..n]

Output

For each test case,output an integer, which means the answer.

Sample Input

1

5 2

1 2 3 4 5

Sample Output

30

Source

​​2017 Multi-University Training Contest - Team 3 ​​

        多校就是这么喜欢出计数的题目……

        这题还是比较好想到的，当场就A了。要你求所有区间的第k大之和。最开始还以为是一道数据结构的题目，什么主席树平衡树树套树什么的，然后发现好像根本没必要，或者说起始那么做更不好做。

        还是比较惯用的伎俩，我们肯定不能枚举出每一个区间，所以我们计算每一个数字作为区间第k大的贡献。对于每一个数字，我们只需要计算以他为区间第k大的区间的个数，然后用个数乘以这个数字再求和就是我们最后的结果。那么问题来了，如何求区间个数呢？我们考虑该数字是区间第k大，所以在这个区间就有k-1个数字比该数字大。那么我们就可以枚举在该数字左边有i个数字比它大，那么在右边就有k-1-i个数字比他小，我们对应的分别求出满足条件的区间左端点数和区间右端点数，再相乘就是此时的贡献。

        这里为了求左右端点的方案数，我们设置pos1和pos2数组。其中pos1[i]表示在该数字左边第一个有i个比该数字大的区间的左端点，对应的pos2[i]表示在该数字右边第一个有i个数字比该数字大的区间的右端点。如此一来，我们当我枚举到左边有i个比该数字大的数字的时候，左端点可选则的个数就是pos1[i]-pos1[i+1]；那么，右边有k-1-i个比该数字大的时候，右端点可选择的个数就是pos2[i+1]-pos2[i]。

#include<bits/stdc++.h>
#define LL long long
#define N 501000
using namespace std;

int a[N],nxt[N],pre[N],st[N],n,k;
int pos1[100],pos2[100];
LL ans;

int main()
{
    int T_T;
    cin>>T_T;
    while(T_T--)
    {
        ans=0;
        scanf("%d%d",&n,&k);
        memset(pre,0,sizeof(pre));
        memset(nxt,0,sizeof(nxt));
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        int tot=0; st[0]=0;
        for(int i=1;i<=n;i++)
        {
            while (a[i]>a[st[tot]]&&tot) tot--;                //单调栈预处理pre
            pre[i]=st[tot]; st[++tot]=i;
        }
        tot=0; st[0]=0;
        for(int i=n;i>0;i--)
        {
            while(a[i]>a[st[tot]]&&tot) tot--;                //单调栈预处理nxt
            nxt[i]=st[tot]; st[++tot]=i;
        }
        for(int i=1;i<=n;i++)
            if (!nxt[i]) nxt[i]=n+1;
        nxt[n+1]=n+1;
        for(int i=1;i<=n;i++)
        {
            memset(pos1,0,sizeof(pos1));
            memset(pos2,0,sizeof(pos2));
            pos1[0]=pos2[0]=i;
            for(int j=1;j<=k;j++)                    //计算两个pos数组
            {
                int p=pos1[j-1]+1;                    //当期指针p指向上一个位置的后一位
                while(a[p]<a[i]&&p<=n) p=nxt[p];            //如果该位置的数字小于a[i]，那么往后到它的nxt
                pos1[j]=min(p,n+1); p=pos2[j-1]-1;
                while(a[p]<a[i]&&p) p=pre[p];                //与上面同理，往前移到它的pre
                pos2[j]=max(0,p);
            }
            for(int j=0;j<k;j++)
            {
                LL x=pos1[j+1]-pos1[j];                    //这里的pos与上面描述的pos相反(1是往后、2是往前)
                LL y=pos2[k-j-1]-pos2[k-j];                //x、y分别代表左右端点的取值数量
                ans+=x*y*(LL)a[i];
            }
        }
        printf("%I64d\n",ans);
    }
    return 0;
}