Problem I: qwb VS 去污棒

Time Limit: 2 Sec Memory Limit: 256 MB

Submit: 95 Solved: 36

[Submit][Status][Web Board]

Description

qwb表白学姐失败后，郁郁寡欢，整天坐在太阳底下赏月。在外人看来，他每天自言自语，其实他在和自己的影子“去污棒”聊天。

去污棒和qwb互相出题考验对方，去污棒问了qwb这样一个问题：

现已知一个有n个正整数的序列a[1],a[2]…a[n],接下来有m个操作

操作一共有两种：

1.在序列末尾添加一个数x。

2.查询suf[p] xor x的最大值，其中xor是异或 ,l<=p<=r，

suf[t]表示从t开始的后缀的异或和，即suf[t]=a[t] xor a[t+1] xor …xor a[len]，len为序列长度。

Input

第一行一个整数T(<=5)，表示一共有T组数据。

每组数据第一行两个整数n(<=200000),m(<=200000)，意义如上所述。

随后一行有n个数，表示初始序列。

随后m行，每行表示一个操作。

操作有两种，1： x 表示在末尾添加一个x，2： l r x表示查询suf[p] xor x的最大值，其中l<= p <= r，

所有数及x不超过224 且保证所有操作合法。

Output

每组测试数据的第一行输出”Case x:”，x为数据组数的标号，从1开始。

接下来，对每个操作2输出一行答案。

Sample Input

1

5 5

1 2 3 4 5

2 1 3 4

1 10

1 7

2 4 4 5

2 1 5 19

Sample Output

Case 1:

6

9

31

HINT

这种涉及到可持续的增添元素而且频繁的求最值的，用离线会比较方便。然后如果学过trie树来处理数的异或的话，会知道，数的异或最大值，只要往异或的相反方向走就好。

对于这种持续删减修改，明显是可持续结构，可以保留上一个边界的值。

每个结点保存的是一个后缀和 然后利用 x^(y^k)=(x^y)^k 来得到结果。 x指的是 p[i].x y指的是后缀和。但是对于后面的操作1（在末尾增加元素），后缀和也加了进去，所以需要用异或删掉 这个是k。

可持续化就是有这么一个优点，你能得到所有的区间变化的情况。

而且从中选出最优的

还是太难，即使明白原理也不想不到。

#include 
     
      using namespace std;const int N=400010;struct Trie{    int nxt[2];    int cnt;};Trie L[N*27];int tot,root[N];int suf[N],arr[N];int Ans[N];int n,m;struct node{    int ops;    int l,r,x;}p[N];void init(){    memset(L,0,sizeof(L));    tot=0;}void update(int &cur,int ori,int step,int n,int v){    cur=tot++;    L[cur]=L[ori];    L[cur].cnt+=v;    if(step<0) return ;    int t=(n>>step)&1;    update(L[cur].nxt[t],L[ori].nxt[t],step-1,n,v);}int Find(int S,int E,int step,int n){    if(step<0) return 0;    int t=(n>>step)&1;    if(L[L[E].nxt[t^1]].cnt-L[L[S].nxt[t^1]].cnt>0)    {        return (1<
      
       =1;i--)        {            suf[i]=suf[i+1]^arr[i];            update(root[i],root[i+1],25,suf[i],1);        }        int last=0;        int sz=0;        printf("Case %d:\n", cc);        for(int i=m;i>=1;i--)        {            if(p[i].ops==1)            {                last^=p[i].x;            }            else            {                int one=last^p[i].x;                Ans[++sz]=Find(root[p[i].r+1],root[p[i].l],25,one);//可以得到 l到r 的所有后缀和异或值 情况。然后从中选出                 //异或one的 最大情况            }        }        for(int i=sz;i>=1;i--)        {            printf("%d\n",Ans[i]);        }    }}