Just Another Game of Stones 吉司机线段树 + 尼姆博弈
题目大意：
给你n个数，有两种操作：
- 给你 (l,r,x) 表示在区间 ([l,r]) 更新 (b[i] = max(b[i],x))
- 给你 (l,r,x) 表示求区间 ([l,r]) 和 一堆数量为 (x) ，问先手有多少种不同的方案数使得在 (r - l +2) 堆石头的尼姆博弈中获得胜利。
题解：
对于第一种操作，很明显可以用吉斯机线段树解决，对于第二种操作，首先你要明白如何求尼姆博弈先手胜利的方案数，如果有 (m) 堆石头，假设 (sum) 为 (n) 堆石头的异或和，那么对于第 (i) 堆石头，假设这堆有 (y) 个石头，那么如果 (y>sum \,\,xor\,\,y) 则先手胜利，如果对于 (sum) 的二进制的最高位，如果 (y) 这一个二进制位 (bit = 1) ，那么 (y>sum \,\,xor\,\,y) ，如果 (bit = 0) ，那么 (y<sum \,\,xor\,\,y) ，所以只需要维护二进制的状态即可。
这个题目把我写的要吐血了，重构了好几回，写了两天，发现我的inf设置的小了。。。昨天晚上就可以A的，真的要把我给气死了。。。
我令 (inf = 0x3f3f3f3f) 不够，应该设置成这个的两倍或者 (inf = INT\_MAX;)
//最后重构的代码
#include <bits/stdc++.h>
#define lson (id<<1)
#define rson (id<<1|1)
using namespace std;
const int maxn = 2e5 + 10;
const int inf = INT_MAX;
const int base = 31;
int seg[maxn<<2],mi[maxn<<2],se[maxn<<2],cnt[maxn<<2],lazy[maxn<<2],bit[maxn<<2][33];
int a[maxn];
void pushUp(int id){
seg[id] = seg[lson] ^ seg[rson];
for(int i=0;i<base;i++) bit[id][i] = bit[lson][i] + bit[rson][i];
if(mi[lson]==mi[rson]){
mi[id] = mi[lson],cnt[id] = cnt[lson] + cnt[rson];
se[id] = min(se[lson],se[rson]);
}
else{
int ls = lson,rs = rson;
if(mi[rs]<mi[ls]) swap(ls,rs);
mi[id] = mi[ls],cnt[id] = cnt[ls];
se[id] = min(se[ls],mi[rs]);
}
}
void build(int id,int l,int r){
lazy[id] = 0;
if(l==r){
seg[id] = mi[id] = a[l];
se[id] = inf,cnt[id] = 1;
for(int i=0;i<base;i++) bit[id][i] = (a[l]>>i&1);
return ;
}
int mid = (l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
pushUp(id);
}
void work(int id,int v){
if(cnt[id]&1) seg[id]^=mi[id]^v;
for(int i=0;i<base;i++) {
bit[id][i] -= (mi[id]>>i&1)*cnt[id];
bit[id][i] += (v>>i&1)*cnt[id];
}
mi[id] = lazy[id] = v;
}
void pushDown(int id){
if(lazy[id]>mi[lson]) work(lson,lazy[id]);
if(lazy[id]>mi[rson]) work(rson,lazy[id]);
}
void update(int id,int l,int r,int x,int y,int v){
if(v<=mi[id]) return;
if(x<=l&&y>=r&&v<se[id]){
work(id,v);
return ;
}
pushDown(id);
int mid = (l+r)>>1;
if(x<=mid) update(lson,l,mid,x,y,v);
if(y>mid) update(rson,mid+1,r,x,y,v);
pushUp(id);
}
int queryXor(int id,int l,int r,int x,int y){
if(x<=l&&y>=r) return seg[id];
int ans = 0,mid = (l+r)>>1;
pushDown(id);
if(x<=mid) ans^=queryXor(lson,l,mid,x,y);
if(y>mid) ans^=queryXor(rson,mid+1,r,x,y);
return ans;
}
int queryBit(int id,int l,int r,int x,int y,int p){
if(x<=l&&y>=r) return bit[id][p];
int ans = 0,mid = (l+r)>>1;
pushDown(id);
if(x<=mid) ans+=queryBit(lson,l,mid,x,y,p);
if(y>mid) ans+=queryBit(rson,mid+1,r,x,y,p);
return ans;
}
int main(){
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,1,n);
while(q--){
int op,l,r,x;
scanf("%d%d%d%d",&op,&l,&r,&x);
if(op==1) update(1,1,n,l,r,x);
else{
int sum = queryXor(1,1,n,l,r)^x,ans = (x>(sum^x));
if(sum>0){
int now = sum,pos = -1;
while(now) now>>=1,pos++;
ans += queryBit(1,1,n,l,r,pos);
}
printf("%d
",ans);
}
}
return 0;
}
//之前优化的代码
#include <bits/stdc++.h>
#define lson (id<<1)
#define rson (id<<1|1)
using namespace std;
const int maxn = 2e5+10;
const int inf = INT_MAX;
typedef long long ll;
struct node{ // 维护二进制的线段树
int mi,se,cnt,lazy,s,bit[40];
}tree[maxn<<2];
int a[maxn];
void push_up(int id){
tree[id].s = tree[lson].s ^ tree[rson].s;
int ls = id<<1,rs = id<<1|1;
if(tree[lson].mi == tree[rson].mi){
tree[id].mi = tree[lson].mi;
tree[id].cnt = tree[lson].cnt + tree[rson].cnt;
tree[id].se = min(tree[lson].se,tree[rson].se);
}
else {
if (tree[lson].mi < tree[rson].mi) swap(ls, rs);
tree[id].mi = tree[rs].mi;
tree[id].cnt = tree[rs].cnt;
tree[id].se = min(tree[rs].se, tree[ls].mi);
}
for(int i=0;i<31;i++) tree[id].bit[i] = tree[lson].bit[i] + tree[rson].bit[i];
}
void build(int id,int l,int r){
tree[id].lazy = -1;
if(l==r){
tree[id].mi = tree[id].s = a[l];
tree[id].se = inf,tree[id].cnt = 1;
for(int i=0;i<31;i++) tree[id].bit[i] = a[l]>>i&1;
return ;
}
int mid = (l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
push_up(id);
}
void work(int id,int val){
if(tree[id].cnt&1) tree[id].s ^= tree[id].mi ^ val;
for(int i=0; i<31; ++i){
tree[id].bit[i] -= (tree[id].mi>>i&1)*tree[id].cnt;
tree[id].bit[i] += (val>>i&1)*tree[id].cnt;
}
tree[id].lazy = tree[id].mi = val;
}
void push_down(int id){
if(tree[id].lazy>tree[lson].mi) work(lson,tree[id].lazy);
if(tree[id].lazy>tree[rson].mi) work(rson,tree[id].lazy);
}
void update(int id,int l,int r,int x,int y,int val){
if(x>r||y<l||val<=tree[id].mi) return ;
int mid = (l+r)>>1;
if(x<=l&&y>=r&&tree[id].se>val){
work(id,val);
return ;
}
push_down(id);
if(x<=mid) update(lson,l,mid,x,y,val);
if(y>mid) update(rson,mid+1,r,x,y,val);
push_up(id);
}
int queryXor(int id,int l,int r,int x,int y){
if(x>r||y<l) return 0;
if(x<=l&&y>=r) return tree[id].s;
int mid = (l+r)>>1,ans = 0;
push_down(id);
if(x<=mid) ans ^= queryXor(lson,l,mid,x,y);
if(y>mid) ans ^= queryXor(rson,mid+1,r,x,y);
return ans;
}
int querySum(int id,int l,int r,int x,int y,int f){
if(x>r||y<l) return 0;
if(x<=l&&y>=r) return tree[id].bit[f];
push_down(id);
int mid = (l+r)>>1,ans = 0;
if(x<=mid) ans+=querySum(lson,l,mid,x,y,f);
if(y>mid) ans+=querySum(rson,mid+1,r,x,y,f);
return ans;
}
int main(){
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,1,n);
while(q--){
int op,l,r,x;
scanf("%d%d%d%d",&op,&l,&r,&x);
if(op==1) update(1,1,n,l,r,x);
else{
int sum = queryXor(1,1,n,l,r)^x;
int ans = 0;
if(sum>0){
int now = sum,pos = -1;
while(now) now>>=1,pos++;
ans = querySum(1,1,n,l,r,pos);
if(x>(sum^x)) ans++;
}
printf("%d
",ans);
}
}
return 0;
}
//第一份AC代码
#include <bits/stdc++.h>
#define lson (id<<1)
#define rson (id<<1|1)
using namespace std;
const int maxn = 2e5 + 10;
const int inf = INT_MAX;
const int base = 31;
int seg[maxn<<2],mi[maxn<<2],se[maxn<<2],cnt[maxn<<2],lazy[maxn<<2],bit[maxn<<2][33];
int a[maxn];
void pushUp(int id){
seg[id] = seg[lson] ^ seg[rson];
for(int i=0;i<base;i++) bit[id][i] = bit[lson][i] + bit[rson][i];
if(mi[lson]==mi[rson]){
mi[id] = mi[lson],cnt[id] = cnt[lson] + cnt[rson];
se[id] = min(se[lson],se[rson]);
}
else{
int ls = lson,rs = rson;
if(mi[rs]<mi[ls]) swap(ls,rs);
mi[id] = mi[ls],cnt[id] = cnt[ls];
se[id] = min(se[ls],mi[rs]);
}
}
void build(int id,int l,int r){
lazy[id] = 0;
if(l==r){
seg[id] = mi[id] = a[l];
se[id] = inf,cnt[id] = 1;
for(int i=0;i<base;i++) bit[id][i] = (a[l]>>i&1);
return ;
}
int mid = (l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
pushUp(id);
}
void work(int id,int v){
if(cnt[id]&1) seg[id]^=mi[id]^v;
for(int i=0;i<base;i++) {
bit[id][i] -= (mi[id]>>i&1)*cnt[id];
bit[id][i] += (v>>i&1)*cnt[id];
}
mi[id] = lazy[id] = v;
}
void pushDown(int id){
if(lazy[id]>mi[lson]) work(lson,lazy[id]);
if(lazy[id]>mi[rson]) work(rson,lazy[id]);
}
void update(int id,int l,int r,int x,int y,int v){
if(v<=mi[id]) return;
if(x<=l&&y>=r&&v<se[id]){
work(id,v);
return ;
}
pushDown(id);
int mid = (l+r)>>1;
if(x<=mid) update(lson,l,mid,x,y,v);
if(y>mid) update(rson,mid+1,r,x,y,v);
pushUp(id);
}
int queryXor(int id,int l,int r,int x,int y){
if(x<=l&&y>=r) return seg[id];
int ans = 0,mid = (l+r)>>1;
pushDown(id);
if(x<=mid) ans^=queryXor(lson,l,mid,x,y);
if(y>mid) ans^=queryXor(rson,mid+1,r,x,y);
return ans;
}
int queryBit(int id,int l,int r,int x,int y,int p){
if(x<=l&&y>=r) return bit[id][p];
int ans = 0,mid = (l+r)>>1;
pushDown(id);
if(x<=mid) ans+=queryBit(lson,l,mid,x,y,p);
if(y>mid) ans+=queryBit(rson,mid+1,r,x,y,p);
return ans;
}
int main(){
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,1,n);
while(q--){
int op,l,r,x;
scanf("%d%d%d%d",&op,&l,&r,&x);
if(op==1) update(1,1,n,l,r,x);
else{
int sum = queryXor(1,1,n,l,r)^x,ans = (x>(sum^x));
if(sum>0){
int now = sum,pos = -1;
while(now) now>>=1,pos++;
ans += queryBit(1,1,n,l,r,pos);
}
printf("%d
",ans);
}
}
return 0;
}