【hdu6058】 Kanade's sum 模拟

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6058

题目大意：给你一个$1$到$n$的排列，请求出该序列所有区间中第$k$大之和，若该区间内少于$k$个数，则不计算答案。

数据范围： $n≤5*10^5,k≤50$。

想出来了好像真的是模拟题（然而我并没完全独立思考）。

和上午做的某一题挺像的。

我们考虑数字$x$，不难发现，我们只要分别找出该数字左边和右边大于它的$k-1$个数字分别是什么，然后简单地扫一遍就可以得出$x$作为第$k$大的数字出现的次数。

下面考虑如何求出数字$x$两侧比它大的数字。

我们将输入的数字从小到大处理，对于数字$x$，我们维护一个双向链表，按照原序列的殊勋保存所有$＞x$的数字，每次处理完$x$后，将$x$从该链表中删除。

不难发现，初始时链表中只有$n$个元素，且删除一个元素耗时为$O(1)$，且每次扫描为$O(k)$，故总时间复杂度为$O(n*k+n log n)$。

 1 #include<bits/stdc++.h>
 2 #define M 500005
 3 #define L long long
 4 using namespace std;
 5 
 6 int l[M]={0},r[M]={0},a[M]={0},p[M]={0};
 7 int n,k; L ans=0;
 8 bool cmp(int x,int y){return a[x]<a[y];}
 9 int main(){
10     int cas=0; cin>>cas;
11     while(cas--){
12         ans=0;
13         scanf("%d%d",&n,&k);
14         for(int i=1;i<=n;i++) scanf("%d",a+i),p[i]=i;
15         for(int i=1;i<=n;i++) r[i]=i+1,l[i]=i-1;
16         sort(p+1,p+n+1,cmp);
17         for(int i=1;i<=n;i++){
18             int id=p[i];
19             int lid,lcnt=1;
20             for(lid=id;l[lid]!=0&&lcnt!=k;lid=l[lid],lcnt++);
21             int rid=id,rcnt=0;
22             while(lcnt+rcnt<k&&r[rid]!=n+1){
23                 rid=r[rid];
24                 rcnt++;
25             }
26             if(lcnt+rcnt==k){
27                 while(rid!=n+1){
28                     L ll=lid-l[lid],rr=r[rid]-rid;
29                     ans+=ll*rr*a[id];
30                     if(lid==id) break;
31                     lid=r[lid]; rid=r[rid];
32                 }
33             }
34             lid=l[id]; rid=r[id];
35             r[lid]=rid; l[rid]=lid;
36         }
37         cout<<ans<<endl;
38     }
39 }