HE XOR queries ( Persistent Segment Tree on BIT, XOR, Online, Kth )

XOR queries | Segment Trees & Data Structures Practice Problems | HackerEarth

題意：
給一個數列 A。要求在線處理 Q 筆詢問：
第一種：
__將 A[ i ] 改為 x
第二種：
__問 A[ l, r ] 排序後，其中 [ i, j ] 間的 xor 值為何。

制約：
N, Q ≤ 5e4
1 ≤ A[ i ], x ≤ 1e5

解法：
BIT 套持久化線段樹。首先想像維護第 i 棵線段樹保有區間中數值為 i 的數量。對第二種詢問，可以在 BIT 上二分搜出第 K 大的值為何，並用前綴和的關係就能處理答案 ( query( l, r, i, j ) = prefix_xor( l, r, i - 1 ) xor prefix_xor( l, r, j ) )。

時間 / 空間複雜度：
O( N lg^2 N + Q lg^2 N )

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = int( 5e4 );
const int MAXA = int( 1e5 );
 
int N, Q;
int A[ MAXN ];
 
tuple< int, int, int, int > online( int ans, int L, int R, int I, int J ) {
  int ll = 1 + ( ( ans ^ L ) % N );
  int rr = 1 + ( ( ans ^ R ) % N );
  if( ll > rr ) swap( ll, rr );
  int ii = 1 + ( ( I ^ ans ) % ( rr - ll + 1 ) );
  int jj = 1 + ( ( J ^ ans ) % ( rr - ll + 1 ) );
  if( ii > jj ) swap( ii, jj );
  return make_tuple( ll, rr, ii, jj );
}
 
struct pst { // persistent segment tree
  int cnt, xsum;
  pst *lc, *rc;
  pst() {
    cnt = xsum = 0;
    lc = rc = NULL;
  }
  void pull() {
    cnt = xsum = 0;
    if( lc ) {
      cnt += lc->cnt;
      xsum ^= lc->xsum;
    }
    if( rc ) {
      cnt += rc->cnt;
      xsum ^= rc->xsum;
    }
  }
} *root[ MAXA + 1 ];
 
pst* clone( pst *rt ) {
  pst *res = new pst();
  if( rt == NULL ) return res;
  res->cnt = rt->cnt;
  res->xsum = rt->xsum;
  res->lc = rt->lc;
  res->rc = rt->rc;
  return res;
}
 
pst* add( pst *rt, int lb, int rb, int k, int v, int x ) {
  pst *res = clone( rt );
  if( lb + 1 == rb ) {
    res->cnt += v;
    res->xsum ^= x;
    return res;
  }
  int mid = lb + rb >> 1;
  if( k < mid ) {
    res->lc = add( rt ? rt->lc : NULL, lb, mid, k, v, x );
  } else {
    res->rc = add( rt ? rt->rc : NULL, mid, rb, k, v, x );
  }
  res->pull();
  return res;
}
 
pair< int, int > query( pst *rt, int lb, int rb, int ql, int qr ) {
  if( rt == NULL or qr <= lb or rb <= ql ) return make_pair( 0, 0 );
  if( ql <= lb and rb <= qr ) return make_pair( rt->cnt, rt->xsum );
  int mid = lb + rb >> 1;
  pair< int, int > res( 0, 0 );
  if( rt->lc ) {
    int f, s;
    tie( f, s ) = query( rt->lc, lb, mid, ql, qr );
    res.first += f;
    res.second ^= s;
  }
  if( rt->rc ) {
    int f, s;
    tie( f, s ) = query( rt->rc, mid, rb, ql, qr );
    res.first += f;
    res.second ^= s;
  }
  return res;
}
 
int xsum_prefix_k( int k, int lb, int rb ) { // k: 1 base, [ lb, rb ): 0 base
  int x = 0;
  int res = 0;
  for( int i = 1 << 31 - __builtin_clz( MAXA ); i and k; i >>= 1 ) {
    if( x + i > MAXA ) continue;
    int cnt, xsum;
    tie( cnt, xsum ) = query( root[ x + i ], 0, N, lb, rb );
    if( cnt <= k ) {
      k -= cnt;
      res ^= xsum;
      x += i;
    }
  }
  return res;
}
 
signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> Q;
  for( int i = 0; i < N; ++i ) {
    cin >> A[ i ];
    for( int j = A[ i ]; j <= MAXA; j += j & -j ) {
      root[ j ] = add( root[ j ], 0, N, i, 1, A[ i ] );
    }
  }
  int ans = 0;
  for( int qi = 0; qi < Q; ++qi ) {
    int op;
    cin >> op;
    if( op == 1 ) {
      int id, x;
      cin >> id >> x;
      for( int i = A[ id - 1 ]; i <= MAXA; i += i & -i ) {
        root[ i ] = add( root[ i ], 0, N, id - 1, -1, A[ id - 1 ] );
      }
      A[ id - 1 ] = x;
      for( int i = A[ id - 1 ]; i <= MAXA; i += i & -i ) {
        root[ i ] = add( root[ i ], 0, N, id - 1, 1, A[ id - 1 ] );
      }
    } else {
      int L, R, I, J;
      cin >> L >> R >> I >> J;
      int ll, rr, ii, jj;
      tie( ll, rr, ii, jj ) = online( ans, L, R, I, J );
      ans = xsum_prefix_k( ii - 1, ll - 1, rr ) ^ xsum_prefix_k( jj, ll - 1, rr );
      cout << ans << "\n";
    }
  }
  return 0;
}