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;
}