前言
图灵山脉之中有着数不清的奇峰异石, 而其中, 名为’傻逼变态数据结构题’一峰更是高达万丈, 是图灵山脉中最难攀登的几座高峰之一。有生之年, 吾辈终于得以体验攀登此峰之愉悦快感…
好吧也可以说是SGT专练…(替罪羊树)
紫荆花之恋
题目大意:
有一棵树, 树点和树边带权, 要求维护以下操作:
1.插入一个节点。
2.询问树上所有点对(u, v)的数量。其中u和v满足dist(u, v)≤A[u]+A[v](u和v的点权和)
强制在线。
解题报告
淦!
首先考虑纯暴力做法。考虑插入一个节点cur后对答案的影响。
沿着cur的father链向上跳, 设当前跳到了节点u。
如果有一条路径(x, cur)满足条件并且x在u的子树内, 并且路径经过点u, 那意味着dist(x, u)+dist(u, cur)≤A[x]+A[cur]。
变形可得dist(x, u)-A[x]≤A[cur]-dist(u, cur)。每个节点使用一个Treap维护等式左边那一坨(把子树内每个节点的dist(x, u)-A[x]都塞进去), 直接在Treap内查询即可。这样当x和cur拥有同一个u的儿子节点作为父亲时就会算重, 那么对每个节点v再维护一个Treap塞dist(x, fa[v])-A[x]在统计答案时减掉就可以了。
然后由于树的形态可能很鬼畜(链), 需要对树进行点分治来维护树相对平衡的结构。动态插入怎么办呢? 利用替罪羊树的思想当点分治分支结构的缺陷性达到一个阈值后整块暴力重建即可。
貌似还好。
然后Hineven就码了2h, 调了6h+。
Treap在rebuild的时候没有考虑重复元素塞到一个节点的问题。
在点分治重建遍历的时候思路出毒…导致重构代码还是wa在同一个地方没话可说。
前前后后码了应该有30k…至少AC了…醉了…
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <set>
#include <assert.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int MAXN = 100100;
namespace Treap {
const int MAXD = MAXN*180;
struct Node {
int ch[2], fa, val, sz;
int prio;
} d[MAXD];
int dtot;
int memstk[MAXD], stktop;
inline void updata (int u)
{d[u].sz = d[d[u].ch[0]].sz+d[d[u].ch[1]].sz+1;}
inline int newNode (int val, int fa) {
int u;
if(!stktop) u = ++dtot;
else {
u = memstk[stktop --];
d[u].ch[0] = d[u].ch[1] = 0;
}
d[u].prio = rand();
d[u].val = val, d[u].fa = fa;
d[u].sz = 1;
return u;
}
struct Root {
int root;
Root () {root = 0;}
int * src;
inline int build (int lb, int rb) {
if(lb > rb) return 0;
if(lb == rb) return newNode(src[lb], 0);
int mid = (lb+rb)>>1;
int u = newNode(src[mid], 0);
d[d[u].ch[0] = build(lb, mid-1)].fa = u;
d[d[u].ch[1] = build(mid+1, rb)].fa = u;
d[u].prio = max(d[d[u].ch[0]].prio, d[d[u].ch[1]].prio)+1;
updata(u);
return u;
}
inline void releaseMemory (int u) {
if(!u) return ;
memstk[++stktop] = u;
releaseMemory(d[u].ch[0]);
releaseMemory(d[u].ch[1]);
}
inline void clear () {
releaseMemory(root);
root = 0;
}
inline void buildFrom (int * s_pointer, int len) {
clear();
src = s_pointer;
sort(src+1, src+len+1);
root = build(1, len);
}
inline void rotate (int x) {
int y = d[x].fa;
bool f = d[y].ch[1] == x;
d[y].ch[f] = d[x].ch[!f];
d[d[y].ch[f]].fa = y;
d[x].ch[!f] = y;
d[x].fa = d[y].fa;
d[y].fa = x;
d[d[x].fa].ch[d[d[x].fa].ch[1] == y] = x;
if(!d[x].fa) root = x;
updata(y), updata(x);
}
inline void adjust (int u) {
while(d[u].fa && d[u].prio > d[d[u].fa].prio) rotate(u);
}
inline void insert (int val) {
if(!root) {root = newNode(val, 0); return ;}
int u = root, l = 0;
while(u) {
l = u; d[u].sz++;
if(d[u].val < val) u = d[u].ch[1];
else u = d[u].ch[0];
}
u = newNode(val, l);
d[l].ch[d[l].val < val] = u;
adjust(u);
}
inline int queryLEq (int val) const {
int u = root, ret = 0;
while(u) {
if(d[u].val > val) u = d[u].ch[0];
else ret += d[d[u].ch[0]].sz+1, u = d[u].ch[1];
}
return ret;
}
} ;
}
int N;
struct DiGraph {
struct Node {
int v, nxt, w;
} d[MAXN*4];
int head[MAXN], etot;
int memstk[MAXN*4], stktop;
inline int newEdge () {
if(stktop) return memstk[stktop--];
else return ++etot;
}
inline void eraseNode (int u) {
for(int e = head[u]; e; e = d[e].nxt)
memstk[++stktop] = e;
head[u] = 0;
}
inline void addEdge (int a, int b, int c = 0) {
int e = newEdge();
d[e].v = b;
d[e].nxt = head[a];
d[e].w = c;
head[a] = e;
}
inline Node & operator [] (int index) {
return d[index];
}
} inp;
namespace ST {
int dep[MAXN], depl[MAXN];
int fa[MAXN][20];
void stMaintain (int f, int u, int dist) {
fa[u][0] = f, dep[u] = dep[f]+1, depl[u] = depl[f]+dist;
for(int i = 1; i<20; i++)
fa[u][i] = fa[fa[u][i-1]][i-1];
}
int stLCA (int a, int b) {
if(dep[a] < dep[b]) swap(a, b);
for(int i = 19; i>=0; i--)
if(dep[fa[a][i]] >= dep[b])
a = fa[a][i];
if(a == b) return a;
for(int i = 19; i>=0; i--)
if(fa[a][i] != fa[b][i])
a = fa[a][i], b = fa[b][i];
return fa[a][0];
}
int stDistance (int a, int b) {
int lca = stLCA(a, b);
return depl[a]+depl[b]-depl[lca]*2;
}
int stJump (int u, int dis) {
for(int i = 19; i>=0; i--)
if(dis >= (1<<i)) dis -= (1<<i), u = fa[u][i];
return u;
}
int stLast (int f, int u) {
int lca = stLCA(f, u);
if(dep[lca] < dep[f]) return fa[f][0];
else if(lca == f)
return stJump(u, dep[u]-dep[f]-1);
return 0;
}
}
int A[MAXN];
namespace DynamicDC {
int sz[MAXN], cur_sz;
int rpos, rvalue;
bool vis[MAXN];
int fa[MAXN];
int dfsSize (int u, int f) {
sz[u] = 1;
for(int e = inp.head[u]; e; e = inp[e].nxt)
if(!vis[inp[e].v] && inp[e].v != f)
sz[u] += dfsSize(inp[e].v, u);
return sz[u];
}
void dfsRoot (int u, int f) {
int cur_val = cur_sz-sz[u];
for(int e = inp.head[u]; e; e = inp[e].nxt)
if(inp[e].v != f && !vis[inp[e].v]) {
dfsRoot(inp[e].v, u);
cur_val = max(cur_val, sz[inp[e].v]);
}
if(cur_val <= rvalue) rpos = u, rvalue = cur_val;
}
int buffer[MAXN], btot;
int vdepth[MAXN], dlim;
void printToBuffer (int u, int f, int cur_dis) {
if(vdepth[u] <= dlim) return ;
buffer[++btot] = cur_dis-A[u];
for(int e = inp.head[u]; e; e = inp[e].nxt)
if(inp[e].v != f) printToBuffer(inp[e].v, u, cur_dis+inp[e].w);
}
int bsize[MAXN];
Treap::Root rt1[MAXN], rt2[MAXN];
int construct (int u, int f) {
dfsSize(u, f);
cur_sz = sz[u], rpos = u, rvalue = INF;
dfsRoot(u, f);
vdepth[u = rpos] = vdepth[f]+1;
vis[u] = true, bsize[u] = cur_sz;
fa[u] = f;
vector<pair<int, int> > vec;
for(int e = inp.head[u]; e; e = inp[e].nxt) {
if(vis[inp[e].v]) continue ;
pair<int, int> pr(construct(inp[e].v, u), e);
vec.push_back(pr);
}
btot = 0, dlim = vdepth[u];
for(int i = 0; i<(int)vec.size(); i++) {
int lpos = btot;
printToBuffer(inp[vec[i].second].v, 0, inp[vec[i].second].w);
rt2[vec[i].first].buildFrom(buffer+lpos, btot-lpos);
}
rt1[u].buildFrom(buffer, btot);
rt1[u].insert(-A[u]);
return u;
}
void clearStructure (int u, int f) {
vis[u] = false, vdepth[u] = 0;
for(int e = inp.head[u]; e; e = inp[e].nxt)
if(inp[e].v != f && vdepth[inp[e].v] >= dlim)
clearStructure(inp[e].v, u);
}
int dtot;
void rebuild (int u) {
int f = fa[u];
dlim = vdepth[u], clearStructure(u, 0);
u = construct(u, f);
fa[u] = f;
if(f) {
int pre = ST::stLast(f, u);
int cdist = abs(ST::depl[pre]-ST::depl[f]);
btot = 0, dlim = vdepth[f];
printToBuffer(pre, f, cdist);
rt2[u].buildFrom(buffer, btot);
}
}
LL current_answer = 0;
const float STRUCTRURE_STRENGH = 0.77;
inline bool isAcceptable (int a, int b)
{return (float)b/a < STRUCTRURE_STRENGH;}
void insert (int u, int dist, int val) {
int cur = ++dtot; A[cur] = val;
rt1[cur].insert(-A[cur]), bsize[cur] = 1;
vis[cur] = true, vdepth[cur] = vdepth[u]+1;
ST::stMaintain(u, cur, dist);
if(u) {
inp.addEdge(u, cur, dist), inp.addEdge(cur, u, dist);
fa[cur] = u, rt2[cur].insert(dist-A[cur]);
}
int tmp = dist;
while(u) {
bsize[u] ++;
current_answer += rt1[u].queryLEq(A[cur]-tmp);
rt1[u].insert(tmp-A[cur]);
if(fa[u]) {
current_answer -= rt2[u].queryLEq(A[cur]-(tmp = ST::stDistance(fa[u], cur)));
rt2[u].insert(tmp-A[cur]);
}
u = fa[u];
}
int ctarget = 0;
tmp = fa[cur];
while(tmp) {
if(!isAcceptable(bsize[tmp], bsize[cur]))
ctarget = tmp;
cur = tmp, tmp = fa[tmp];
}
if(ctarget) rebuild(ctarget);
}
inline LL answer () {return current_answer;}
}
inline int getInt () {
int ret; char ch; bool flg = false;
while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
ret = ch-'0';
while((ch = getchar()) >= '0' && ch <= '9')
ret = ret*10+(ch-'0');
return flg ? -ret : ret;
}
int main () {
srand(20010627);
getInt();
N = getInt();
LL last_ans = 0;
for(int i = 1; i<=N; i++) {
int a = getInt(), b = getInt(), c = getInt();
a = a^(last_ans%1000000000);
DynamicDC::insert(a, b, c);
printf("%lld\n", last_ans = DynamicDC::answer());
}
}
ALOEXT
题目大意:
给你一个序列, 要求支持以下操作:
1.插入元素。
2.删除元素。
3.修改元素。
4.询问区间[l, r]中的每个数a异或区间次大值的最大值。
强制在线。
解题报告
考虑到插入删除就不能可持久化Trie了。
动态的话考虑像树套树一样用数据结构X套上普通的Trie, 但是这里如果数据结构X发生结构变更, Trie的更新操作复杂度是线性的, 于是X就选取为替罪羊树。删除时惰性删除, 常数捉急, 注意适时回收内存。
一坨细节…最后不停RE百思不得其解回头把数组开大了三倍就AC了…
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cmath>
using namespace std;
const int MAXN = 100100;
const int TDEPTH = 19;
namespace Trie {
const int MAXD = MAXN*200;
struct Node {
int ch[2];
int sz;
} d[MAXD];
int dtot = 0;
int memstk[MAXD], stktop;
inline int newNode () {
int u;
if(stktop) {
u = memstk[stktop--];
memset(d+u, 0, sizeof d[0]);
} else u = ++dtot;
return u;
}
struct Root {
int root;
Root () {root = newNode();}
inline void releaseMemory (int u) {
if(!u) return ;
memstk[++stktop] = u;
releaseMemory(d[u].ch[0]);
releaseMemory(d[u].ch[1]);
}
inline void clear () {
releaseMemory(root);
root = newNode();
}
void insert (int val) {
int u = root;
d[u].sz ++;
for(int i = TDEPTH; i>=0; i--) {
bool f = val&(1<<i);
if(!d[u].ch[f]) d[u].ch[f] = newNode();
u = d[u].ch[f];
d[u].sz++;
}
}
void erase (int val) {
int u = root;
d[u].sz --;
for(int i = TDEPTH; i>=0; i--) {
bool f = val&(1<<i);
if(!(--d[d[u].ch[f]].sz)) {
releaseMemory(d[u].ch[f]);
d[u].ch[f] = 0;
return ;
} else u = d[u].ch[f];
}
}
int query (int val) {
int ret = 0;
int u = root;
for(int i = TDEPTH; i>=0; i--) {
bool f = !(val&(1<<i));
if(!d[u].ch[f]) {
u = d[u].ch[!f];
if(!f) ret |= (1<<i);
} else {
u = d[u].ch[f];
if(f) ret |= (1<<i);
}
}
return ret^val;
}
};
int size (int u) {return d[u].sz;}
}
namespace SGT { // Scapegoat Tree
const int MAXD = MAXN*10;
const float STRUCTRUE_STRENTH = 0.84;
struct Node {
int ch[2];
Trie::Root rt;
bool del;
int sz, val;
int mx1, mx2;
} d[MAXD];
int dtot, root;
int memstk[MAXD], stktop;
inline int newNode (int val) {
int u;
if(stktop) {
u = memstk[stktop--];
d[u].ch[0] = d[u].ch[1] = 0;
d[u].del = false;
} else u = ++dtot;
d[u].sz = 1;
d[u].mx1 = d[u].val = val;
d[u].mx2 = 0;
return u;
}
inline void pushin (int u, int val) {
if(val >= d[u].mx1) d[u].mx2 = d[u].mx1, d[u].mx1 = val;
else if(val > d[u].mx2) d[u].mx2 = val;
}
inline void updata (int u) {
d[u].mx1 = d[u].mx2 = -1;
if(!d[u].del) pushin(u, d[u].val);
pushin(u, d[d[u].ch[0]].mx1);
pushin(u, d[d[u].ch[0]].mx2);
pushin(u, d[d[u].ch[1]].mx1);
pushin(u, d[d[u].ch[1]].mx2);
}
int src[MAXN*2], stot;
void printSource (int u) { // 同时回收内存
if(!u) return ;
printSource(d[u].ch[0]);
if(!d[u].del) src[++stot] = d[u].val;
printSource(d[u].ch[1]);
d[u].rt.clear();
memstk[++stktop] = u;
}
int build (int lb, int rb) {
if(lb > rb) return 0;
int mid = (lb+rb)>>1;
int u = newNode(src[mid]);
d[u].sz = rb-lb+1;
for(int i = lb; i<=rb; i++)
d[u].rt.insert(src[i]);
if(lb == rb) {return u;}
d[u].ch[0] = build(lb, mid-1);
d[u].ch[1] = build(mid+1, rb);
updata(u);
return u;
}
void initialize (int * from, int len) {
d[0].mx1 = d[0].mx2 = d[0].val = -1;
root = newNode(-1);
int x = d[root].ch[1] = newNode(-1);
d[root].sz = len+2, d[x].sz = len+1;
for(int i = 1; i<=len; i++) src[i] = from[i];
d[x].ch[0] = build(1, len);
updata(x), updata(root);
}
void rebuild (int u, int f) {
//printf("rebuild At:%d\n", u);
//记得更新root! 和fa!
stot = 0;
printSource(u);
int cur = build(1, stot);
if(!f) root = cur;
else d[f].ch[d[f].ch[1] == u] = cur;
}
inline bool isAcceptable (int u) {
return !(((float)d[d[u].ch[0]].sz/d[u].sz > STRUCTRUE_STRENTH)
||((float)d[d[u].ch[1]].sz/d[u].sz > STRUCTRUE_STRENTH));
}
int temp[MAXD];
void insertAfter (int rk, int val) {
++ rk;
//printf("ins:%d, %d\n", rk, val);
int u = root, ttot = 0;
while(u) {
temp[++ttot] = u;
if(!d[u].del) d[u].rt.insert(val);
d[u].sz ++;
if(d[d[u].ch[0]].sz >= rk) u = d[u].ch[0];
else if(d[d[u].ch[0]].sz+(!d[u].del) == rk) break;
else rk -= d[d[u].ch[0]].sz+(!d[u].del), u = d[u].ch[1];
}
if(d[u].ch[1]) {
int suc = d[u].ch[1];
if(!d[suc].del) d[suc].rt.insert(val);
d[suc].sz ++, temp[++ttot] = suc;
while(d[suc].ch[0]) {
suc = d[suc].ch[0];
if(!d[suc].del) d[suc].rt.insert(val);
d[suc].sz ++, temp[++ttot] = suc;
}
d[d[suc].ch[0] = newNode(val)].rt.insert(val);
} else
d[d[u].ch[1] = newNode(val)].rt.insert(val);
int target = 0;
for(int i = 1; i<=ttot; i++) {
pushin(temp[i], val);
if(!target && !isAcceptable(temp[i]))
target = i;
}
if(target) rebuild(temp[target], temp[target-1]);
}
void modify (int rk, int val) {
++ rk;
int u = root, ttot = 0;
while(u) {
temp[++ttot] = u;
if(!d[u].del) d[u].rt.insert(val);
if(d[d[u].ch[0]].sz >= rk) u = d[u].ch[0];
else if(d[d[u].ch[0]].sz+(!d[u].del) == rk) break;
else rk -= d[d[u].ch[0]].sz+(!d[u].del), u = d[u].ch[1];
}
int eval = d[u].val; d[u].val = val;
for(int i = ttot; i; i--) {
if(!d[temp[i]].del) d[temp[i]].rt.erase(eval);
updata(temp[i]);
}
}
void erase (int rk) {
++ rk;
//printf("del:%d\n", rk);
int u = root, ttot = 0;
while(u) {
temp[++ttot] = u;
d[u].sz --;
if(d[d[u].ch[0]].sz >= rk) u = d[u].ch[0];
else if(d[d[u].ch[0]].sz+(!d[u].del) == rk) break;
else rk -= d[d[u].ch[0]].sz+(!d[u].del), u = d[u].ch[1];
}
d[u].del = true;
d[u].rt.clear(); // 直接clear, 简单粗暴解决一切QWQ
int target = 0;
for(int i = ttot; i>=1; i--) {
if(!d[temp[i]].del) d[temp[i]].rt.erase(d[u].val);
updata(temp[i]);
if(!isAcceptable(temp[i]))
target = i;
}
if(target) rebuild(temp[target], temp[target-1]);
}
int cur1, cur2;
inline void updValue (int val) {
if(val >= cur1) cur2 = cur1, cur1 = val;
else if(val > cur2) cur2 = val;
}
int ql, qr;
Trie::Root buffer[100]; int btot; // 记得忽略0!
int bufferSingle[100], bstot;
void getIntervals (int u, int lb, int rb) {
if(!u || qr < lb || ql > rb || lb > rb) return ;
//printf("at:(%d)[%d, %d]\n", u , lb, rb);
if(ql <= lb && rb <= qr && !d[u].del) { // 加上判断del...
buffer[++btot] = d[u].rt;
updValue(d[u].mx1), updValue(d[u].mx2);
return ;
}
int mid = lb+d[d[u].ch[0]].sz+(!d[u].del)-1;
if(!d[u].del) {
if(ql <= mid && mid <= qr) {
updValue(d[u].val);
bufferSingle[++bstot] = d[u].val;
}
}
getIntervals(d[u].ch[0], lb, mid-(!d[u].del));
getIntervals(d[u].ch[1], mid+1, rb);
}
int query (int l, int r) {
l++, r++;
//printf("qry:%d, %d\n", l, r);
btot = bstot = 0;
ql = l, qr = r, cur1 = cur2 = -1;
getIntervals(root, 1, d[root].sz);
int sec = cur2;
//printf("sec:%d\n", sec);
int ret = 0;
for(int i = 1; i<=bstot; i++)
ret = max(ret, bufferSingle[i]^sec);
for(int i = 1; i<=btot; i++)
ret = max(ret, buffer[i].query(sec));
return ret;
}
void print (int u) {
if(!u) return ;
print(d[u].ch[0]);
if(!d[u].del) printf("%d, ", d[u].val);
print(d[u].ch[1]);
}
void debug () {print(root);}
}
inline int getInt () {
int ret; char ch; bool flg = false;
while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
ret = ch-'0';
while((ch = getchar()) >= '0' && ch <= '9')
ret = ret*10+(ch-'0');
return ret;
}
//#define ONLINE_JUDGE
char ord[5];
int A[MAXN];
int main () {
int N = getInt(), M = getInt();
for(int i = 1; i<=N; i++) A[i] = getInt();
SGT::initialize(A, N);
int mask = (1<<20)-1, lastans = 0;
for(int i = 1; i<=M; i++) {
scanf("%s", ord);
if(ord[0] == 'I') {
int x = getInt(), y = getInt();
#ifdef ONLINE_JUDGE
x = (x+lastans)%N, y = (y+lastans)&mask;
#endif // ONLINE_JUDGE
SGT::insertAfter(x, y);
N ++;
} else if(ord[0] == 'D') {
int x = getInt();
#ifdef ONLINE_JUDGE
x = (x+lastans)%N;
#endif // ONLINE_JUDGE
SGT::erase(x+1);
N --;
} else if(ord[0] == 'C') {
int x = getInt(), y = getInt();
#ifdef ONLINE_JUDGE
x = (x+lastans)%N, y = (y+lastans)&mask;
#endif // ONLINE_JUDGE
SGT::modify(x+1, y);
} else {
int l = getInt(), r = getInt();
#ifdef ONLINE_JUDGE
l = (l+lastans)%N, r = (r+lastans)%N;
#endif // ONLINE_JUDGE
printf("%d\n", lastans = SGT::query(l+1, r+1));
//SGT::debug();
}
}
}
BZOJ 3065
题目大意: RT, 带插入区间K小值。
强制在线。
解题报告
替罪羊树套Trie, 询问时候把区间拉出来整体二分。
拉区间时可以把区间分解为正负进行容斥或者直接塞vector里暴力…(反正都是log级的)。
写这题时超级困…一开始wa了, 改着改着不知道怎么就AC了…可能原来二分有问题?好困啊懒得深究…
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <vector>
using namespace std;
const int DEPTH = 16;
const int MAXN = 70070*2;
namespace Trie {
const int MAXD = MAXN*120;
struct Node {
int ch[2];
int sz;
} d[MAXD];
int dtot;
int memstk[MAXD], stktop;
inline int newNode () {
int u;
if(stktop) {
u = memstk[stktop--];
d[u].ch[0] = d[u].ch[1] = 0;
d[u].sz = 0;
} else u = ++dtot;
return u;
}
struct Root {
int root;
Root () {root = newNode();}
inline void insert (int val) {
int u = root; d[u].sz ++;
for(int i = DEPTH; i>=0; i--) {
bool flg = val&(1<<i);
if(!d[u].ch[flg]) d[u].ch[flg] = newNode();
u = d[u].ch[flg];
d[u].sz ++;
}
}
inline void releaseMemory (int u) {
if(!u) return ;
releaseMemory(d[u].ch[0]);
releaseMemory(d[u].ch[1]);
memstk[++stktop] = u;
}
inline void clear () {
releaseMemory(root);
root = newNode();
}
inline void erase (int val) {
int u = root; d[u].sz --;
for(int i = DEPTH; i>=0; i--) {
bool flg = val&(1<<i);
d[d[u].ch[flg]].sz --;
if(!d[d[u].ch[flg]].sz) {
releaseMemory(d[u].ch[flg]);
d[u].ch[flg] = 0;
return ;
}
u = d[u].ch[flg];
}
}
} ;
inline int size (int u) {return d[u].sz;}
}
namespace SGT {
const int MAXD = MAXN*4;
struct Node {
int ch[2];
int val, sz;
Trie::Root rt;
} d[MAXD];
int root, dtot;
int memstk[MAXD], stktop;
inline int newNode (int val) {
int u;
if(stktop) {
u = memstk[stktop--];
d[u].ch[0] = d[u].ch[1] = 0;
d[u].rt.clear();
} else u = ++dtot;
d[u].val = val;
d[u].sz = 1;
return u;
}
inline void updata (int u) {
d[u].sz = d[d[u].ch[0]].sz+d[d[u].ch[1]].sz+1;
}
const float STRUCTURE_STRENGH = 0.76;
inline bool isnAcceptable (int u) {
return (float)d[d[u].ch[0]].sz/d[u].sz > STRUCTURE_STRENGH
|| (float)d[d[u].ch[1]].sz/d[u].sz > STRUCTURE_STRENGH;
}
int src[MAXN*2], *scur;
int build (int lb, int rb) {
if(lb > rb) return 0;
int mid = (lb+rb)>>1;
int u = newNode(src[mid]);
for(int i = lb; i<=rb; i++)
d[u].rt.insert(src[i]);
if(lb == rb) return u;
d[u].ch[0] = build(lb, mid-1);
d[u].ch[1] = build(mid+1, rb);
updata(u);
return u;
}
void initialize (int * isource, int len) {
root = newNode(-1);
int x = d[root].ch[1] = newNode(-1);
for(int i = 1; i<=len; i++) src[i] = isource[i];
d[x].ch[0] = build(1, len);
updata(x), updata(root);
}
void printSource (int u) { // 同时回收内存
if(!u) return ;
printSource(d[u].ch[0]);
*(++scur) = d[u].val;
printSource(d[u].ch[1]);
d[u].rt.clear();
memstk[++stktop] = u;
}
void rebuild (int u, int f) {
//printf("rebuild at:%d %d\n", u, f);
scur = src;
printSource(u);
int r = build(1, scur-src);
if(f) d[f].ch[d[f].ch[1] == u] = r;
else root = r;
}
int trace[MAXD], ttot;
void insert (int rk, int val) {
int u = root;
rk ++, ttot = 0;
while(u) {
trace[++ttot] = u;
d[u].rt.insert(val);
d[u].sz ++;
if(d[d[u].ch[0]].sz >= rk) u = d[u].ch[0];
else if(d[d[u].ch[0]].sz+1 == rk) break;
else rk -= d[d[u].ch[0]].sz+1, u = d[u].ch[1];
}
if(!d[u].ch[0]) d[d[u].ch[0] = newNode(val)].rt.insert(val);
else {
u = d[u].ch[0];
d[u].sz ++, trace[++ttot] = u;
d[u].rt.insert(val);
while(d[u].ch[1]) {
u = d[u].ch[1];
d[u].sz ++, trace[++ttot] = u;
d[u].rt.insert(val);
}
d[d[u].ch[1] = newNode(val)].rt.insert(val);
}
for(int i = 1; i<=ttot; i++)
if(isnAcceptable(trace[i]))
{rebuild(trace[i], trace[i-1]); break ;}
}
void modify (int rk, int val) {
int u = root;
ttot = 0, rk ++;
while(u) {
trace[++ttot] = u;
d[u].rt.insert(val);
if(d[d[u].ch[0]].sz >= rk) u = d[u].ch[0];
else if(d[d[u].ch[0]].sz+1 == rk) break;
else rk -= d[d[u].ch[0]].sz+1, u = d[u].ch[1];
}
int x = d[u].val;
d[u].val = val;
for(int i = 1; i<=ttot; i++)
d[trace[i]].rt.erase(x);
}
int buffer[200], btot;
vector<int> bufferSingle;
int ql, qr;
void getIntervals (int u, int lb, int rb) {
if(!u || lb > qr || rb < ql || lb > rb) return ;
//printf("at:[%d](%d, %d)\n", u, lb, rb);
if(ql <= lb && rb <= qr) {buffer[++btot] = d[u].rt.root; return ;}
int mid = lb+d[d[u].ch[0]].sz;
if(ql <= mid && mid <= qr) bufferSingle.push_back(d[u].val);
getIntervals(d[u].ch[0], lb, mid-1);
getIntervals(d[u].ch[1], mid+1, rb);
}
int queryKth (int l, int r, int k) {
l ++, r ++;
ql = l, qr = r;
bufferSingle.clear(), btot = 0;
getIntervals(root, 1, d[root].sz);
sort(bufferSingle.begin(), bufferSingle.end());
int cur = 0;
for(int cdep = DEPTH; cdep >= 0; cdep --) {
int sum0 = 0;
for(int i = 1; i<=btot; i++)
sum0 += Trie::size(Trie::d[buffer[i]].ch[0]);
int x;
for(x = 0; x<bufferSingle.size(); x++)
if(bufferSingle[x]&(1<<cdep)) break;
else sum0++;
if(sum0 >= k) {
bufferSingle.erase(bufferSingle.begin()+x, bufferSingle.end());
for(int i = 1; i<=btot; i++)
buffer[i] = Trie::d[buffer[i]].ch[0];
} else {
bufferSingle.erase(bufferSingle.begin(), bufferSingle.begin()+x);
for(int i = 1; i<=btot; i++)
buffer[i] = Trie::d[buffer[i]].ch[1];
k -= sum0;
cur += 1<<cdep;
}
//printf("bsl, bsr:%d, %d\n", bsl, bsr);
}
return cur;
}
}
inline int getInt () {
int ret; char ch; bool flg = false;
while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
ret = ch-'0';
while((ch = getchar()) >= '0' && ch <= '9')
ret = ret*10+(ch-'0');
return flg ? -ret : ret;
}
int A[MAXN];
int main () {
int N = getInt();
for(int i = 1; i<=N; i++) A[i] = getInt();
int Q = getInt();
char buf[30];
int last_ans = 0;
SGT::initialize(A, N);
while(Q --) {
scanf("%s", buf);
int a, b;
if(buf[0] == 'Q') {
a = getInt()^last_ans, b = getInt()^last_ans;
printf("%d\n", last_ans = SGT::queryKth(a, b, getInt()^last_ans));
} else if(buf[0] == 'I') {
a = getInt()^last_ans;
SGT::insert(a, getInt()^last_ans);
} else if(buf[0] == 'M') {
a = getInt()^last_ans;
SGT::modify(a, getInt()^last_ans);
}
}
}
/*
10
10 5 8 28 0 19 2 31 1 22
30
I 6 9
M 1 11
I 8 17
M 1 31
M 6 26
Q 2 7 6
I 23 30
M 31 7
I 22 27
M 26 18
Q 26 17 31
I 5 2
I 18 13
Q 3 3 3
I 27 19
Q 23 23 30
Q 5 13 5
I 3 0
M 15 27
Q 0 28 13
Q 3 29 11
M 2 8
Q 12 5 7
I 30 19
M 11 19
Q 17 8 29
M 29 4
Q 3 0 12
I 7 18
M 29 27
*/
Join the discussion