Description：

给一个数列，求第 $k$ 大子串，相同数字统计一次。

$1\le n \le 10^5$ $1\le k \le 2\times 10^5$

Solution：

注意到 $k$ 和 $n$ 是同级别的，于是一定是从第 $1$ 大开始一个一个求。

开 $n$ 棵线段树，第 $i$ 棵线段树维护每个位置到 $i$ 的后缀和，线段树维护一个最大值，开不下，可以用主席树，每次在上一颗树的基础上区间 $[pre + 1,i]$ 加 $a[i]$ ，主席树区间加，可以用标记永久化，用一个大根堆维护五元组 $(v,x,l,r,m)$ ，表示区间和为 $v$ ，所在线段树根节点为 $x$ ，所选左端点范围为 $[l,r]$ ，选了 $m$ 。然后重复 $k$ 次，每次取出堆顶，扩展出 $[l,m−1]$ 以及 $[m+1,r]$ 两个新状态。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<queue>

#include<vector>

#include<cstring>

using namespace std;

int n,k;

typedef long long ll; 

#define INF 0x3f3f3f3f

#define MAXN 100010

ll a[MAXN];

map<ll,int> pre;

struct node

{

	int lc,rc;

	int pos;

	ll tag,maxs;

	node(){pos = 0;tag = maxs = 0;}

}t[MAXN * 40];

int ptr = 0;

int newnode(){return ++ptr;}

int root[MAXN];

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	t[rt].pos = l;

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void add(int &rt,int rt_,ll k,int L,int R,int l,int r)

{

	rt = newnode();t[rt] = t[rt_];

	if(L <= l && r <= R)

	{

		t[rt].tag += k;t[rt].maxs += k;t[rt].pos = t[rt_].pos;

		return;

	}

	if(L <= mid)add(t[rt].lc,t[rt_].lc,k,L,R,l,mid);

	if(R >= mid + 1)add(t[rt].rc,t[rt_].rc,k,L,R,mid + 1,r);

	if(t[t[rt].lc].maxs >= t[t[rt].rc].maxs)

	{

		t[rt].maxs = t[t[rt].lc].maxs + t[rt].tag;

		t[rt].pos = t[t[rt].lc].pos;

	}

	else

	{

		t[rt].maxs = t[t[rt].rc].maxs + t[rt].tag;

		t[rt].pos = t[t[rt].rc].pos;

	}

	return;

}

struct state{ll maxs;int pos,rt,L,R;};

struct cmp

{

	bool operator ()(state a,state b){return a.maxs < b.maxs;}

};

pair<int,ll> query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return make_pair(t[rt].pos,t[rt].maxs);

	pair<int,ll> res;

	if(R <= mid){res = query(t[rt].lc,L,R,l,mid);res.second += t[rt].tag;return res;}

	if(L > mid){res = query(t[rt].rc,L,R,mid + 1,r);res.second += t[rt].tag;return res;}

	pair<int,ll> resl = query(t[rt].lc,L,R,l,mid),resr = query(t[rt].rc,L,R,mid + 1,r);

	return (resl.second > resr.second ? make_pair(resl.first,resl.second + t[rt].tag) : make_pair(resr.first,resr.second + t[rt].tag));

}

int main()

{

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

	for(int i = 1;i <= n;++i)scanf("%lld",&a[i]);

	build(root[0],1,n);

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

	{

		add(root[i],root[i - 1],a[i],pre[a[i]] + 1,i,1,n);

		pre[a[i]] = i;

	}

	priority_queue<state,vector<state>,cmp> q;

	pair<int,ll> l;

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

	{

		l = query(root[i],1,i,1,n);

		q.push((state){l.second,l.first,i,1,i});

	}

	ll res;

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

	{

		state tmp = q.top();q.pop();

		res = tmp.maxs;

		if(tmp.L < tmp.pos)

		{

			l = query(root[tmp.rt],tmp.L,tmp.pos - 1,1,n);

			q.push((state){l.second,l.first,tmp.rt,tmp.L,tmp.pos - 1});

		}

		if(tmp.pos < tmp.R)

		{

			l = query(root[tmp.rt],tmp.pos + 1,tmp.R,1,n);

			q.push((state){l.second,l.first,tmp.rt,tmp.pos + 1,tmp.R});

		}

	}

	cout << res << endl;

	return 0;

}