Consecutive Sum LightOJ - 1269(区间异或和)

Consecutive Sum

又来水一发blog...

本来是昨天补codechef的题，最后一道题是可持久化字典树，然后去黄学长博客看了看

觉得字典树写法有点不太一样，就想着用黄学长的板子写码几道题吧...

最后发现...其实是可持久化字典树跟普通字典树写法不一样...我好傻逼...

区间异或和

可以先把前缀异或和插入到字典树中，然后去贪心

求最大值就是要求从高到低尽量不一样

高位不一样优先

用一个bit数组来存放好看多了

偷偷摸摸顺便学了快读板子...虽说可能没啥用...

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e6 + ;

int sum[ + ];

int ans1, ans2;

int bit[];

inline int read() {

    int x = , f = ; char ch = getchar();

    while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }

    while (ch >= '' && ch <= '') { x = x *  + ch - ''; ch = getchar(); }

    return x * f;

}

struct Trie {

    int tol;

    int Next[maxn][];

    void init() {

        tol = ;

        memset(Next, , sizeof(Next));

    }

    void insert(int x) {

        int root = ;

        for (int i = ; i >= ; i--) {

            int id = x & bit[i]; id >>= i;

            if (!Next[root][id]) Next[root][id] = ++tol;

            root = Next[root][id];

        }

    }

    void query(int x) {

        int temp1 = , root1 = , root2 = , temp2 = ;

        for (int i = ; i >= ; i--) {

            int id = x & bit[i]; id >>= i;

            if (Next[root1][id ^ ]) root1 = Next[root1][id ^ ], temp1 += bit[i];

            else root1 = Next[root1][id];

            if (Next[root2][id]) root2 = Next[root2][id];

            else root2 = Next[root2][id ^ ], temp2 += bit[i];

        }

        ans1 = max(ans1, temp1);

        ans2 = min(ans2, temp2);

    }

} trie;

int main() {

    bit[] = ; for(int i = ; i <= ; i++) bit[i] = bit[i-] << ;

    int T;

    T = read();

   // cin >> T;

    int kase = ;

    while (T--) {

        int n = read();

      //  Trie trie;

        trie.init();

        ans1 = ;

        ans2 = 0x3f3f3f3f;

        trie.insert();

        for (int i = ; i <= n; i++) {

            int x; cin >> x;

            sum[i] = sum[i-] ^ x;

            trie.query(sum[i]);

            trie.insert(sum[i]);

        }

        printf("Case %d: %d %d", ++kase, ans1, ans2);

        puts("");

    }

    return ;

}