題面
Description
taorunz平時最喜歡的東西就是可移動存儲器了……隻要看到别人的可移動存儲器，他總是用盡一切辦法把它裡面的東西弄到手。
突然有一天，taorunz來到了一個密室，裡面放着一排可移動存儲器，存儲器裡有非常珍貴的OI資料……不過比較特殊的是，每個存儲器上都寫着一個非負整數。taorunz很高興，要把所有的存儲器都拿走（taorunz的智商高達500，他一旦弄走了這裡的所有存儲器，在不久到來的AHOI和NOI中……你懂的）。不過這時有一個聲音傳來：“你隻能拿走這裡的一個存儲器，而且還不能直接拿，你需要指定一段區間[l, r]，滿足l<r，然後在第l個和第r個存儲器之間選一個拿走，你能獲得的知識增加量等于區間[l,r]中所有存儲器上寫的整數的次大值與你拿走的這個存儲器上寫的整數作按位異或運算的結果。”
問題是，這裡的可移動存儲器數量太多，而且，它們還在不斷地發生變化，有時候天上會掉下來一個新的存儲器，并插入到這一排存儲器中，有時候某個存儲器會不明原因消失，有時候某個存儲器上寫的整數變化了。taorunz雖然智商很高，但也無法應對如此快的變化，他指定了許多段區間，讓你幫他找出如果在這個區間中拿走存儲器，他能獲得的最多的知識是多少。
Input
第一行兩個整數N、M，表示一開始的存儲器數和後面發生的事件數。
第二行N個非負整數，表示一開始從左到右每個存儲器上寫的數字。注意，存儲器從0開始編号，也就是最左邊的存儲器是第0個。
接下來M行，每行描述一個事件，有4種可能的事件。
（1）I x y：表示天上掉下來一個寫着數字y的存儲器，并插入到原來的第x個存儲器之前，如果x等于原來存儲器的個數，則插入到末尾；
（2）D x：表示第x個存儲器消失；
（3）C x y：表示第x個存儲器上寫的數字變為y；
（4）F l r：表示taorunz指定區間[l,r]，讓你告訴他最多能獲得多少知識。
注意，本題強制線上，也就是事件中出現的所有數字都進行了加密，數字s表示的真實值是
對于I、D、C事件中的x及F事件中的l、r：(s+last_ans) mod n0；
對于I、C事件中的y：(s+last_ans) mod 1048576。
其中n0為目前存儲器個數，last_ans為上一個F事件的結果，如果前面尚未發生F事件，則last_ans=0。
Output
對于每個F事件，輸出結果。
Sample Input
5 10
2 6 3 8 7
F 1 4
I 2 1048565
I 0 1048566
D 3
F 3 0
I 3 1048569
D 5
C 1 1048570
F 1 2
F 2 1
Sample Output
15
7
4
7
HINT
1<=N, M<=100000。所有F事件滿足l<r。
本題共有5組資料，除1組為随機資料外，其它資料均為人工構造。
題目大意
帶插入, 删除, 修改, 求區間的次大值 異或 區間内一個數 的值的最大值.
題解
替罪羊樹套trie.
代碼懶的寫了. 敲了一點僞代碼, 将就這看吧.
#include <cstdio>
#include <cctype>
#include <vector>
const double ALPH = 0.75;
struct trieTree
{
struct node
{
node* suc[2];
};
node *rt;
inline trieTree
{
rt = NULL;
}
node* modify(node*, int, int);
inline void insert(int);
inline void Delete(int);
};
std::vector<int> cpy;
struct scapegoatTree
{
struct node
{
int ext, del, w;
node* suc[2];
inline node()
{
ext = del = 0;
rec = new trieTree;
suc[0] = suc[1] = NULL;
}
};
int flg;
node* build(int, int);
void DFS(node*);
inline void rebuild(node*);
inline int check(node*);
node* insert(node*, int, int);
inline void insert(int);
node* Delete(node*, int);
inline void Delete(int);
std::vector<trieTree::node*> nd, _nd;
inline int query(int L, int R, int x);
}
int main()
{}