题解：P8930 「TERRA-OI R1」神，不惧死亡
Diigit
·
·
题解
题解 P8930
题意转化
首先我们先找到这个游戏的贪心策略：
把一段前缀数值（满足出现次数都为奇数）的出现次数削成 1，然后下一个数值全部削掉，答案就是下下个数值。
而如果没有下下个数值，那序列就削完了。
如果不能找到一个出现次数是偶数次的数，说明无法削掉任何数/游戏无法结束。
原因：你无法借助后续的削除削掉出现次数为偶数次的数，因为后续削除最多使这个数出现次数减 1，只能把 2 次削成 1 次。
例：
序列：1 1 1 2 3 3 4。
削前缀后：1 2 3 3 4。
削除 3：4。
所以问题转化为：对于一个序列，按数值从小到大找到第一个出现次数为偶数的数。
数据维护
对于一个序列区间加值域区间询问，单点修改的问题，我们显然可以用带修莫队加值域分块解决。
把值域分成 B 个块，维护 cnt_i，cntB_{j,0/1}，其中：
$cntB_{j,0}$ 表示块 $j$ 内出现次数大于零且为偶数的数的个数。
$cntB_{j,1}$ 表示块 $j$ 内出现次数大于零且为奇数的数的个数。
然后就可以 $O(1)$ 插入/删除，$O(\frac{n}{B})$ 查询了。
时间复杂度瓶颈在带修莫队上，为 $O(n^{\frac{5}{3}})$。
### 代码
```cpp
#include<bits/stdc++.h>
#define rep(a, b, c) for(int a=(b);a<=(c);a++)
#define rop(a, b, c) for(int a=(b);a>=(c);a--)
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
using namespace std;
const int N=5e5+10;
int pos[N], bl[N], br[N];
struct cnode{int x, y;}c[N];
struct qnode{int l, r, a, b, t, id;}q[N];
inline bool cmp(qnode a, qnode b) {return (pos[a.l]^pos[b.l])?pos[a.l]<pos[b.l]:((pos[a.r]^pos[b.r])?pos[a.r]<pos[b.r]:a.t<b.t);}
int n, m, ti, num, b[N], a[N], ans[N];
void init(int n, int siz) {
int len=ceil((double)n/siz);
rep(i, 1, len) {
bl[i]=siz*(i-1)+1;
br[i]=siz*i;
rep(j, bl[i], br[i]) pos[j]=i;
}
}
struct BK{
int cnt[N], cb[N][2];
inline void add(int x) {
cb[pos[x]][cnt[x]&1]-=(cnt[x]>0);
cnt[x]++;
cb[pos[x]][cnt[x]&1]+=(cnt[x]>0);
}
inline void del(int x) {
cb[pos[x]][cnt[x]&1]-=(cnt[x]>0);
cnt[x]--;
cb[pos[x]][cnt[x]&1]+=(cnt[x]>0);
}
inline int qry(int l, int r) {
// cerr<<"#:"<<l<<' '<<r<<' '<<pos[l]<<' '<<pos[r]<<'\n';
// rep(i, 1, n) cerr<<i<<' '<<cnt[i]<<' '<<pos[i]<<'\n';
// if(l==1&&r==5) {
// cerr<<"begin: \n";
// rep(i, 1, n) cerr<<i<<' '<<cnt[i]<<' '<<pos[i]<<'\n';
// cerr<<"end.\n";
// }
if(pos[l]==pos[r]) {
bool v=0;
rep(i, l, r) {
if(!cnt[i]) continue;
if(v) return i;
v=cnt[i]&1^1;
} return -1;
}
bool v=0;
rep(i, l, br[pos[l]]) {
if(!cnt[i]) continue;
if(v) return i;
v|=cnt[i]&1^1;
}
rep(i, pos[l]+1, pos[r]-1) {
if(cb[i][0]==0&&cb[i][1]==0) continue;
if(v||(cb[i][0]>0)) {
rep(j, bl[i], br[i]) {
if(!cnt[j]) continue;
if(v) return j;
v|=cnt[j]&1^1;
}
} v|=(cb[i][0]>0);
}
rep(i, bl[pos[r]], r) {
if(!cnt[i]) continue;
if(v) return i;
v|=cnt[i]&1^1;
} return -1;
}
}B;
signed main(){
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin>>n>>num;
rep(i, 1, n) {cin>>a[i]; b[i]=a[i];}
rep(i, 1, num) {
int opt;
cin>>opt;
if(opt==1) {
ti++;
cin>>c[ti].x>>c[ti].y;
c[ti].y=(b[c[ti].x]+=c[ti].y);
// cout<<ti<<'\n';
} else {
m++;
cin>>q[m].l>>q[m].r>>q[m].a>>q[m].b;
q[m].t=ti; q[m].id=m;
// cout<<ti<<'\n';
}
}
init(n, pow(n, 2.0/3.0));
sort(q+1, q+m+1, cmp);
init(n, sqrt(n));
int l=1, r=0, t=0;
rep(i, 1, m) {
int ql=q[i].l, qr=q[i].r, qt=q[i].t, qid=q[i].id, qa=q[i].a, qb=q[i].b;
while(l>ql) B.add(a[--l]);
while(r<qr) B.add(a[++r]);
while(l<ql) B.del(a[l++]);
while(r>qr) B.del(a[r--]);
// cout<<qid<<' '<<t<<' '<<qt<<'\n';
while(t<qt) {
++t;
if(ql<=c[t].x&&c[t].x<=qr) B.del(a[c[t].x]), B.add(c[t].y);
swap(a[c[t].x], c[t].y);
}
while(t>qt) {
if(ql<=c[t].x&&c[t].x<=qr) B.del(a[c[t].x]), B.add(c[t].y);
swap(a[c[t].x], c[t].y);
t--;
}
ans[qid]=B.qry(qa, qb);
}
rep(i, 1, m) cout<<ans[i]<<'\n';
return 0;
}
```