题目链接：https://nanti.jisuanke.com/t/42547
题目大意
给定一个序列，有以下几种操作：
-
将第 (x) 位置的数修改为 (y)。
-
询问区间 ([L, R])，问其子集之和的 MEX。
思路
首先有一个性质：先看看是否存在 (1)。若没有 (1)，则表明必然无法凑出 (1)，那么答案就是 (1)。
然后假设上一次求出来的和的值为 (x)，表明 ([1,x]) 都可以通过子集表示出来。再求 ([1,x+1]) 的和，若和 ([1,x]) 求和的值相等，则表示 (x+1) 不能被表示。
最坏情况为斐波那契数列。
带修区间+小于某个树的值查询=树状数组套主席树！
花絮
因为并没有很好地使用之前已有的节点导致一直MLE，主席树盲目创建结点不可取。
AC代码
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN = 2e5 + 100;
class DS {
public:
// HJT begin
int ch[MAXN * 150][2], tot = 0;
ll sum[MAXN * 150];
inline void push_up(int rt) {
sum[rt] = sum[ch[rt][0]] + sum[ch[rt][1]];
}
int update(int rt, int pos, int val, int be, int en) {
int nrt = rt;
if (!rt) {
nrt = ++tot;
ch[nrt][0] = ch[nrt][1] = sum[nrt] = 0;
}
// int nrt = ++tot;
// ch[nrt][0] = ch[nrt][1] = sum[nrt] = 0;
if (be == en) {
sum[nrt] += (ll) be * val;
return nrt;
}
int mid = (be + en) >> 1;
if (pos <= mid) {
ch[nrt][0] = update(ch[rt][0], pos, val, be, mid);
ch[nrt][1] = ch[rt][1];
} else {
ch[nrt][0] = ch[rt][0];
ch[nrt][1] = update(ch[rt][1], pos, val, mid + 1, en);
}
push_up(nrt);
return nrt;
}
// HJT end
int n, c_len, root[MAXN];
void init(int _n, int _c_len) {
c_len = _c_len, n = _n;
for (int i = 1; i <= c_len; i++) root[i] = i;
tot = c_len;
}
inline int lowbit(int x) { return x & (-x); }
void insert(int pos, int pos_val, int val) {
for (int i = pos; i <= n; i += lowbit(i)) root[i] = update(root[i], pos_val, val, 1, c_len);
}
int t1[MAXN], t2[MAXN], n1, n2;
inline ll SUM(int R, int be, int en) {
if (be == en) {
ll ans = 0;
for (int i = 1; i <= n1; i++) ans -= sum[t1[i]];
for (int i = 1; i <= n2; i++) ans += sum[t2[i]];
return ans;
}
int mid = (be + en) >> 1;
ll ans = 0;
if (mid >= R) {
for (int i = 1; i <= n1; i++) t1[i] = ch[t1[i]][0];
for (int i = 1; i <= n2; i++) t2[i] = ch[t2[i]][0];
return SUM(R, be, mid);
} else {
for (int i = 1; i <= n1; i++) ans -= sum[ch[t1[i]][0]];
for (int i = 1; i <= n2; i++) ans += sum[ch[t2[i]][0]];
for (int i = 1; i <= n1; i++) t1[i] = ch[t1[i]][1];
for (int i = 1; i <= n2; i++) t2[i] = ch[t2[i]][1];
return ans + SUM(R, mid + 1, en);
}
}
ll query(int l, int r, int x) {
n1 = n2 = 0;
for (int i = l - 1; i >= 1; i -= lowbit(i)) t1[++n1] = root[i];
for (int i = r; i >= 1; i -= lowbit(i)) t2[++n2] = root[i];
return SUM(x, 1, c_len);
}
} tree;
int a[MAXN];
int main() {
//freopen("test.in", "r", stdin);
int n, q;
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
tree.init(n, 2e5);
for (int i = 1; i <= n; i++) {
tree.insert(i, a[i], 1);
}
while (q--) {
int opt;
scanf("%d", &opt);
if (opt == 1) {
int x, y;
scanf("%d%d", &x, &y);
tree.insert(x, a[x], -1);
a[x] = y;
tree.insert(x, a[x], 1);
} else {
int L, R;
scanf("%d%d", &L, &R);
ll now = 1, sum = 0;
while (1) {
int t = min(now, (ll) 2e5);
ll tmp = tree.query(L, R, t);
if (tmp == sum) {
printf("%lld
", now);
break;
} else {
sum = tmp, now = sum + 1;
}
}
}
}
// fclose(stdin);
}