题意：给出一个从1~n的数列，任意排列，求任意区间的第K大的数之和
思路：把求任意区间第K大转化为对某一个数x而言，作为第K大时对区间数量的贡献；通过预处理先记录下每个数的位置，设置两个数组left[],和right[],分别记录x左边和右边比x大的数的位置，这样对枚举的每一个x而言，只需要扫一遍左k和右k个数即可，如果枚举的时候从大到小，可以发现前面添加的数都是比当前x大的；可以发现对于x而言左边舍弃一个比它大的值，右边添加一个比它的值，区间依旧满足x第k大；
附上借鉴一位大牛写的代码：
#include<iostream> #include<cstdio> #include<set> using namespace std; const int maxn=500005; typedef long long ll; int n,k; int le[maxn],ri[maxn],vis[maxn]; const int read() { int f=1,x=0; char ch=getchar(); while(ch<'0' || ch>'9'){if(ch=='-')f*=-1;ch=getchar();} while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} return f*x; } ll sol() { set<int>s; set<int>::iterator it; s.insert(0); s.insert(n+1); ll ans=0; for(int i=n;i>0;i--) { int l,r; s.insert(vis[i]); it=s.find(vis[i]); it++; r=*it; l=le[r]; le[r]=vis[i]; ri[vis[i]]=r; ri[l]=vis[i]; le[vis[i]]=l; int nowl=vis[i]; for(int j=0;j<k&&nowl;j++) nowl=le[nowl]; int nowr=nowl; for(int j=0;j<k&&nowr!=n+1;j++) nowr=ri[nowr]; for(int j=0;j<k;j++) { if(nowl==vis[i] || nowr==n+1) break; ans+=1ll*(ri[nowl]-nowl)*(ri[nowr]-nowr)*i; nowl=ri[nowl]; nowr=ri[nowr]; } } return ans; } int main() { freopen("input.txt","r",stdin); int cas; for(scanf("%d",&cas);cas;cas--) { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { int x=read(); vis[x]=i; le[i]=0; ri[i]=n+1; } if(k<1) { printf("0 "); continue; } le[n+1]=0;ri[n+1]=n+1; ll ans=sol(); cout<<ans<<endl; } return 0; }