BZOJ 3261 最大异或和

Link

模板题了 # Code 各种卡终于卡到了RANK1。。感觉自己好闲好zz。。

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
//Code by Lucida
#include<bits/stdc++.h>
//#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
namespace IO
{
#ifndef get
const int IN=1e7;
char inbuf[IN],*iptr=inbuf,*iend=inbuf;
#define getc() ((iptr==iend && (iend=(iptr=inbuf)+fread(inbuf,1,IN,stdin),iptr==iend))?EOF:*iptr++)
inline void get(int &x)
{
static int f;static char ch;
f=1;while(!isdigit(ch=getc())) if(ch=='-') f=-1;
x=ch-'0';while(isdigit(ch=getc())) (x*=10)+=ch-'0';
x*=f;
}
#endif
const int OUT=1e7;
char outbuf[OUT],*optr=outbuf,*oend=outbuf+OUT-1;
#define flush() (fwrite(outbuf,1,optr-outbuf,stdout))
#define putc(x) ((optr==oend)?flush(),optr=outbuf,*optr++=x:*optr++=x)
inline void put(int x)
{
if(x<0) putc('-');
if(!x) putc('0');
if(x)
{
static char stack[100];int top;
for(top=0;x;x/=10)
stack[++top]=(x%10)+'0';
while(top) putc(stack[top--]);
}
putc('\n');
}
}using namespace IO;
const int MAXN=400000+10;
namespace iTrie
{
const int LEN=24,SIZE=LEN*MAXN<<1;
struct Node
{
Node *son[2];
int cnt;
Node(){son[0]=son[1]=0;cnt=0;}
}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL,*null=new(ME++) Node,*root[MAXN<<1]={null};
int sum[MAXN<<1],rc;
Node *newNode()
{
static Node *cur;cur=ME++;
cur->son[0]=cur->son[1]=null;cur->cnt=0;
return cur;
}
Node *newNode(Node *old)
{
static Node *cur;cur=new(ME++) Node;*cur=*old;
return cur;
}
void Insert(Node *&pos,int x)
{
pos=newNode(pos);Node *cur=pos;
for(int c,i=LEN-1;~i;i--)
{
c=(x>>i)&1;cur->cnt++;
cur->son[c]=newNode(cur->son[c]);
cur=cur->son[c];
}
cur->cnt++;
}
void Add(int x)
{
++rc;sum[rc]=sum[rc-1]^x;
Insert(root[rc]=root[rc-1],sum[rc]);
}
int cnxt(Node *pl,Node *pr,int c){return pr->son[c]-pl->son[c];}
int Query(int x,int l,int r)
{
int res=x;Node *pl=root[l],*pr=root[r+1];
for(int c,i=LEN-1;~i;i--)
{
c=(x>>i)&1;
if(cnxt(pl,pr,c^1))
{
pl=pl->son[c^1],pr=pr->son[c^1];
res|=(1<<i);
}
else
{
pl=pl->son[c],pr=pr->son[c];
res&=~(1<<i);
}
}
return res;
}
}using namespace iTrie;
int main()
{
null->son[0]=null->son[1]=null;
Add(0);
int n,m;get(n),get(m);
for(int i=1;i<=n;i++)
{
int x;get(x);
Add(x);
}
for(int i=1;i<=m;i++)
{
char opt;int l,r,x;
while(!isalpha(opt=getc()));
if(opt=='A')
{
get(x);
Add(x);
}
else
{
get(l),get(r),get(x);
//printf("%d\n",Query(x^sum[rc],l-1,r-1));
put(Query(x^sum[rc],l-1,r-1));
}
}
flush();
return 0;
}
/* AC Record(Bugs) *
*
* * * * * * * * * */

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利