题意:给出长为n的序列a,给出整数k,求对于序列a,每个区间第k大的数之和
题解:相当于求每个数字分别是多少个区间的第k大。记录每个数出现的位置,维护一个set(相当于链表),从大到小遍历,将每个数的位置插入set;对于每个数,只需在其两边找k个比它大的数,对起始位置进行遍历,计算每个数对答案的贡献,求和。
#include<iostream> #include<stdio.h> #include<string.h> #include<vector> #include<algorithm> #include<math.h> #include<queue> #define INF 1e9 #define ll long long #define maxn 300005 #include<set> #include<stack> using namespace std; int a[500005]; int pos[500005]; int ri[500005]; int le[500005]; int main() { int t; scanf("%d",&t); while(t--) { int n,k; memset(a,0,sizeof(a)); memset(pos,0,sizeof(pos)); scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); pos[a[i]]=i; le[i]=0; ri[i]=n+1; } set<int>s; set<int>::iterator it; s.insert(0); s.insert(n+1); ll ans=0; le[n+1]=0; ri[n+1]=n+1; ri[0]=n+1; le[0]=0; for(int x=n;x>=1;x--) { s.insert(pos[x]); it=s.find(pos[x]); it++; int p=*it; int pp=le[p]; le[pos[x]]=pp; ri[pos[x]]=p; le[p]=pos[x]; ri[pp]=pos[x]; int l=pos[x]; for(int j=0;j<k&&l!=0;j++) l=le[l]; int r=l; for(int j=0;j<k&&r!=n+1;j++) r=ri[r]; int nowl=l; int nowr=r; for(int j=0;j<k;j++) { if(nowl==pos[x]||nowr==n+1) break; int nextl=ri[nowl]; int nextr=ri[nowr]; ans+=(1ll*(nextl-nowl)*(nextr-nowr)*x); // cout<<ans<<endl; nowl=nextl; nowr=nextr; } } printf("%lld\n",ans); } return 0; }