题目大意：带插入，单点修改的区间k小值在线查询。
?
思路：本年度做过最酸爽的题。
树套树的本质是一个外层不会动的树来套一个内层会动（或不会动）的树。两个树的时间复杂度相乘也就是差不多O(nlog^2n)左右。但是众所周知，高级数据结构经常会伴有庞大的常数，所以一般来说树套树的常数也不会小到哪去。所以在做这种题的时候先不要考虑常数的问题。。。
为什么要用替罪羊树呢？因为一般的平衡树都是会动的，这就很难办了。外层的树动了之后，内层的树肯定也是会动的。很显然，一般的二叉平衡树会经常会旋转，这样在动外层的树那么时间复杂度就会飞起。所以就需要一种不会动（或很少动）的二叉平衡树来做外层的树。
这样的树有两种：朝鲜树和替罪羊树。其中朝鲜树的时间复杂度是大概O(√n)的，而替罪羊树是O(logn)的。为什么朝鲜树的均摊时间是O(√n)呢，因为朝鲜树的思想是当树的高度超过√n是就暴力重建整棵树。所以所有操作的均摊时间就是O(√n)。
替罪羊树相对来说就比较优越一些了。一般来说替罪羊树很少直接暴力重建整棵树。在每次向替罪羊树中插入东西的时候，就查看经过的节点中有没有子树的size太大的节点，如果有的话就直接重建一个子树，保证了树的高度是logn左右，均摊时间复杂度也就减下来了。
重建一棵子树也十分简单，把这个子树的中序遍历记录下来，然后让它变得平衡就行了。然后要记得经过的所有节点都要回收内存，~不然内存会飞起~，用一个厉害一点的垃圾收集器，内存池也别静态开了，没敢，直接全都动态。当然，外层替罪羊树的内存回收了，内层的线段树的内存也要回收，~不然内存会飞起~。
这个题的查询过程时间复杂度O(nlong^3n)，其余操作均摊O(nlong^2n)。推荐你们去看看vfk的代码，简直dio……
?
CODE：
?
#include#include #include #include #include #define MAX 70010 #define RANGE 70010 using namespace std; #define SIZE(a) ((a) == NULL ? 0:(a)->size) const double alpha = 0.8; const int L = 1 << 15; int cnt,src[MAX],asks; struct SegTree{ static queue bin; SegTree *son[2]; int cnt; void *operator new(size_t,int _ = 0,SegTree *__ = NULL,SegTree *___ = NULL) { static SegTree *mempool,*C; SegTree *re; if(!bin.empty()) { re = bin.front(); bin.pop(); } else { if(C == mempool) C = new SegTree[L],mempool = C + L; re = C++; } re->cnt = _; re->son[0] = __,re->son[1] = ___; return re; } void operator delete(void *r) { bin.push(static_cast (r)); } void Insert(int l,int r,int x) { ++cnt; if(l == r) return ; int mid = (l + r) >> 1; if(x <= mid) { if(son[0] == NULL) son[0] = new SegTree(); son[0]->Insert(l,mid,x); } else { if(son[1] == NULL) son[1] = new SegTree(); son[1]->Insert(mid + 1,r,x); } } void Delete(int l,int r,int x) { --cnt; if(l == r) return ; int mid = (l + r) >> 1; if(x <= mid) son[0]->Delete(l,mid,x); else son[1]->Delete(mid + 1,r,x); } void Decomposition() { if(son[0] != NULL) son[0]->Decomposition(); if(son[1] != NULL) son[1]->Decomposition(); delete this; } int Ask(int l,int r,int x) { if(this == NULL) return 0; if(l == r) return cnt; int mid = (l + r) >> 1; if(x <= mid) return son[0]->Ask(l,mid,x); return (son[0] ? son[0]->cnt:0) + son[1]->Ask(mid + 1,r,x); } }; struct ScapeTree{ static queue bin; ScapeTree *son[2]; SegTree *root; int val,size; void *operator new(size_t,int _,ScapeTree *__,ScapeTree *___,SegTree *____,int _size) { static ScapeTree *mempool,*C; ScapeTree *re; if(!bin.empty()) { re = bin.front(); bin.pop(); } else { if(C == mempool) C = new ScapeTree[L],mempool = C + L; re = C++; } re->val = _; re->son[0] = __,re->son[1] = ___; re->root = ____; re->size = _size; return re; } void operator delete(void *r) { bin.push(static_cast (r)); } void Maintain() { size = 1; if(son[0] != NULL) size += son[0]->size; if(son[1] != NULL) size += son[1]->size; } int Ask(int k,int _val) { if(!k) return 0; if(SIZE(son[0]) >= k) return son[0]->Ask(k,_val); k -= SIZE(son[0]); int re = (son[0] ? son[0]->root->Ask(0,RANGE,_val):0) + (val <= _val); if(k == 1) return re; return son[1]->Ask(k - 1,_val) + re; } }*root; queue ScapeTree :: bin; queue SegTree :: bin; ScapeTree *BuildScapeTree(int l,int r,int arr[]) { if(l > r) return NULL; int mid = (l + r) >> 1; SegTree *root = new (0,NULL,NULL)SegTree; for(int i = l; i <= r; ++i) root->Insert(0,RANGE,arr[i]); ScapeTree *re = new (arr[mid],BuildScapeTree(l,mid - 1,arr),BuildScapeTree(mid + 1,r,arr),root,r - l + 1)ScapeTree; return re; } int temp[MAX],top; void DFS(ScapeTree *a) { if(a == NULL) return ; DFS(a->son[0]); temp[++top] = a->val; DFS(a->son[1]); a->root->Decomposition(); delete a; } void Rebuild(ScapeTree *&a) { top = 0; DFS(a); a = BuildScapeTree(1,top,temp); }