2213. K个串

★★★★ 输入文件：bzoj_4504.in 输出文件：bzoj_4504.out 简单对比
时间限制：20 s 内存限制：512 MB

【题目描述】

兔子们在玩k个串的游戏。首先，它们拿出了一个长度为n的数字序列，选出其中的一

个连续子串，然后统计其子串中所有数字之和（注意这里重复出现的数字只被统计一次）。

兔子们想知道，在这个数字序列所有连续的子串中，按照以上方式统计其所有数字之和，第

k大的和是多少。

【输入格式】

第一行，两个整数n和k，分别表示长度为n的数字序列和想要统计的第k大的和

接下里一行n个数a_i，表示这个数字序列

【输出格式】

一行一个整数，表示第k大的和

【样例输入】

7 5

3 -2 1 2 2 1 3 -2

【样例输出】

【提示】

1 <= n <= 100000, 1 <= k <= 200000, 0 <= |a_i| <= 10^9数据保证存在第 k 大的和

　　和HDU 5654 xiaoxin and his watermelon candy几乎一模一样。

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <algorithm>

 #include <queue>

 using namespace std;

 const int maxn=;

 const int INF=;

 int hash[maxn],a[maxn],n,k;

 int head[maxn],nxt[maxn],pre[maxn];

 int rt[maxn],pos[maxn<<];

 int ch[maxn<<][],cnt;

 long long lx[maxn<<],tr[maxn<<];

 void Push_up(int x){

     int l=ch[x][],r=ch[x][];

     tr[x]=tr[l]+tr[r];

     if(lx[l]>tr[l]+lx[r]){

         lx[x]=lx[l];

         pos[x]=pos[l];

     }

     else{

         lx[x]=tr[l]+lx[r];

         pos[x]=pos[r];

     }

 }

 void Build(int &rt,int l,int r){

     rt=++cnt;

     if(l==r){

         pos[rt]=l;

         if(!pre[l]){

             tr[rt]=hash[a[l]];

             lx[rt]=hash[a[l]];

         }

         return;

     }

     int mid=(l+r)>>;

     Build(ch[rt][],l,mid);

     Build(ch[rt][],mid+,r);

     Push_up(rt);

 }

 void Update(int pr,int &rt,int l,int r,int g,int d){

     rt=++cnt;

     tr[rt]=tr[pr]+d;

     if(l==r){

         pos[rt]=g;

         lx[rt]=tr[rt];

         return;

     }

     ch[rt][]=ch[pr][];

     ch[rt][]=ch[pr][];

     int mid=(l+r)>>;

     if(g<=mid)Update(ch[pr][],ch[rt][],l,mid,g,d);

     else Update(ch[pr][],ch[rt][],mid+,r,g,d);

     Push_up(rt);

 }

 struct data{int x;long long y;};

 data Query(int t,int l,int r,int x,int y)

 {

     if(l==x && r==y) return (data){pos[t],lx[t]};

     int mid=(l+r)>>;

     if(y<=mid) return Query(ch[t][],l,mid,x,y);

     else if(x>mid){

         data tmp=Query(ch[t][],mid+,r,x,y);

         return (data){tmp.x,tmp.y+tr[ch[t][]]};

     }

     else{

         data tmp1=Query(ch[t][],l,mid,x,mid);

         data tmp2=Query(ch[t][],mid+,r,mid+,y);

         if(tmp1.y>tmp2.y+tr[ch[t][]]) return tmp1;

         else return (data){tmp2.x,tmp2.y+tr[ch[t][]]};

     }

 }

 struct node{int i,l,r,x; long long y;};

 bool operator<(const node& a1,const node& a2)

 {return a1.y<a2.y;}

 priority_queue<node> q;

 int main(){

     freopen("bzoj_4504.in","r",stdin);

     freopen("bzoj_4504.out","w",stdout);

     scanf("%d%d",&n,&k);

     for(int i=;i<=n;i++)

         scanf("%d",&a[i]);

     for(int i=;i<=n;i++)

         hash[i]=a[i];

     sort(hash+,hash+n+);

     for(int i=;i<=n;i++)

         a[i]=lower_bound(hash+,hash+n+,a[i])-hash;

     for(int i=;i<=n;i++){

         pre[i]=head[a[i]];

         nxt[head[a[i]]]=i;

         head[a[i]]=i;

     }

     Build(rt[],,n);

     for(int i=;i<n;i++){

         Update(rt[i],rt[i+],,n,i+,-hash[a[i]]);

         if(nxt[i])Update(rt[i+],rt[i+],,n,nxt[i],hash[a[i]]);

     }

     for(int i=;i<=n;i++){

         data tmp=Query(rt[i],,n,i,n);

         q.push((node){i,i,n,tmp.x,tmp.y});

     }

     long long ans;

     for(int i=;i<=k;i++){

         node t=q.top(); q.pop(); ans=t.y;

         if(t.l!=t.x){

             data tmp=Query(rt[t.i],,n,t.l,t.x-);

             q.push((node){t.i,t.l,t.x-,tmp.x,tmp.y});

         }

         if(t.r!=t.x){

             data tmp=Query(rt[t.i],,n,t.x+,t.r);

             q.push((node){t.i,t.x+,t.r,tmp.x,tmp.y});

         }

     }

     printf("%lld\n",ans);

     return ;

 }

　　有时间一定要重打！！！

K个