腿部挂件「NOIP多校联考 2019」

题意

给定序列以及若干询问，每次询问格式为X L R，询问区间[L,R]中与X最大的异或值。

---

思路

看到异或很容易想到01trie，由于询问[L,R]，所以需要可持久化。

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {

    template<typename T>inline void read (T &x) {
        x=0;T f=1;char c=getchar();
        for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
        for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
        x*=f;
    }

    template<typename T>inline void write (T x) {
        if (x<0) putchar('-'),x*=-1;
        if (x>=10) write(x/10);
        putchar(x%10+'0');
    }

}

using namespace StandardIO;

namespace Project {

    const int N=200200;

    int n,q;
    int tot;
    int root[N];
    struct node {
        int cnt;
        int ch[2];
    } trie[N<<5];

    void update (int dep,int x,int &pos) {
        trie[++tot]=trie[pos],pos=tot,++trie[pos].cnt;
        if (dep==-1) return;
        update(dep-1,x,trie[pos].ch[(x>>dep)&1]);
    }
    int query (int dep,int x,int last,int cur) {
        if (dep==-1) return 0;
        int o=(x>>dep)&1;
        if (trie[trie[last].ch[o^1]].cnt<trie[trie[cur].ch[o^1]].cnt) return query(dep-1,x,trie[last].ch[o^1],trie[cur].ch[o^1])|(1<<dep);
        return query(dep-1,x,trie[last].ch[o],trie[cur].ch[o]);
    }

    inline void MAIN () {
        read(n),read(q);
        for (register int i=1,x; i<=n; ++i) {
            read(x);
            root[i]=root[i-1];
            update(31,x,root[i]);
        }
        while (q--) {
            int x,l,r;
            read(x),read(l),read(r);
            write(query(31,x,root[l],root[r+1])),putchar('\n');
        }
    }

}

int main () {
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    Project::MAIN();
}