I-Kuriyama Mirai and Exclusive Or

KeHe題解
diabolusexnihil題解

不過diabolusexnihil大佬的題解有一部分寫錯了應該是：每次分裂標記$b_{l,i}$需要給數組$[l+2^{i?1},l+2^i)\oplus 2^{i?1}$然后標記分裂成$b_{l,i?1},b_{l+2^{i?1},i?1}$

#include<bits/stdc++.h> using namespace std; using ll=long long; template <class T=int> T rd() {T res=0;T fg=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') fg=-1;ch=getchar();}while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res*fg; } int n,q; const int N=600010; int a[N],tag[N]; bool b[N][22]; int main() {n=rd(),q=rd();for(int i=1;i<=n;i++) a[i]=rd();while(q--){int op=rd(),l=rd(),r=rd(),x=rd();if(!op) // 操作一直接差分打標記{tag[l]^=x,tag[r+1]^=x;continue;}// 考慮區間[l,l+2^i) 每次考慮lowbit(x) ^(x+i) -> ^x^ifor(int i=0;i<=19;i++)if((x>>i&1)&&(l+(1<<i)-1)<=r)// 注意右端點{b[l][i]^=1;tag[l]^=(x>>i)<<i; tag[l+(1<<i)]^=(x>>i)<<i;//差分打標記l+=(1<<i);x+=(1<<i);}// 最后一段區間[l,r]// 此時如果l+2^i<r 那么 x>>i&1一定是0 同樣 ^(x+i) -> ^x^i效仿上面做法即可for(int i=19;i>=0;i--)if((l+(1<<i)-1)<=r){b[l][i]^=1;tag[l]^=(x>>i)<<i;tag[l+(1<<i)]^=(x>>i)<<i;l+=(1<<i);x+=(1<<i);}}// 標記分裂for(int i=19;i>=1;i--)for(int j=1;j<=n;j++){if(!b[j][i]) continue;b[j][i-1]^=1;// 分裂標記1if(j+(1<<(i-1))<=n){b[j+(1<<(i-1))][i-1]^=1;// 分裂標記2// [l+2^{i-1},l+2^i) 需要打上抑或 2^{i-1}的標記tag[j+(1<<(i-1))]^=(1<<(i-1));if(j+(1<<i)<=n) tag[j+(1<<i)]^=(1<<(i-1));}}for(int i=1;i<=n;i++){tag[i]^=tag[i-1];printf("%d%c",a[i]^tag[i]," \n"[i==n]);}}

一輩子學不會的做法www

總結

以上是生活随笔為你收集整理的2021牛客暑期多校训练营3 I-Kuriyama Mirai and Exclusive Or（异或+差分）的全部內容，希望文章能夠幫你解決所遇到的問題。

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