【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)$。

 #include<bits/stdc++.h>

 #define M 500005

 #define L long long

 using namespace std;

 int l[M]={},r[M]={},a[M]={},p[M]={};

 int n,k; L ans=;

 bool cmp(int x,int y){return a[x]<a[y];}

 int main(){

     int cas=; cin>>cas;

     while(cas--){

         ans=;

         scanf("%d%d",&n,&k);

         for(int i=;i<=n;i++) scanf("%d",a+i),p[i]=i;

         for(int i=;i<=n;i++) r[i]=i+,l[i]=i-;

         sort(p+,p+n+,cmp);

         for(int i=;i<=n;i++){

             int id=p[i];

             int lid,lcnt=;

             for(lid=id;l[lid]!=&&lcnt!=k;lid=l[lid],lcnt++);

             int rid=id,rcnt=;

             while(lcnt+rcnt<k&&r[rid]!=n+){

                 rid=r[rid];

                 rcnt++;

             }

             if(lcnt+rcnt==k){

                 while(rid!=n+){

                     L ll=lid-l[lid],rr=r[rid]-rid;

                     ans+=ll*rr*a[id];

                     if(lid==id) break;

                     lid=r[lid]; rid=r[rid];

                 }

             }

             lid=l[id]; rid=r[id];

             r[lid]=rid; l[rid]=lid;

         }

         cout<<ans<<endl;

     }

 }

巴特西

【hdu6058】 Kanade's sum 模拟

最新文章

热门文章