BZOJ 3217 ALOEXT

题面

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

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()
{}