[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 I: qwb VS 去污棒 [可持久化01字典树]【数据结构】

2017-06-03 02:41:12 Tabris_ 阅读数：969

博客爬取于2020-06-14 22:40:14
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72849787

题目链接：http://115.231.222.240:8081/JudgeOnline/problem.php?cid=1005&pid=8
——————————————————————————————————————————
Problem I: qwb VS 去污棒
Time Limit: 2 Sec Memory Limit: 256 MB
Submit: 74 Solved: 26
[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
——————————————————————————————————————————

以下是边做题时边写的

可持久化Trie 离线，维护后缀异或和 然后在区间上进行查找
其实通过消去率能将suffix变成前缀，不对么

yes

假如序列长度为 n

那么prexor[n]^prexor[k] = suf[k+1]; 所以在线就好了；

可持久化01字典树，那就用一个可持久化线段树来实现，怎么搞呢。

算了还是先改了别人的吧。。。

异或最大值就想到了01trie

但是限制区间所以要可持久化

可持久化01字典树可以借鉴主席树来写,

但是我这个最后被卡常了,加了读入挂才AC

附本题代码
——————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

# define abs(x) (((x)>0)?(x):-(x))

const int N = 400000+10;
const int MOD  = 1e8;

int read(){
    int x=0;char ch = getchar();
    while('0'>ch||ch>'9')ch=getchar();
    while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x;
}

/**********************************/

int trie[N*40][2],sz[N*40],rt[N];
int n,m,cnt,sum;
char s[10];

int update(int pre,int i,int x){
    int now=++cnt;
    if(0==i){
        trie[now][0]=trie[now][1]=0;
        sz[now]=sz[pre]+1;
        return now;
    }
    int bt=((x>>(i-1))&1);
    trie[now][1-bt]=trie[pre][1-bt];
    trie[now][bt]=update(trie[pre][bt],i-1,x);
    sz[now]=sz[trie[now][0]]+sz[trie[now][1]];
    return now;
}

int query(int rt1,int rt2,int i,int x){
    if (i==0) return 0;
    int bt=((x>>(i-1))&1);
    if (sz[trie[rt2][1-bt]]-sz[trie[rt1][1-bt]])
        return (1<<(i-1))+query(trie[rt1][1-bt],trie[rt2][1-bt],i-1,x);
    else
        return query(trie[rt1][bt],trie[rt2][bt],i-1,x);
}

int main(){
    int _=read(),kcase=0;
    while(_--){
        n=read(),m=read();
        rt[0]=trie[0][0]=trie[0][1]=sz[0]=sum=0;
        rt[0]=update(rt[0],25,0);
        for (int i=1;i<=n;i++){
            sum^=read();
            rt[i]=update(rt[i-1],25,sum);
        }

        printf("Case %d:\n",++kcase);
        while (m--){
            int l,r;
            scanf("%s",s+1);
            if (s[1]=='1'){
                sum^=read();
                n++;rt[n]=update(rt[n-1],25,sum);
            }
            else{
                l=read()-1,r=read()-1;
                printf("%d\n",query(rt[l-1],rt[r],25,sum^read()));
            }
        }
    }
    return 0;
}