HDU 6058 Kanade's sum(多校3)

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

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

题目大意

求n个数1~n中 所有区间第k大的值的和。

解题思路

难道只有我一个人把第k大曲解了吗[捂脸哭泣]纠结了好久，1234中第3大的数是2[忍不住哭泣]…… 现在要求出所有区间第k大的值的和，我们可以转化为对任意一个数求其满足几个区间的第k大，假设为ai，则最后结果即为 ∑ni=1ai∗i ，即求1~n每个数的贡献值。 当一个数x左侧有j个值大于它，若需满足第k大，则右侧需要有k-j-1个值大于它，根据这一性质，我们可以对任意一个 x 标记左侧k个比它大的数的位置，同样右侧标记k个。

如图所示，三角号表示当前遍历到的点，即编号为8的点，空心圆圈表示该点值比8号点值大，在k=3的情况下计算8号点的贡献值有3种情况： 1、8号点右侧有2个大于它的值，则满足条件的最小区间为[8,12]，这是必须要包含的一段区间，但我们可以这段区间扩展，因为实心点小于8号点所以对8的第k大值地位无影响，所以区间可扩展为[6,12]，则对于这种情况下，左边界可以取值有A1=(6,7,8)，右边界可以取值有A2=(12)，则满足条件的区间个数即为 |A1|∗|A2|=3∗1=(fron[1]−fron[2])∗∗(bac[4]−bac[3]) ； 2、8号点左侧有1个值大于它，右侧有一个值大于它，同理满足条件的最小区间为[5,10]，区间可扩展为[4,11]，所以A1=(4,5)，A2=(10,11)，满足条件的区间个数为 |A1|∗|A2|=2∗2=(fron[2]−fron[3])∗∗(bac[3]−bac[2]) ； 3、8号点左侧有2个大于它的值，则满足这个条件的最小的区间是[3,8]，扩展可为[1,9]，此时A1=(1,2,3)，A2=(8,9)，则满足条件的区间个数为 |A1|∗|A2|=3∗2=(fron[3]−fron[4])∗∗(bac[2]−bac[1]) ； 如此模拟便可。 为了简便运算过程，x位置由1~n依次增大，用链表维护，每计算完依次x就将x节点删除，这样就可以保证左右两侧的数全都是大于x的数，那样在统计k的位置范围时只需要往左或往右k个位置即可。

代码实现

#include <iostream> #include<cstdio> #include<cstring> using namespace std; #define maxn 500007 #define ll long long int a[maxn],pos[maxn],pre[maxn],ne[maxn]; ll fron[85],bac[85]; int main() { int T,n,k; scanf("%d",&T); while(T--) { scanf("%d %d",&n,&k); for(int i=1; i<=n; i++) { scanf("%d",&a[i]); pos[a[i]]=i; pre[i]=i-1; ne[i]=i+1; } pre[0]=-1,ne[n+1]=n+2; ll temp,ans=0; for(int i=1; i<=n; i++) { int x=0,y=0; int now=pos[i]; for(int j=now; j>=0&&x<=k; j=pre[j]) fron[++x]=j; for(int j=now; j<=n+1&&y<=k; j=ne[j]) bac[++y]=j; for(int j=1; j<=x-1; j++) { if(k-j+2>y) continue; temp=(fron[j]-fron[j+1])*(bac[k-j+2]-bac[k-j+1]); ans+=temp*i; } ne[pre[now]]=ne[now],pre[ne[now]]=pre[now]; //链表删除节点x } printf("%lld\n",ans); } return 0; }