首页 > 代码库 > hdu 6058

hdu 6058

2024-11-14 22:31:02   203人阅读

题意：求任意区间第k大之和

思路：该题因为每个数不重复，如果以X为第k大，我们是不是知道比他大的那些数字的位置，然后从其左边取x个，右边取y个，使得x+y=k-1，即可

　　　 所以我们从大到小，把其位置从小到大连接起来，第x个数字，我就从该位置前面去选，后面去选，最多移动k次

　　

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=500005;
 5 
 6 int n,k,pos[N],l[N],r[N],L[N],R[N];
 7 set<int > a;
 8 set<int >:: iterator it,itt;
 9 
10 void hh(int x,int y){//位置的连接
11     int z=L[x];//没插入前，x的前面一个数
12     L[y]=z;//变成y前面的了
13     R[y]=x;//x前面变成y了
14     L[x]=y;
15     R[z]=y;//z后面变成y了，原来是x的
16 }
17 int main(){
18     int t;
19     scanf("%d",&t);
20     while(t--){
21         a.clear();
22         scanf("%d%d",&n,&k);
23         int x;
24         for(int i=1;i<=n;i++) {
25             scanf("%d",&x);
26             pos[x]=i;
27         }
28         a.insert(0);a.insert(n+1);
29         L[0]=-1;R[0]=n+1;
30         L[n+1]=0;R[n+1]=-1;
31         for(int i=n;i>n-k+1;i--){
32             it=a.lower_bound(pos[i]);
33 
34             hh(*it,pos[i]);
35             a.insert(pos[i]);
36         }
37         ll sum=0;
38         for(int i=n-k+1;i>=1;i--){
39             it=(a.lower_bound(pos[i]));
40             int po=*it;
41           //  cout<<po<<endl;
42             for(int j=0;j<=k;j++) l[j] = -1;
43             l[0]=pos[i];
44             for(int j=1,h=L[po];j<=k&&h!=-1;j++,h=L[h]) {
45                 l[j]=h;
46             }
47             r[0]=pos[i];
48             for(int j=1,h=po;j<=k&&h!=-1;j++,h=R[h]) {
49                 r[j]=h;
50                 if(l[k-j+1]!=-1)
51                     sum+=1LL*i*(l[k-j]-l[k-j+1])*(r[j]-r[j-1]);
52             }
53             hh(*it,pos[i]);
54             a.insert(pos[i]);
55         }
56         cout<<sum<<endl;
57     }
58 }

 

hdu 6058


联系
我们