HDU 6058 Kanade's sum(思维)

xiaoxiao2021-02-28  15

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; }

转载请注明原文地址: https://www.6miu.com/read-250435.html

最新回复(0)