https://ac.nowcoder.com/acm/contest/12548

M - Stone Games

 

题意：给定一个数组，多次询问，每次询问给定L，R，问最小的，不能由区间 [L,R][L,R] 中的数求和得到的数值。

主席树

建立一个权值线段树，假设用左子树中的权值能凑出 11 到 XX 中所有的数，数组中位于右子树的元素和为 SS，则用整棵树能凑出 11 到 X+SX+S 中所有的数。但是如果 XX 小于数组中最小的且位于右子树的数-1，则说明一定有数无法被凑出来。这时就找到了答案。

因此对于这棵权值线段树，从权值 1 开始，不断合并右侧兄弟子树，合并前判断是否大于右侧子树最小值-1，这就需要递归右侧子树。所以总的复杂度为 O(Qlog⁡2(109))O(Q\log^2(10^9))。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
const int M = 1000000000;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
typedef pair<int, int>pii;

int n, q;
ll a[N];
ll ans;
#define mid ((l+r)>>1)
int root[N], tot;
int lc[N * 40], rc[N * 40];
ll trsum[N * 40];
void upd(int l, int r, int &x, int y, int q) {
	x = ++tot;
	lc[x] = lc[y]; rc[x] = rc[y];
	trsum[x] = trsum[y] + q;
	if (l == r)return;
	if (q <= mid)upd(l, mid, lc[x], lc[y], q);
	else upd(mid + 1, r, rc[x], rc[y], q);
}
ll ask(int x, int y, int l, int r) {
	if (trsum[x] - trsum[y] == 0)return inf;
	if (l == r)return l;
	if (trsum[lc[x]] - trsum[lc[y]] > 0)return ask(lc[x], lc[y], l, mid);
	else return ask(rc[x], rc[y], mid + 1, r);
}
ll qry(int x, int y, int l, int r) {
	if (l == r) {
		return trsum[x] - trsum[y];
	}
	ll tmp = qry(lc[x], lc[y], l, mid);
	if (tmp < ask(rc[x], rc[y], mid + 1, r) - 1)return tmp;
	else return tmp + trsum[rc[x]] - trsum[rc[y]];
}
int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		upd(1, M, root[i], root[i - 1], a[i]);
	}
	while (q--) {
		int l, r, tl, tr;
		scanf("%d%d", &l, &r);
		tl = 1ll*(l + ans) % n + 1;
		tr = 1ll*(r + ans) % n + 1;
		l = min(tl, tr);
		r = max(tl, tr);
		ans = qry(root[r], root[l - 1], 1, M) + 1;
		printf("%lld\n", ans);
	}
	return 0;
}