Codeforce 242 E. XOR on Segment 解析(思維、線段樹)

今天我們來看看CF242E
題目連結

題目
給一個數列，有兩種操作，區間和查詢或者是區間對某個數字$x$作XOR。

前言

這題蠻酷的

想法

首先一開始會覺得就是線段樹模板套進去就好，但是思考一下後會發現區段和做XOR和個別數字做XOR再加起來的結果不一樣。
因此我們需要對於數列中數字的每一個bit都建一棵線段樹。假設現在$a[i]$只有一個bit，那麼對$1$取XOR和取NOT是一樣的。而我們對$[l,r]$取XOR時，$[l,r]$的和原本如果是$k$，就會變成$length-k$，也就是$r-l-k$。如此我們就有辦法建線段樹了(維護某個bit，在區間有幾個$1$)。

程式碼:

const int _n=2e5+10;  
int t,l,r,x,n,m,a[_n];  
class Seg{  
  public:  
  int nn;  
  int t[_n<<2],laz[_n<<2];  
  void pull(int v){t[v]=t[2*v+1]+t[2*v+2];}  
  void apply(int v,int len){t[v]=len-t[v],laz[v]=(laz[v]?0:len);}  
  void push(int v){  
    if(laz[v])apply(2*v+1,laz[v]/2),apply(2*v+2,laz[v]/2+laz[v]%2),laz[v]=0;  
  }  
  void build(int v,int l,int r,int b){  
    if(l+1==r)t[v]=((a[l]&(1<<b))>0);  
    else{int m=(l+r)>>1;build(2*v+1,l,m,b),build(2*v+2,m,r,b);pull(v);}  
  }  
  void add(int v,int l,int r,int ql,int qr){  
    if(r<=ql or qr<=l)return;  
    else if(ql<=l and r<=qr)apply(v,r-l);  
    else{  
      push(v);int m=(l+r)>>1;  
      add(2*v+1,l,m,ql,qr),add(2*v+2,m,r,ql,qr);  
      pull(v);  
    }  
  }  
  void add(int l,int r){add(0,0,nn,l,r);}  
  void init(int n_,int b){nn=n_;build(0,0,nn,b);}  
  int query(int v,int l,int r,int ql,int qr){  
    if(r<=ql or l>=qr)return 0;  
    if(ql<=l and qr>=r)return t[v];  
    int m=(l+r)>>1,res;push(v);  
    res=query(2*v+1,l,m,ql,qr)+query(2*v+2,m,r,ql,qr);  
    pull(v);return res;  
  }  
};  
Seg STs[21];  
main(void) {cin.tie(0);ios_base::sync_with_stdio(0);  
  cin>>n;rep(i,0,n)cin>>a[i];  
  rep(i,0,21)STs[i].init(n,i);  
  cin>>m;while(m--){  
    cin>>t;  
    if(t==1){  
      cin>>l>>r;l--;  
      ll res=0;rep(i,0,21)res+=1ll*(STs[i].query(0,0,n,l,r))*(1<<i);  
      cout<<res<<'\n';  
    }else{  
      cin>>l>>r>>x;l--;  
      rep(i,0,21)if(x&(1<<i))STs[i].add(l,r);  
    }  
  }  
  return 0;  
}  

標頭、模板請點Submission看
Submission