HDU 6058 Kanade's sum（思维）

Kanade's sum

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

Source

2017 Multi-University Training Contest - Team 3

题意：给出长为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; }