记录编号	299046	评测结果	AAAAAAAAAAAAAAAAAAT
题目名称	[HZOI 2015] Seq	最终得分	94
用户昵称	TenderRun	是否通过	未通过
代码语言	C++	运行时间	2.387 s
提交时间	2016-08-23 17:31:30	内存使用	110.94 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=500010;
int n,K,s[maxn],pos;
struct Node{
    int node,l,r;
    Node(int NODE=0,int L=0,int R=0){
        node=NODE;l=L;r=R;
    }
};
int mm[maxn],Max[maxn][25],Mpos[maxn][25];

int Query(int l,int r){
    if(Max[l][mm[r-l+1]]<Max[r-(1<<mm[r-l+1])+1][mm[r-l+1]]){
        pos=Mpos[r-(1<<mm[r-l+1])+1][mm[r-l+1]];
        return Max[r-(1<<mm[r-l+1])+1][mm[r-l+1]];
    }
    else{
        pos=Mpos[l][mm[r-l+1]];
        return Max[l][mm[r-l+1]];
    }
}

int Q(Node x){
    return Query(x.l,x.r)-s[x.node-1];
}

struct Heap{
    int cnt;
    Node h[maxn<<1];
    void Insert(Node x){
        int p=++cnt;
        while(p!=1){
            if(Q(x)<=Q(h[p>>1]))break;
            h[p]=h[p>>1];
            p>>=1;
        }
        h[p]=x;
    } 
    
    void Delete(){
        int p=1,a,b;
        Node x=h[cnt--];
        while(p*2<=cnt){
            a=p<<1;b=a|1;
            if(b<=cnt&&Q(h[a])<Q(h[b]))a=b;
            if(Q(h[a])<=Q(x))break;
            h[p]=h[a];
            p=a;    
        }
        h[p]=x;
    }
}q;

int main(){
    freopen("final_set.in","r",stdin);
    freopen("final_set.out","w",stdout);
    scanf("%d%d",&n,&K);
    
    for(int i=1;i<=n;i++)
        scanf("%d",&s[i]);    
    for(int i=1;i<=n;i++)
        s[i]+=s[i-1];
    
    mm[0]=-1;
    for(int i=1;i<=n;i++){
        mm[i]=(i&(i-1))==0?mm[i-1]+1:mm[i-1];
        Max[i][0]=s[i];
        Mpos[i][0]=i;
    }
    
    for(int k=1;k<=mm[n];k++)
        for(int i=1;i+(1<<k)-1<=n;i++){
            if(Max[i][k-1]>Max[i+(1<<(k-1))][k-1]){
                Max[i][k]=Max[i][k-1];
                Mpos[i][k]=Mpos[i][k-1];
            }
            else{
                Max[i][k]=Max[i+(1<<(k-1))][k-1];
                Mpos[i][k]=Mpos[i+(1<<(k-1))][k-1];
            }
        }
    
    for(int i=1;i<=n;i++)
        q.Insert(Node(i,i,n));
    
    long long ans=0;
    int p;
    Node x;
    while(K--){
        ans=Q(q.h[1]);
        x=q.h[1];p=pos;
        q.Delete();
        
        if(x.l<p)q.Insert(Node(x.node,x.l,p-1));
        if(x.r>p)q.Insert(Node(x.node,p+1,x.r));
    }
    printf("%lld\n",ans);
    return 0;
}