题目链接

题意

给你\(n\)堆石子，每堆有\(a_i\)堆石子，\(q\)次操作：

在\([L,R]\)内有多少个子区间使得\(Alice\)(先手)在\(Nim\)博弈中获胜；
交换\(a_{pos},a_{pos+1}\)的值。

思路

这题和cf617E差不多。

首先我们知道以下性质：

\(Nim\)博弈只有当所有石子数异或为\(0\)才会导致先手必败；
在预处理前缀异或和后，交换相邻两堆石子的石子数只会影响\(pos\)处的值。

因此我们在预处理出前缀异或和后就可以用待修改莫队来解决本题，我们用\(cnt\)数组来处理出区间内\(x\)出现次数，\(sum\)表示区间内有多少个子区间异或和为\(0\)，那么最后答案为\(\frac{(R-L+1)(R-L)}{2}-sum\)。

代码实现如下

#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("D://Code//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 = 1e5 + 7;

const double pi = acos(-1);

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3fLL;

int n, q, op, l, r, block;

LL sum;

int a[maxn], b[maxn];

LL cnt[1<<20+5];

struct que {

    int l, r, id, t;

    LL ans;

    bool operator < (const que& x) const {

        if((l - 1) / block != (x.l - 1) / block) {

            return l < x.l;

        }

        if((r - 1) / block != (x.r - 1) / block) {

            return r < x.r;

        }

        return t < x.t;

    }

}ask[maxn];

struct modify {

    int pre, val, pos;

}mfy[maxn];

void del(int x) {

    --cnt[x];

    sum -= cnt[x];

}

void add(int x) {

    sum += cnt[x];

    ++cnt[x];

}

int main() {

#ifndef ONLINE_JUDGE

FIN;

#endif // ONLINE_JUDGE

    while(~scanf("%d%d", &n, &q)) {

        sum = 0;

        for(int i = 0; i <= 1024 * 1024; ++i) cnt[i] = 0;

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

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

            b[i] = b[i-1] ^ a[i];

        }

        block = (int)pow(n, 2.0 / 3);

        int nw = 0, idq = 0, idc = 0;

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

            scanf("%d", &op);

            if(op == 1) {

                idq++;

                scanf("%d%d", &ask[idq].l, &ask[idq].r);

                ask[idq].id = idq;

                --ask[idq].l;

                ask[idq].t = nw;

            } else {

                idc++;

                ++nw;

                scanf("%d", &mfy[idc].pos);

                int pos = mfy[idc].pos;

                mfy[idc].pre = b[pos];

                mfy[idc].val = b[pos+1] ^ a[pos];

                b[pos] = b[pos+1] ^ a[pos];

                swap(a[pos], a[pos+1]);

            }

        }

        sort(ask + 1, ask + idq + 1);

        int tmp = nw;

        for(int i = 1, l = 1, r = 0; i <= idq; ++i) {

            while (r < ask[i].r) add(b[++r]);

            while (l > ask[i].l) add(b[--l]);

            while (r > ask[i].r) del(b[r--]);

            while (l < ask[i].l) del(b[l++]);

            while (tmp < ask[i].t) {

                tmp++;

                if (mfy[tmp].pos >= ask[i].l && mfy[tmp].pos <= ask[i].r) {

                    del(mfy[tmp].pre);

                    add(mfy[tmp].val);

                }

                b[mfy[tmp].pos] = mfy[tmp].val;

            }

            while (tmp > ask[i].t) {

                if (mfy[tmp].pos >= ask[i].l && mfy[tmp].pos <= ask[i].r) {

                    del(mfy[tmp].val);

                    add(mfy[tmp].pre);

                }

                b[mfy[tmp].pos] = mfy[tmp].pre;

                tmp--;

            }

            ask[ask[i].id].ans = 1LL * (ask[i].r - ask[i].l) * (ask[i].r - ask[i].l + 1) / 2 - sum;

        }

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

            printf("%lld\n", ask[i].ans);

        }

    }

    return 0;

}

巴特西

2019年杭电多校第三场 1008题Game(HDU6610+带修改莫队+Nim博弈)

题目链接

题意

思路

代码实现如下

最新文章

热门文章