題目鏈接：點擊查看

題目大意：給出一個長度為 $n$ 的數列 $a$，現在需要執行 $m$ 次操作，每次操作分為兩種類型：

$1lrx$：對于所有 $i\in [l,r]$ 執行 $a_i=max(a_i,x)$

$2lrx$：對于區間 $[l,r]$ 內的 $a_i$ 加上 $x$ 這一共 $r?l+2$ 個數進行尼姆游戲，問先手必勝的情況下第一次能有多少種不同的取石子方案

題目分析：操作 $1$ 不難想到吉司機線段樹，所以只需要將操作 $2$ 轉換一下就可以了

下面參考官方題解：

對于所有數組的尼姆游戲，先求出其異或和 $xor$，如果 $xor=0$ 顯然答案為 $0$，如果不為 $0$ 的話需要挑選某一堆石子進行取數，假設某一堆石子為 $y$，如果想要從這堆石子取數，需要滿足 $y?(xor\oplus y)>0$ 才行，移項得到 $y>xor\oplus y$，考慮對于 $xor$ 的最高位來說，如果 $y$ 的這一位也是 $1$ 的話，前面的不等式顯然滿足，反之 $y<xor\oplus y$ 成立，所以現在操作 $2$ 的目標轉換為了：

求區間異或值

求二進制下區間內等于某個數的個數

因為操作 $2$ 需要求某個二進制的個數，還要求異或的答案，所以在儲存的時候就可以直接按位儲存區間和

代碼：

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=2e5+100; int sum[30]; struct Node {int l,r,num,mmin,se_mmin;//num:最小值的個數,mmin:區間最小值,se_mmin:次小值 int sum[30]; }tree[N<<2]; void pushup(int k) {tree[k].num=0;for(int i=0;i<30;i++)tree[k].sum[i]=tree[k<<1].sum[i]+tree[k<<1|1].sum[i];tree[k].mmin=min(tree[k<<1].mmin,tree[k<<1|1].mmin);tree[k].se_mmin=min(tree[k<<1].se_mmin,tree[k<<1|1].se_mmin);if(tree[k].mmin==tree[k<<1].mmin)tree[k].num+=tree[k<<1].num;elsetree[k].se_mmin=min(tree[k].se_mmin,tree[k<<1].mmin);if(tree[k].mmin==tree[k<<1|1].mmin)tree[k].num+=tree[k<<1|1].num;elsetree[k].se_mmin=min(tree[k].se_mmin,tree[k<<1|1].mmin); } void change(int k,int pre,int cur) {for(int i=0;i<30;i++){if((pre>>i)&1) tree[k].sum[i]-=tree[k].num;if((cur>>i)&1) tree[k].sum[i]+=tree[k].num;} } void pushdown(int k) {if(tree[k].mmin>tree[k<<1].mmin){change(k<<1,tree[k<<1].mmin,tree[k].mmin);tree[k<<1].mmin=tree[k].mmin;}if(tree[k].mmin>tree[k<<1|1].mmin){change(k<<1|1,tree[k<<1|1].mmin,tree[k].mmin);tree[k<<1|1].mmin=tree[k].mmin;} } void build(int k,int l,int r) {tree[k].l=l,tree[k].r=r;if(l==r){scanf("%d",&tree[k].mmin);tree[k].se_mmin=INT_MAX;tree[k].num=1;change(k,0,tree[k].mmin);return;}int mid=(l+r)>>1;build(k<<1,l,mid),build(k<<1|1,mid+1,r);pushup(k); } void update(int k,int l,int r,int val) {if(tree[k].mmin>=val) return;if(tree[k].l>r||tree[k].r<l) return;if(tree[k].l>=l&&tree[k].r<=r&&val<tree[k].se_mmin){change(k,tree[k].mmin,val);tree[k].mmin=val;return;}pushdown(k);update(k<<1,l,r,val),update(k<<1|1,l,r,val);pushup(k); } void query(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l) return;if(tree[k].l>=l&&tree[k].r<=r){for(int i=0;i<30;i++) sum[i]+=tree[k].sum[i];return;}pushdown(k);query(k<<1,l,r),query(k<<1|1,l,r); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;read(n),read(m);build(1,1,n);while(m--){int op,l,r,x;read(op),read(l),read(r),read(x);if(op==1) update(1,l,r,x);else if(op==2){int t=x;memset(sum,0,sizeof(sum));query(1,l,r);for(int i=0;i<30;i++) if(sum[i]&1) x^=(1<<i);if(!x){puts("0");continue;}int h=log2(x);write(sum[h]+((t>>h)&1)),putchar('\n');}}return 0; }

總結

以上是生活随笔為你收集整理的2020ICPC(南京) - Just Another Game of Stones(吉司机线段树+博弈)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。