题解 P4735 【最大异或和】
HomuraCat
2018-11-16 22:06:37
可持久化Trie板子题
如果你会主席树的话,我有自信几句话就讲清楚这个算法
如果你不会的话,还是去学学主席树吧。
你肯定是会01trie的,但是01trie加进去就无序了,想想主席树,我们可以将每一次加数都新建一条链,那样就相当于又建了一棵01trie,n个数就会出现n个01trie,然后你有左端点和右端点,记录一下每个点的sum值,接下来就是主席树基操了。
warning:这题卡常,我开O2
```cpp
#include<bits/stdc++.h>
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 10000000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define mod 19260817
#define eps 1e-4
#define itset std::set<node>::iterator
#define lb lower_bound
#define N 18000005
#define ls (k << 1)
#define rs (k << 1 | 1)
char ch;
int b[N], rt[N], t[N][2], sum[N];
int n, m, s, x, cnt, l, r;
inline void split (int x)
{
fo (i, 0, 24)
{
if (x & 1) b[i] = 1; else b[i] = 0;
x >>= 1;
}
}
inline void update (int &now, int pk)
{
now = ++cnt;
int k = now;
sum[k] = sum[pk] + 1;
fd (i, 24, 0)
{
t[k][b[i]] = ++cnt;
t[k][b[i] ^ 1] = t[pk][b[i] ^ 1];
k = t[k][b[i]]; pk = t[pk][b[i]];
sum[k] = sum[pk] + 1;
}
}
inline int query (int pk, int k)
{
int ret = 0;
fd (i, 24, 0)
{
ret <<= 1;
if (sum[t[k][b[i] ^ 1]] - sum[t[pk][b[i] ^ 1]] > 0)
{
ret |= 1;
k = t[k][b[i] ^ 1]; pk = t[pk][b[i] ^ 1];
}
else
{
k = t[k][b[i]]; pk = t[pk][b[i]];
}
}
return ret;
}
int main ()
{
scanf("%d %d", &n, &m);
++n;
update(rt[1], rt[0]);
fo (i, 2, n)
{
scanf("%d", &x);
s ^= x;
split(s);
update(rt[i], rt[i - 1]);
}
fo (i, 1, m)
{
ch = getchar(); while (ch != 'A' && ch != 'Q') ch = getchar();
if (ch == 'A')
{
++n;
scanf("%d", &x); s ^= x;
split(s);
update(rt[n], rt[n - 1]);
}
else
{
scanf("%d %d %d", &l, &r, &x);
split(s ^ x);
printf("%d\n", query(rt[l - 1], rt[r]));
}
}
return 0;
}
```