区间查询异或最大值——cf1100F,hdu6579（线性基）

hdu6579

题意
初始时有n个数，现在有q次操作：

查询[l,r]内选择一些数使得异或和最大；
在末尾加入一个数。
题目强制在线。

思路
对于i我们记录[1,i]每个基底最靠近i的位置和这个位置的值，然后查询时看r 这个位置记录的每个基底的位置是否大于等于l，如果大于等于那么[l,r] 内一定有一个位置可以贡献这个基底，然后比较答案大小即可。

题目对数据加密了：

x^=lastans; ///题目的要求

l=(l^lastans)%n+1; ///题目的要求
r=(r^lastans)%n+1; ///题目的要求

#include<bits/stdc++.h>

using namespace std;

const int maxn =  + ;

int t, n, q, op, l, r, x;

int a[maxn], b[], pos[], base[maxn][], las[maxn][];

bool add(int val, int pp) {

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

        if (val & (1ll << i)) {

            if (!b[i]) {

                pos[i] = pp;

                b[i] = val;

                break;

            }

            if(pos[i] < pp) {

                swap(b[i], val);

                swap(pos[i], pp);

            }

            val ^= b[i];

        }

    }

    return val > ;

}

int main() {

    scanf("%d", &t);

    while(t--) {

        scanf("%d%d", &n, &q);

        for(int i = ; i >= ; --i) b[i] = , pos[i] = ;

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

            scanf("%d", &a[i]);

            add(a[i], i);

            for(int j = ; j >= ; --j) base[i][j] = b[j], las[i][j] = pos[j];

        }

        int lastans = ;

        while(q--) {

            scanf("%d", &op);

            if(op) {

                ++n;

                scanf("%d", &x);

                x ^= lastans;///题目的要求

                add(x, n);

                for(int i = ; i >= ; --i) base[n][i] = b[i], las[n][i] = pos[i];

            } else {

                scanf("%d%d", &l, &r);

                l = (l ^ lastans) % n + , r = (r ^ lastans) % n + ;///题目的要求

                if(l > r) swap(l, r);

                lastans = ;

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

                    if(las[r][i] >= l && (lastans ^ base[r][i]) > lastans) {

                        lastans ^= base[r][i];

                    }

                }

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

            }

        }

    }

    return ;

}

cf1100F - Ivan and Burgers

给定n和a[]

有q个询问：

给定l,r

求在a[]al…r中选取任意个，使得他们的异或和最大。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int maxn =1e6+;

int b[],pos[],a[maxn],base[maxn][],las[maxn][];

bool add(int val , int pp){

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

        if(val & (<<i)){

            if (!b[i]) {

                pos[i] = pp;

                b[i] = val;

                break;

            }

            if(pos[i] < pp) {

                swap(b[i], val);

                swap(pos[i], pp);

            }

            val^=b[i];

        }

    }

    return val>;

}

int main(){

        int n,q;

        scanf("%d",&n);

        for(int i= ; i>= ; i--) b[i]=,pos[i]=;

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

            scanf("%d",&a[i]);

            add(a[i],i);

            for(int j= ; j>= ; j--) base[i][j]=b[j],las[i][j]=pos[j];

        }

        int lastans=;

        scanf("%d",&q);

        while(q--){

                int op,x,l,r;

                scanf("%d%d",&l,&r);

                lastans=;

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

                    if(las[r][i]>=l && (lastans^base[r][i])>lastans){

                        lastans^=base[r][i];

                    }

                }

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

        }

}

巴特西

区间查询异或最大值——cf1100F,hdu6579（线性基）

最新文章

热门文章