替罪羊套线段树 O(nlog^2n)

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<ctime>
#include<cmath>
using namespace std;

typedef pair<int, int> Pii;
typedef long long LL;
typedef long double db;
#define rep(_,A,B) for(_=A;_<=B;++_)
#define repi(_,A,B) for(register int _=A;_<=B;++_)
#define FOR(_,A) for(int _=h[A];_;_=next[_])
#define A first
#define B second
#define mp make_pair
char o;template<class O> void read(O&x){while(o=getchar(),o<'0'||o>'9');for(x=o^48;o=getchar(),o>='0'&&o<='9';)x=x*10+(o^48);}
const int L = 70005, M = 10000005;
const double alpha = 0.8;

int n, Q;
int a[L], id[L]; 

struct T { 
     int l, r, s;
     T(){ l = r = s = 0; }
}e[M];
#define mid (l + r >> 1)

int rec[M], rec_num, tot;

inline int newnode(void) {
    if(rec_num) { e[rec[rec_num]] = T(); return rec[rec_num--]; }
    else return ++tot;
}

void reclaim(int &x) {
     if(!x) return ;
     rec[++rec_num] = x; reclaim(e[x].l), reclaim(e[x].r);
}

void ins(int &x, int l, int r, int y, int f) {
     if(!x)x = newnode(); e[x].s += f;
     //cout << "ins : " << x << " " << l << " " << r << " " << y << endl;
     if(l == r) return ;
     if(y <= mid) ins(e[x].l, l, mid, y, f);
     else ins(e[x].r, mid + 1, r, y, f); 
     if(!e[x].s) reclaim(x), x = 0;
}

int root[L], lc[L], rc[L], Root;

void build(int &x, int l, int r) {
     //cout << "build " << l << " " << r << endl; 
     if(l > r) return ;
     x = id[mid];
     build(lc[x], l, mid - 1), build(rc[x], mid + 1, r);
     repi(i, l, r) ins(root[x], 0, 70000, a[id[i]], 1);//, cout << "INS " << x << " " << i << endl;
}

void init(void) {
     cin >> n;
     repi(i, 1, n) read(a[i]), id[i] = i;
     build(Root, 1, n);
}

int q[L], cnt;

void del(int &x) {
     //cout << "del " << x << endl;
     if(!x) return ; reclaim(root[x]), root[x] = 0;
     del(lc[x]); q[++cnt] = x; del(rc[x]); x = 0;
}

void rebuild(int &x) {
     //cout << "rebuild : " << x << endl;
     cnt = 0; del(x);
     repi(i, 1, cnt) id[i] = q[i];//, cout << id[i] << " "; cout << endl;   
     build(x, 1, cnt);
}

int tmp;

void ins(int &x, int y, int z) {
     //cout << "ins : " << x << " " << y << " " << z << endl;
     if(!x) { x = ++n, ins(root[x], 0, 70000, z, 1), a[x] = z; return ;}
     ins(root[x], 0, 70000, z, 1);
     int t = e[root[lc[x]]].s;
     if(y <= t) ins(lc[x], y, z);
     else ins(rc[x], y - t - 1, z);
     if(e[root[x]].s * alpha > max(e[root[lc[x]]].s, e[root[rc[x]]].s)) {
        if(tmp) {
          //cout << "rc2 " << rc[2] << endl;
          if(lc[x] == tmp) rebuild(lc[x]);
          else rebuild(rc[x]);
        }
        tmp = 0;
     }
     else tmp = x;
} 

int modify(int x, int y, int val) {
     ins(root[x], 0, 70000, val, 1); 
     //cout << "modify : " << x << " " << y << " " << val << endl;
     int z, t = e[root[lc[x]]].s;
     if(y <= t) z = modify(lc[x], y, val);
     else if(y - 1 == t)z = a[x], a[x] = val;
     else z = modify(rc[x], y - t - 1, val);
     ins(root[x], 0, 70000, z, -1);
     return z;
}

int q1[L], q2[L], cnt1, cnt2;

void query(int x, int l, int r) {
     //cout << "query " << x << " " << l << " " << r << " ";
     int l_s = e[root[lc[x]]].s, r_s = e[root[x]].s;  //cout << l_s << " " << r_s << endl;
     if(l == 1 && r == r_s) { q1[++cnt1] = root[x]; /*cout << "q1 " << x << endl;*/ return ; }
     if(l <= l_s + 1 && l_s + 1 <= r) q2[++cnt2] = a[x];//, cout << "q2 " << x << endl;
     if(r <= l_s) query(lc[x], l, r);
     else if(l > l_s + 1) query(rc[x], l - l_s - 1, r - l_s - 1);
     else {
        if(l <= l_s) query(lc[x], l, l_s);
        if(r > l_s + 1) query(rc[x], 1, r - l_s - 1);
     }
}

int Query(int x, int y, int k) {
    cnt1 = cnt2 = 0; query(Root, x, y);
    int l = 0, r = 70000;
    while(l < r) {
       int t = 0;
       repi(i, 1, cnt1) t += e[e[q1[i]].l].s;
       repi(i, 1, cnt2) if(l <= q2[i] && q2[i] <= mid) ++t;
       if(k <= t) {
         repi(i, 1, cnt1) q1[i] = e[q1[i]].l; r = mid;
       }
       else {
         repi(i, 1, cnt1) q1[i] = e[q1[i]].r; l = mid + 1, k -= t;
       }
    }
    return l;
}

void work(void) {
     cin >> Q;
     char op[5]; int x, y, k, ans = 0;
     while(Q--) {
        //cout << "Q rc2 " << Q + 1 << " " << rc[2] << endl;
        scanf("%s", op); read(x), read(y); x ^= ans, y ^= ans;
        if(op[0] == 'Q') read(k), printf("%d\n", ans = Query(x, y, k ^ ans));
        else if(op[0] == 'M') modify(Root, x, y);
        else tmp = 0, ins(Root, x - 1, y); 
     }
}
int main(void) {
  freopen("3065.in","r",stdin), freopen("3065.out","w",stdout);
  init(), work(); return 0;
}