【2021北京省选模拟】奇怪的数列 • TonyYin's Blog

题意#

有一个长度为 $n$ 的数字序列 $a$ ，对这个序列的任意一个连续子串，求所有数字之和，重复出现的数字只被统计一次。问第 $k$ 大的和是多少。

$n\leq 10^5$ ， $k\leq 2\times 10^5$ ， $0\leq |a_i|\leq 10^9$ .

思路#

下面提到的所有区间和均为去重后的区间和。

考虑用线段树维护。

以右端点为横坐标，第 $i$ 棵线段树维护：以 $i$ 作为左端点的所有区间和的最大值。

先考虑第 $1$ 棵线段树。由于 $a_i$ 较大，先借助 $\rm{map}$ 处理出去重后的前缀和。

for(int i = 1; i <= n; i++) {
    pre_sum[i] = pre_sum[i - 1];
    if(!mp[in[i]]) {
        pre_sum[i] += in[i];
        mp[in[i]] = 1;
    }
}

cpp

这样我们就知道了：所有以 $1$ 作为左端点的区间和。依此直接建树即可得到第 $1$ 棵线段树。

对于后面的 $n-1$ 棵线段树，如果采取同样的方法，时间和空间都会炸。

我们发现，第 $i$ 棵线段树和第 $i-1$ 棵线段树差距不大，因此使用可持久化线段树，使线段树之间共享节点。

进一步，从第 $i$ 棵线段树转移到第 $i+1$ 棵线段树，只变了 $i$ 到下一次 $a_i$ 出现的位置之前这段区间。右端点在这段区间内的线段都减少了 $a_i$ .

同样，我们借助 $\rm{map}$ 预处理出每个元素 $a_i$ 下一次出现的位置 $\operatorname{next}_{a_i}$ ，每次就可以通过上一棵线段树直接转移出当前所求。

void add(int &id, int his, int l, int r, int L, int R, int v) {}

for(int l = 2; l <= n; l++) { //l为左端点
    root[l] = root[l - 1];
    add(root[l], root[l - 1], 1, n, l - 1, nxt[l - 1] - 1, -in[l - 1]);
    add(root[l], root[l], 1, n, l - 1, l - 1, -inf);
}

cpp

用主席树维护之后，开始解决第 $k$ 大的问题。

由于 $k$ 不大， $\mathcal{O}(k\log)$ 的复杂度可以接受，直接用大根堆维护。

先找出以每个 $i$ 作为左端点的最大区间和，共 $n$ 个，加入大根堆。

priority_queue<pair<pair<int, int>, int> > q;
for(int i = 1; i <= n; i++) q.push(make_pair(t[root[i]].mx, i));

cpp

之后每次取出后，利用线段树找到另一个最大的。

int ans;
while(k--) {
    pair<pair<int, int>, int> now = q.top(); q.pop();
    ans = now.first.first;
    add(root[now.second], root[now.second], 1, n, now.first.second, now.first.second, -inf);
    q.push(make_pair(t[root[now.second]].mx, now.second));
}
cout << ans << endl;

cpp

Code#

#include <bits/stdc++.h>
#define int long long
using namespace std;

inline int read() {
	int ret = 0, ch = getchar(), f = 1;
	while(ch < '0' || ch > '9') {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch <= '9' && ch >= '0') {
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	return ret * f;
}
const int MAXN = 1e5 + 10;
const int inf = 0x3f3f3f3f3f3f3f3fll;
int n, k;
int in[MAXN], pre_sum[MAXN];
int nxt[MAXN];
map<int, int> mp;
struct node{
	pair<int, int> mx;
	int add_mark, l, r;
} t[MAXN << 8];
int point_cnt = 0;
void push_up(int id) {
	t[id].mx = max(t[t[id].l].mx, t[t[id].r].mx);
}
void build(int &id, int l, int r) {
	id = ++point_cnt;
	if(l == r) {
		t[id].mx = make_pair(pre_sum[l], l);
		return;
	}
	int mid = (l + r) >> 1;
	build(t[id].l, l, mid);
	build(t[id].r, mid + 1, r);
	push_up(id);
}
int root[MAXN];
void add_point(int &id, int v) {
	if(!id) return;
	t[++point_cnt] = t[id]; id = point_cnt;
	if(v == -inf) {
		t[id].mx.first = t[id].add_mark = v;
	} else {
		t[id].mx.first += v; t[id].add_mark += v;
	}
}
void push_down(int id) {
	if(!t[id].add_mark) return;
	if(t[id].l) add_point(t[id].l, t[id].add_mark);
	if(t[id].r) add_point(t[id].r, t[id].add_mark);
	t[id].add_mark = 0;
}
void add(int &id, int his, int l, int r, int L, int R, int v) {
	id = ++point_cnt;
	t[id].mx.first = -inf;
	if(l == L && r == R) {
		t[id] = t[his];
		add_point(id, v);
		return;
	}
	push_down(his);
	int mid = (l + r) >> 1;
	if(R <= mid) {
		t[id].r = t[his].r;
		add(t[id].l, t[his].l, l, mid, L, R, v);
	} else if(L > mid) {
		t[id].l = t[his].l;
		add(t[id].r, t[his].r, mid + 1, r, L, R, v);
	} else {
		add(t[id].l, t[his].l, l, mid, L, mid, v);
		add(t[id].r, t[his].r, mid + 1, r, mid + 1, R, v);
	}
	push_up(id);
}
signed main() {
	n = read(); k = read();
	for(int i = 1; i <= n; i++) in[i] = read();
	for(int i = 1; i <= n; i++) nxt[i] = n + 1;
	for(int i = n; i >= 1; i--) {
		if(mp[in[i]]) nxt[i] = mp[in[i]];
		mp[in[i]] = i;
	}
	mp.clear();
	for(int i = 1; i <= n; i++) {
		pre_sum[i] = pre_sum[i - 1];
		if(!mp[in[i]]) {
			pre_sum[i] += in[i];
			mp[in[i]] = 1;
		}
	}
	t[0].mx = make_pair(-inf-1, 0);
	build(root[1], 1, n);
	for(int l = 2; l <= n; l++) {
		root[l] = root[l - 1];
		add(root[l], root[l - 1], 1, n, l - 1, nxt[l - 1] - 1, -in[l - 1]);
 		add(root[l], root[l], 1, n, l - 1, l - 1, -inf);
	}
	priority_queue<pair<pair<int, int>, int> > q;
	for(int i = 1; i <= n; i++) q.push(make_pair(t[root[i]].mx, i));
	int ans;
	while(k--) {
		pair<pair<int, int>, int> now = q.top(); q.pop();
		ans = now.first.first;
		add(root[now.second], root[now.second], 1, n, now.first.second, now.first.second, -inf);
		q.push(make_pair(t[root[now.second]].mx, now.second));
	}
	cout << ans << endl;
	return 0;
}

cpp