题目链接

题意

初始时有\(n\)个数，现在有\(q\)次操作：

查询\([l,r]\)内选择一些数使得异或和最大；
在末尾加入一个数。

题目强制在线。

思路

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

本题和\(cf1100F\)一样的写法只是多了个操作而已。

代码实现如下

#include <set>

#include <map>

#include <deque>

#include <queue>

#include <stack>

#include <cmath>

#include <ctime>

#include <bitset>

#include <cstdio>

#include <string>

#include <vector>

#include <cassert>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <unordered_map>

using namespace std;

typedef long long LL;

typedef pair<LL, LL> pLL;

typedef pair<LL, int> pLi;

typedef pair<int, LL> pil;;

typedef pair<int, int> pii;

typedef unsigned long long uLL;

#define lson rt<<1

#define rson rt<<1|1

#define lowbit(x) x&(-x)

#define name2str(name) (#name)

#define bug printf("*********\n")

#define debug(x) cout<<#x"=["<<x<<"]" <<endl

#define FIN freopen("/home/dillonh/CLionProjects/Dillonh/in.txt","r",stdin)

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

const double eps = 1e-8;

const int mod = 1000000007;

const int maxn = 1000000 + 7;

const double pi = acos(-1);

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3fLL;

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

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

bool add(int val, int pp) {

    for (int i = 30; i >= 0; 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 > 0;

}

int main() {

#ifndef ONLINE_JUDGE

    FIN;

#endif

    scanf("%d", &t);

    while(t--) {

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

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

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

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

            add(a[i], i);

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

        }

        int lastans = 0;

        while(q--) {

            scanf("%d", &op);

            if(op) {

                ++n;

                scanf("%d", &x);

                x ^= lastans;

                add(x, n);

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

            } else {

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

                l = (l ^ lastans) % n + 1, r = (r ^ lastans) % n + 1;

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

                lastans = 0;

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

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

                        lastans ^= base[r][i];

                    }

                }

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

            }

        }

    }

    return 0;

}

巴特西

2019年杭电多校第一场 1002题Operation(HDU6579+线性基)

题目链接

题意

思路

代码实现如下

最新文章

热门文章