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

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

__將 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;
}
```