Description
兔子们在玩k个串的游戏。首先，它们拿出了一个长度为n的数字序列，选出其中的一个连续子串，然后统计其子串中所有数字之和（注意这里重复出现的数字只被统计一次）。
兔子们想知道，在这个数字序列所有连续的子串中，按照以上方式统计其所有数字之和，第k大的和是多少。
Input
第一行，两个整数n和k，分别表示长度为n的数字序列和想要统计的第k大的和
接下里一行n个数a_i，表示这个数字序列
Output
一行一个整数，表示第k大的和
设 \(f(i,j)\) 表示以 \(i\) 为左端点，\(j\) 为右端点的子串和。
对于每一个左端点 \(i\)，我们可以先把 \(f(i,j)\) 里面最大的那个放入优先队列（从大到小排序）中，接下来进行 \(k-1\) 次这样的操作：
先取出队首并弹出，设其所对应的是 \(f(a,b)\)，那么我们可以找到 \(f(a,j)\) 中比 \(f(a,b)\) 小的最大的那个，并把它加入队列。也就是说，找到以 \(a\) 为左端点的 \(f(a,j)\) 次大值，扔进优先队列。
这样的 \(k-1\) 次操作结束后，队首就是我们要找的那个 \(k\) 大值了。
至于为什么，自己模拟一下或自己想一想。
现在的关键是如何维护最大值和次大值。
设 \(nxt_i\) 表示数 \(a_i\) 在 \(i\) 之后出现的第一个位置，显然可以 \(O(n)\) 预处理。
显然，\(f(1)\) 可以 \(O(n)\) 维护出来。
考虑如何从 \(f(1)\) 转移出 \(f(2)\)。
-
当 \(j=1\) 时，\(f(2,j)\) 不存在，设为 \(-\infty\)。
-
当 \(2\leq j < nxt_1\) 时，如下图：
设 \(nxt_1=5\)，不妨设 \(a_1=a_5=10\)，那么由 \(nxt\) 的定义可知，当 \(2\leq j < nxt_1\) 时，\(a_2\sim a_j\) 中不可能存在一个数是 \(10\)。那么从 \(f(1,j)\) 更新到 \(f(2,j)\) 时，要减去 \(10\) 对 \(f(2,j)\) 的贡献。比如当 \(j=4\) 时，\(a_1\sim a_4\) 中出现的数有：\(1\)、\(2\)、\(10\)，所以 \(f(1,4)=1+2+10=13\)（如图红框），而 \(a_2\sim a_4\) 中 \(a_1=10\) 被去掉了，而 \(a_2\sim a_4\) 中又没有重新出现过 \(10\)，所以 \(f(2,4)=f(1,4)-10=3\)（如图蓝框）。
-
当 \(j\geq nxt_1\) 时，如下图：
我们用同样的一个例子。观察发现：从 \(f(1,j)\) 转移到 \(f(2,j)\) 的时候只是去掉了 \(a_1=10\)，但是当 \(j\geq nxt_1\) 时，可以保证在 \(a_2\sim a_j\) 之间肯定会出现 \(10\)，所以 \(10\) 还是对 \(f(2,j)\) 有贡献，也就是说始终有 \(f(2,j)=f(1,j)\)。比如当 \(j=7\) 时，\(a_1\sim a_7\) 出现的数有 \(1\)、\(2\)、\(4\)、\(10\)，\(f(1,7)=1+2+4+10=17\)，而 \(a_2\sim a_7\) 中出现的数和 \(a_1\sim a_7\) 中出现的数没有变化，所以 \(f(2,7)=f(1,7)=17\)。
综上所述，可以推出：
当 \(j< i-1\)，\(f(i,j)=f(i-1,j)=-\infty\)；
当 \(j=i-1\) 时，\(f(i,j)=-\infty\)；
当 \(i \leq j < nxt_{i-1}\) 时，\(f(i,j)=f(i-1,j)-a_{i-1}\)；
当 \(j\geq nxt_{i-1}\) 时，\(f(i,j)=f(i-1,j)\)。
我们就可以发现，\(f(i-1,j)\) 和 \(f(i,j)\) 有一段区间是一样的（\(j<i-1\) 或 \(j\geq nxt_{i-1}\)），有一段区间是 \(f(i,j)\) 等于 \(f(i-1,j)\) 减去一个相同的值（\(i \leq j < nxt_{i-1}\)），有一个特殊的位置是 \(f(i,j)=-\infty\)（\(j=i-1\)）。
容易联想到用可持久化线段树维护 \(f(i,j)\)。（\(n\) 棵线段树，每棵线段树 \(i\) 存储 \(f(i,j)\) 及它们的最大值）。
代码及注释如下：
#include<bits/stdc++.h>
#define N 100010
#define lc t[u].ch[0]
#define rc t[u].ch[1]
#define ll long long
#define int long long
#define LNF 1e15
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
struct data
{
ll val;
int rt,id;
data(){};
data(ll vall,int rtt,int idd){val=vall,rt=rtt,id=idd;}
bool operator < (const data &a) const
{
return val<a.val;
}
};
struct Segment_Tree
{
int ch[2],where;
ll maxn,tag;
}t[N*100];
int n,nn,k,a[N],b[N],last[N],nxt[N];
int node,root[N];
ll f[N];
bool vis[N];
priority_queue<data>q;
void up(int u)
{
if(t[lc].maxn-t[lc].tag>t[rc].maxn-t[rc].tag)
{
t[u].maxn=t[lc].maxn-t[lc].tag;
t[u].where=t[lc].where;
}
else
{
t[u].maxn=t[rc].maxn-t[rc].tag;
t[u].where=t[rc].where;
}
}
void build(int &u,int l,int r)
{
u=++node;
if(l==r)
{
t[u].maxn=f[l];
t[u].where=l;
return;
}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
up(u);
}
void update(int &u,int last,int l,int r,int ql,int qr,ll x)
{
u=++node;
t[u]=t[last];
if(ql<=l&&r<=qr)
{
t[u].tag+=x;
return;
}
int mid=(l+r)>>1;
if(ql<=mid) update(lc,t[last].ch[0],l,mid,ql,qr,x);
if(qr>mid) update(rc,t[last].ch[1],mid+1,r,ql,qr,x);
up(u);
}
void change(int u,int l,int r,int x,ll y)
{
if(l==r)
{
t[u].maxn=y;
t[u].tag=0;
return;
}
int mid=(l+r)>>1;
if(x<=mid) change(lc,l,mid,x,y);
else change(rc,mid+1,r,x,y);
up(u);
}
signed main()
{
n=read(),k=read();
for(int i=1;i<=n;i++)
b[i]=a[i]=read();
sort(b+1,b+n+1);
nn=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++)
a[i]=lower_bound(b+1,b+nn+1,a[i])-b;
//以上是离散化
for(int i=1;i<=n;i++) nxt[i]=n+1;
for(int i=1;i<=n;i++)
{
if(last[a[i]]) nxt[last[a[i]]]=i;
last[a[i]]=i;
}
//以上是预处理nxt
for(int i=1;i<=n;i++)
{
if(!vis[a[i]])
{
vis[a[i]]=1;
f[i]=f[i-1]+b[a[i]];
}
else f[i]=f[i-1];
}
//预处理f[1][i]
build(root[1],1,n);//建出第一棵线段树
for(int i=2;i<=n;i++)
{
if(i<=nxt[i-1]-1) update(root[i],root[i-1],1,n,i,nxt[i-1]-1,b[a[i-1]]);
else update(root[i],root[i-1],1,n,1,n,0);//区间减
update(root[i],root[i],1,n,i-1,i-1,LNF);//单点修改
//注意这个update不能直接在原树上改，要新建一棵树，否则有可能修改到root[i-1]的树
}
for(int i=1;i<=n;i++)
q.push(data(t[root[i]].maxn+t[root[i]].tag,root[i],t[root[i]].where));//先把f[i]的最大值扔进队列
for(int i=1;i<k;i++)
{
data now=q.top();
q.pop();//取出队首
update(now.rt,now.rt,1,n,now.id,now.id,LNF);
q.push(data(t[now.rt].maxn+t[now.rt].tag,now.rt,t[now.rt].where));//放入次大值
}
printf("%lld\n",q.top().val);//操作k-1次后直接输出
return 0;
}
/*
7 3
3 -2 1 2 2 1 3
*/
原文地址：http://www.cnblogs.com/ez-lcw/p/16837304.html
