BZOJ 3065 帶插入區間K小值 替罪羊樹套線段樹

BZOJ 3065 帶插入區間K小值 替罪羊樹套線段樹

題目大意：帶插入，單點修改的區間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);
}
 
bool Check(ScapeTree *a)
{
    if(a->son[0] != NULL)
        if((double)a->son[0]->size / a->size > alpha)
            return false;
    if(a->son[1] != NULL)
        if((double)a->son[1]->size / a->size > alpha)
            return false;
    return true;
}
 
ScapeTree *will_rebuild;
 
void Insert(ScapeTree *&a,int k,int val)
{
    if(a == NULL) {
        SegTree *root = new SegTree();
        root->Insert(0,RANGE,val);
        a = new (val,NULL,NULL,root,1)ScapeTree;
        return ;
    }
    a->root->Insert(0,RANGE,val);
    int temp = SIZE(a->son[0]);
    if(k <= temp)	Insert(a->son[0],k,val);
	else	Insert(a->son[1],k - temp - 1,val);
	a->Maintain();
	
    if(!Check(a))   will_rebuild = a;
}
 
void Modify(ScapeTree *a,int k,int val)
{
    static int old;
    if(k <= SIZE(a->son[0]))
        Modify(a->son[0],k,val);
    else if((k -= SIZE(a->son[0])) == 1) {
        old = a->val;
    	a->val = val;
	}
    else
        Modify(a->son[1],k - 1,val);
    a->root->Delete(0,RANGE,old);
    a->root->Insert(0,RANGE,val);
}
 
inline int Judge(int l,int r,int ans)
{
    return root->Ask(r,ans) - root->Ask(l - 1,ans);
}
 
inline int Query(int x,int y,int k)
{
    int l = 0,r = RANGE,re = -1;
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(Judge(x,y,mid) >= k)  
            r = mid - 1,re = mid;
        else    l = mid + 1;
    }
    return re;
}

char c[10];
 
int main()
{
    cin >> cnt;
    for(int i = 1; i <= cnt; ++i)
        scanf("%d",&src[i]);
    root = BuildScapeTree(1,cnt,src);
    cin >> asks;
    int last_ans = 0;
    for(int x,y,z,i = 1; i <= asks; ++i) {
        scanf("%s%d%d",c,&x,&y);
        x ^= last_ans;
        y ^= last_ans;
        if(c[0] == 'Q') {
            scanf("%d",&z);
            z ^= last_ans;
            printf("%d\n",last_ans = Query(x,y,z));
        }
        else if(c[0] == 'M')
            Modify(root,x,y);
        else {
            will_rebuild = NULL;
            Insert(root,x - 1,y);
            if(will_rebuild != NULL)
                Rebuild(will_rebuild);
        }
    }
    return 0;
}