Kanade's sum
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 871 Accepted Submission(s): 357
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
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]
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
【题意】给你一个序列，（1~n的一个全排列），然后询问所有的子区间第k大的数，累加起来，如果区间长度不足k，则为0，求累加 和。
【分析】由于区间数量太多，我们考虑算每个数的贡献。一个数的贡献显然就是它所能存在的区间数量，在这些区间内它是第k大。首先，要保证它是这个区间里的第k大，那么我们必须在他左边和右边找到共k-1个比他大的，然后围成区间就行。我们可以再这个数左边找到最多k个比他大的，右边找到最多k个比他大的（如果存在k个的话）。比如x是当前枚举的数，k=3，a,b,c是左边比他大的数的位置，d,e,f是右边比他大的数的位置（都是位置离x最近的），现在就是这样a b c x d e f，那么现在x的贡献就是能够围成的所有合法区间的数量，比如我们可以左边取x,右边取d e,那么此时的贡献就是(x-c)*(f-e),也可以左边取c,x,右边取d，此时的贡献就是(c-b)*(e-d)...
这样我们把贡献累加起来就是了，但是现在的问题是如何找这k个数。
我们发现当我们枚举到x时，找k个数是直接跨过了比x小的数，直接跳到了比x大的，所以我们可以从小到大枚举x，用一个链表把所有比x大的数连起来，当我们处理完x的时候，我们就把x的位置从链表里删除，这样我们的链表里存的都是比x大的数，而且相对位置也没变。这样我们就是O(k)找到这k个数.总时间复杂度，O(n*k)。
#include <bits/stdc++.h> #define inf 0x3f3f3f3f #define met(a,b) memset(a,b,sizeof a) #define pb push_back #define mp make_pair #define inf 0x3f3f3f3f #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 using namespace std; typedef long long ll; const int N = 5e5+50;; const int M = 160009; const int mod = 1e9+7; const double pi= acos(-1.0); typedef pair<int,int>pii; int n,k; int pos[N],pre[N],suf[N]; int l[N],r[N]; void del(int x){ int pree=pre[x]; int suff=suf[x]; if(pree)suf[pree]=suff; if(suff<=n)pre[suff]=pree; pre[x]=suf[x]=0; } int main() { int T; scanf("%d",&T); while(T--){ ll ans=0; scanf("%d%d",&n,&k); for(int i=1,x;i<=n;i++){ scanf("%d",&x); pos[x]=i; } for(int i=1;i<=n;i++){ pre[i]=i-1; suf[i]=i+1; } for(int x=1;x<=n-k+1;x++){ l[0]=r[0]=0; int p=pos[x]; for(int i=p;i&&l[0]<=k+1;i=pre[i])l[++l[0]]=i; for(int i=p;i<n+1&&r[0]<=k+1;i=suf[i])r[++r[0]]=i; l[++l[0]]=0; r[++r[0]]=n+1; for(int i=1;i<l[0];i++){ if(i+r[0]>=k+2&&i<=k){ ans+=1LL*(l[i]-l[i+1])*1LL*(r[k-i+2]-r[k-i+1])*x; } } del(p); } printf("%lld\n",ans); } return 0; }