Kanade's sum

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2491    Accepted Submission(s): 1034 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  

题意：

     给定一个大小为n的数组A ，数组里的元素为1~n，且元素互不相同，现定义一个函数f(l,r,k)，其含义为从A[l]~A[r]中第k大的数。现求l取值为1~n时，r取值为l~n时，所有f(l,r,k)的和。

思路：

     即求A的所有子区间内，第k大数的和。可以转化成为，求所有能使数num成为第k大数的子区间，再用区间个数乘以num的值，最后将所有的num结果相加可得结果。我们可以用链表的思想解决这个问题。

     找在这个数组中，能使num成为第k大数的最大子区间。以num为界，找在num的位置之前k个比num大的数，并记录下各个数字的位置，num之后也同样，我们可以很容易看出来位置的差值就是区间的个数。然后逐个删去可以成为第k大数的num，记录下它的前驱与后继，就可以得出结果。其中注意删去的是num这个值，但各个数字之间的相对位置不变。下面举个例子帮助理解元素位置对求区间的作用(对照程序及注释理解)。

     1

     13 3

     10 12 6 8 (3) (2) 5 7 (4) 9 (1) 13 11

     我们找使5成为区间第3大数的区间个数，此时1，2，3，4都已经删除。

     我们可以想到，符合条件的区间为：

     (5左边比5大的数的个数)  5  (5右边比5大的数的个数)

     (0)  5  (2)

     (1)  5  (1)

     (2)  5  (0)

     我们找到5之前比5大的3个数为12 6 8，s[1]=7，s[2]=4，s[3]=3，s[4]=2;

     5之后比5大的3个数为7，9，13，t[1]=7，t[2]=8，t[3]=10，t[4]=12. (s[1]与t[1]存的是5的位置)

     我们以 (0)  5  (2) 为例

     s[1]-s[2]=7-4=3

     代表在5之前取0个比5大的数可以有3种情况，分别是

     5

     (2) 5

     (3) (2) 5

     t[4]-t[3]=12-10=2

     代表在5之后取2个比5大的数可以有2种情况，分别是

     5 7 (4) 9

     5 7 (4) 9 (1)

     则此时共有6种情况可以使5成为区间第3大数。其他情况亦如此。

下面贴上代码：(细节处理及具体实现详见代码注释)

#include<cstdio> using namespace std; const int maxn=500009; int a[maxn],pos[maxn],prep[maxn],nextp[maxn]; int s[maxn],t[maxn]; int main() { int T,n,k; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&k); for(int i=1; i<=n; i++) { scanf("%d",&a[i]); pos[a[i]]=i;//记录位置 prep[i]=i-1;//链表前驱 nextp[i]=i+1;//链表后继 } long long ans=0; for(int num=1; num<=n-k+1; num++) //枚举可能成为第k大的数(比如一个数列中最大的数不可能在任何子数列里成为第二大) { int p=pos[num]; int ss=1,tt=1; //寻找前后k个比它大的数 //若找第k大数,只需向前(后)找k-1个数就可以,但是我们要记录第k个数比num大的数的位置 //这样才能找到最大的数组区间(因为第k个比num大的数和第k-1个比num大的数之间可能会有比num小的数存在) //再加上ss[1](tt[1])存的是num本身的位置,所以for循环k+1次 for(int i=p; i && ss<=k+1; i=prep[i]) //i初始为num的位置,后面会有删除操作所以不能直接写i-- s[ss++]=i; //s[1]存的是num的位置,s[2]存的是num左边第一个大于num的数的位置,以此类推 for(int j=p; j<=n && tt<=k+1; j=nextp[j]) t[tt++]=j; //t[1]存的是num的位置,t[2]存的是num右边第一个大于num的数的位置,以此类推 //(首尾额外添加两个无限大的数) s[ss]=0; //s尾加0,t尾加n+1 t[tt]=n+1; //相当于在一个数组中取出能使num成为第k大数的一个最大范围的子数组 for(int i=1; i<=ss-1; i++) //i=1代表从num前面取i-1=0个比num大的数 { int tmp=k-(i-1); //tmp代表从num后面取tmp个比num大的数 if(tmp<=tt-1 && tmp>0) ans=ans+(s[i]-s[i+1])*1LL*(t[tmp+1]-t[tmp])*num; //由于区间是连续的,则位置的差值恰好为连续区间的种类数 //num前*num后为大数组中所有能使num成为第k大数的子区间,再乘以num则符合题意 //从链表中将此数删除(p是num的位置) if(prep[p]>0) nextp[prep[p]]=nextp[p]; //p前驱的后继是p的后继 if(nextp[p]<=n) prep[nextp[p]]=prep[p]; //p后继的前驱是p的前驱 prep[p]=nextp[p]=0; //p的前驱和后继赋为0 //删除改变的是num前驱的后继和num后继的前驱,相当于我们只删除了这个数,但这个数的位置依然存在 //如 3 1 2,删除了1,3的位置仍然是1,2的位置仍然是3 } } printf("%I64d\n",ans); } return 0; }