无聊来写了下
一开始发现树高是O(n)的，然后就MLE了，进去看了下发现没有重构！
看了半天发现调用错了函数
然后进去又发现不满足sz = ch[0]->sz + ch[1]->sz + 1
然而全都是maintain过的啊
发现后来受某个代码的影响
返回重建节点时把引用去掉了
这样这个点的父亲的信息就不对了
又仔细去看了一下那个人为什么这样做没问题
结果他每次都把内存回收了，而且重建的根节点是最后删除第一个拿出来的（然后他竟然用的队列，当我什么都没说，我还是不知道为什么是对的。。）
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
//#include<cassert> using namespace std; #define ALL_VALUE 0, 70000
const int N = + ; int CNT1 = , CNT2 = ; namespace ST {
struct Node *stk[N * ]; int top;
struct Node {
int sz;
Node* ch[]; Node() {}
Node(int sz) : sz(sz) {
ch[] = ch[] = ;
} void *operator new (size_t) {
// if(!++CNT1 % 100000) cerr << CNT1 << endl;
if(top) return stk[top--];
static Node *pis;
static int left = ;
if(!left) left = N, pis = new Node[N] ();
return left--, pis++;
} void operator delete(void *p) {
// ++CNT2;
stk[++top] = (Node*) p;
}
}; #define mid ((l + r) >> 1)
#define ls o->ch[0], l, mid
#define rs o->ch[1], mid + 1, r void insert(Node*& o, int l, int r, int v, int d) {
if(!o) o = new Node();
o->sz += d;
if(l == r) return;
if(v <= mid) insert(ls, v, d);
else insert(rs, v, d);
if(!o->sz) delete o, o = ;
} int query(Node* o, int l, int r, int v) {// <=v µÄÊýµÄ¸öÊý
if(!o) return ;
if(r <= v) return o->sz;
return query(ls, v) + (v > mid ? query(rs, v) : );
} void remove(Node*& o) {
if(!o) return;
remove(o->ch[]);
remove(o->ch[]);
delete o, o = ;
} #undef mid
#undef ls
#undef rs
} int a[N], dep = ; namespace SGT {
struct Node *pis;
struct Node {
int sz, v; Node *ch[];
ST::Node *da; int cmp(int k) const {
int s = ch[]->size() + ;
if(s == k) return -;
return k < s ? : ;
} Node(int v = ) : v(v) {
ch[] = ch[] = ;
da = ;
sz = ;
} int size() const {
return this ? sz : ;
} void maintain() {
sz = ch[]->size() + ch[]->size() + ;
} int query(int k, int v) const {//²éѯ1-kÀï <= vµÄÊýµÄÊýÁ¿
if(!this || !k) return ;
// cerr << ch[0]->size() << endl;
if(ch[]->size() >= k) return ch[]->query(k, v);
return (ch[] ? ST::query(ch[]->da, ALL_VALUE, v) : ) + (this->v <= v) + ch[]->query(k - ch[]->size() - , v);
} void *operator new(size_t) {
return pis++;
}
}*null, *root, pool[N]; Node *rec[N]; int tot; void print(Node *o) {
if(!o) return;
print(o->ch[]);
ST::remove(o->da);
rec[++tot] = o;
print(o->ch[]);
} /*void check(Node *o) {
if(!o) return;
assert(o->sz == o->ch[0]->size() + o->ch[1]->size() + 1);
check(o->ch[0]);
check(o->ch[1]);
}*/ void rebuild(Node*& o, int l, int r) {
if(l > r) return o = , void();
int mid = (l + r) >> ;
o = rec[mid];
for(int i = l; i <= r; i++) ST::insert(o->da, ALL_VALUE, rec[i]->v, );
rebuild(o->ch[], l, mid - );
rebuild(o->ch[], mid + , r);
o->maintain();
// assert(o->sz == o->ch[0]->size() + o->ch[1]->size() + 1);
} void build(Node*& o, int l, int r) {
if(l > r) return;
int mid = (l + r) >> ;
o = new Node(a[mid]);
for(int i = l; i <= r; i++) ST::insert(o->da, ALL_VALUE, a[i], );
build(o->ch[], l, mid - );
build(o->ch[], mid + , r);
o->maintain();
} Node*& insert(Node*& o, int k, int x) { // ÔÚµÚx¸öλÖúó²åÈëx
if(!o) {
o = new Node(x);
ST::insert(o->da, ALL_VALUE, x, );
return null;
}
// assert(o->sz == o->ch[0]->size() + o->ch[1]->size() + 1);
int d = o->ch[]->size() >= k ? : ;
if(d == ) k -= o->ch[]->size() + ;
Node*& res = insert(o->ch[d], k, x);
o->maintain();
ST::insert(o->da, ALL_VALUE, x, );
if(o->ch[d]->size() > o->size() * 0.75) return o;
else return res;
// assert(o->sz == o->ch[0]->size() + o->ch[1]->size() + 1);
} int modify(Node*& o, int k, int x) {
// assert(o->sz == o->ch[0]->size() + o->ch[1]->size() + 1);
int d = o->cmp(k), old;
if(d == ) k -= o->ch[]->size() + ;
if(d == -) old = o->v, o->v = x;
else old = modify(o->ch[d], k, x);
ST::insert(o->da, ALL_VALUE, old, -);
ST::insert(o->da, ALL_VALUE, x, );
return old;
} void insert(int k, int x) {
// SGT::check(SGT::root);
Node*& res = insert(root, k, x);
// SGT::check(SGT::root);
if(res != null) {
tot = ;
print(res);
rebuild(res, , tot);
// SGT::check(SGT::root);
}
}
} int query(int l, int r, int k) {
int L = , R = , res = -;
while(L <= R) {
int mid = (L + R) >> ;
int t1 = SGT::root->query(r, mid);
int t2 = SGT::root->query(l - , mid);
if(t1 - t2 >= k) R = mid - , res = mid;
else L = mid + ;
}
return res;
} int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif SGT::pis = SGT::pool; int x, n, m;
scanf("%d", &n); for(int i = ; i <= n; i++) {
scanf("%d", a + i);
} int la = ; SGT::build(SGT::root, , n); scanf("%d", &m);
char opt[]; int y, k, v; for(int i = ; i <= m; i++) {
// if(i == 2859)
// int debug = 1;
// SGT::check(SGT::root); scanf("%s", opt);
if(opt[] == 'Q') {
scanf("%d%d%d", &x, &y, &k);
x ^= la, y ^= la, k ^= la;
printf("%d\n", query(x, y, k));
}else if(opt[] == 'M') {
scanf("%d%d", &x, &v);
x ^= la, v ^= la;
SGT::modify(SGT::root, x, v);
}else {
scanf("%d%d", &x, &v);
x ^= la, v ^= la;
// int last = CNT1; dep = 0;
SGT::insert(x - , v);
// cerr << SGT::root->sz << endl;
// cerr << CNT1 - last << ' ' << dep << endl;
}
} return ;
}