quhengyi11 的博客

quhengyi11 的博客

题解 P4735 【最大异或和】

posted on 2018-11-16 22:06:37 | under 可持久化Trie树 |

可持久化Trie板子题

如果你会主席树的话,我有自信几句话就讲清楚这个算法

如果你不会的话,还是去学学主席树吧。

你肯定是会01trie的,但是01trie加进去就无序了,想想主席树,我们可以将每一次加数都新建一条链,那样就相当于又建了一棵01trie,n个数就会出现n个01trie,然后你有左端点和右端点,记录一下每个点的sum值,接下来就是主席树基操了。

warning:这题卡常,我开O2

#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;
}