【2017西安邀请赛:A】XOR(线段树+线性基)

前言：虽然已经有很多题解了，但是还是想按自己的理解写一篇。

思路：首先分析题目

　　　一、区间操作 —— 线段树

　　　二、异或操作 —— 线性基

　　　这个两个不难想，关键是下一步的技巧

　　　 “或”运算就是两个数的二进制中，对应位只要有1，那么就是该位结果就是 1，所以要想k“或”运算后的结果尽量大，

　　　就需要异或出的数，各个位上的1尽量多。

　　　线性基的操作，可以求出区间最大异或和，但是我们需要的结果是 “或”运算。

　　　所以我们可以将 k 取反，然后把所有数在加入线性基之前，全部 “与”运算一遍，再加入线性基。

　　　这样，线性基中的每一位，全部都是能使得k变大的数了，因为k的二进制上的每一位 1 的位置，线性基中都是0。

　　　所以，我们只需要求， k 异或线性基中最大异或和。

//#pragma comment(linker, "/STACK:1024000000,1024000000")

//#pragma GCC optimize(2)

#include <bits/stdc++.h>

#include<unordered_set>

using namespace std;

typedef double dou;

typedef long long ll;

typedef pair<int, int> pii;

typedef map<int, int> mii;

#define pai acos(-1.0)

#define M 10050

#define inf 0x3f3f3f3f

#define mod 1000000007

#define IN inline

#define W(a) while(a)

#define lowbit(a) a&(-a)

#define left k<<1

#define right k<<1|1

#define lson L, mid, left

#define rson mid + 1, R, right

#define ms(a,b) memset(a,b,sizeof(a))

#define Abs(a) (a ^ (a >> 31)) - (a >> 31)

#define random(a,b) (rand()%(b+1-a)+a)

#define false_stdio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

int T;

int n, q, k;

int tmp, x, y, z;

struct Data {

    int num[];

    void insert(int t) {

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

            if (t >> i & ) {

                if (!num[i]) { num[i] = t; break; }

                t ^= num[i];

            }

        }

    }

}tree[M << ], ans;

IN void Updata(int L, int R, int k,int pos) {

    tree[k].insert(tmp);

    if (L == R)return;

    int mid = L + R >> ;

    if (pos <= mid)Updata(lson, pos);

    else Updata(rson, pos);

}

IN void Query(int L, int R, int k) {

    if(x<=L && R<=y){

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

            if (tree[k].num[i])ans.insert(tree[k].num[i]);

        }

        return;

    }

    int mid = L + R >> ;

    if (x <= mid)Query(lson);

    if (y > mid)Query(rson);

}

IN int read() {//快读

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

    W(!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }

    W(isdigit(ch)) { v = (v << ) + (v << ) + (ch ^ ); ch = getchar(); }

    return f ? -v : v;

}

int main() {

    T = read();

    W(T--) {

        n = read(), q = read(), k = read();

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

            tmp = read();

            tmp &= (~k);//关键的一步

            Updata(, n, , i);

        }

        W(q--) {

            ms(ans.num, );

            x = read(), y = read();

            Query(, n, );

            z = k;

            for (int i = ; i >= ; i--)z = max(z, z ^ ans.num[i]);

            printf("%d\n", z);

        }

    }

    return ;

}

巴特西

【2017西安邀请赛:A】XOR(线段树+线性基)

最新文章

热门文章