HDU 6610 Game

Description:

Again Alice and Bob is playing a game with stones. There are N piles of stones labelled from $1$ to $N$ , the i th pile has $a_i$ stones.

First Alice will choose piles of stones with consecutive labels, whose leftmost is labelled with $L$ and the rightmost one is $R$ . After, Bob will choose another consecutive piles labelled from $l$ to $r (L \le l \le r \le R)$ . Then they're going to play game within these piles.

Here's the rules of the game: Alice takes first and the two will take turn to make a move: choose one pile with nonegetive stones and take at least one stone and at most all away. One who cant make a move will lose.

Bob thinks this game is not so intersting because Alice always take first. So they add a new rule, which is that Bob can swap the number of two adjacent piles' stones whenever he want before a new round. That is to say, if the $i$ th and $i+1$ pile have $a_i$ and $a_i+1$ stones respectively, after this swapping there will be $a_i+1$ and $a_i$ .

Before today's game with Bob, Alice wants to know, if both they play game optimally when she choose the piles from L to R, there are how many pairs $(l, r)$ chosed by Bob that will make Alice win.

Input:

Input contains several test cases.

For each case:

The fisrt line contains $N$ , $M$ . $N$ is mentioned aboved ans M is the number of the sum of game rounds and the times of Bob's swapping.

The second line contains $N$ integars $a_1,a_2,...a_n$ , indicating the number of each piles' stones.

The next $M$ lines will have an integar $opt (1 \le opt \le 2)$ , indicating the type of operation.

If opt equals $1$ , then $L$ and $R$ follow. Alice and Bob start a new round and Alice choose $L$ and $R$ as mentioned.

If opt equals $2$ , then $POS$ follows. Bob will swap the piles labelled $POS$ and $POS+1$ .

$0 \le a_i \le 1,000,000$

$1 \le N,M \le 100,000, \sum N, \sum M<600,000$

$1 \le L \le R \le N$

$1 \le POS<N$

Output:

For each case:

For each opt which equals $1$ , you shall output one line with an integar indicating the number of pairs $(l,r)$ that will make Alice win the round.

Sample Input:

3 3
4 0 4
2 2
2 1
1 1 3

Sample Output:

3

题目链接

对一个数列 $a_i$ 支持两种操作

  1. l r 求区间 $[l,r]$ 内 $NIM$ 博弈先手必胜区间数量
  2. pos 将 $a_{i}$ 与 $a_{i+1}$ 交换

$NIM$ 博弈必胜表示区间异或和为零,即左右端点异或和前缀和相等

所以操作一就可以看做是求区间内相等数对数量,操作二为数列的单点修改

区间内相等数对数量可以用区间数字数量和区间不同数字数量表示出来

区间不同数字数量显然可以用莫队算法求解,但因为要支持操作二的单点修改,所以用带修莫队(也叫三维莫队)

AC代码:

#include <bits/stdc++.h>
const int maxn = 1e5 + 5;
const int maxm = 1e5 + 5;
const int maxb = (1 << 21) + 5;
int n, m;
int block;
int a[maxn], b[maxn];
struct Query { int l, r, t, id; };
Query qry[maxm];
int upd[maxm];
int qrytot, updtot;
long long cur;
long long cnt[maxb];
long long ans[maxm];
void Add(int idx) { cur += cnt[b[idx]]++; }
void Sub(int idx) { cur -= --cnt[b[idx]]; }
void Modify(int t, int i) {
    if (upd[t] >= qry[i].l && upd[t] <= qry[i].r) Sub(upd[t]);
    b[upd[t]] ^= a[upd[t]];
    std::swap(a[upd[t]], a[upd[t] + 1]);
    b[upd[t]] ^= a[upd[t]];
    if (upd[t] >= qry[i].l && upd[t] <= qry[i].r) Add(upd[t]);
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    while (std::cin >> n >> m) {
        block = std::pow(n, 2. / 3);
        qrytot = updtot = 0;
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; ++i) {
            std::cin >> a[i];
            b[i] = b[i - 1] ^ a[i];
        }
        for (int i = 1, opt, l, r, p; i <= m; ++i) {
            std::cin >> opt;
            if (opt == 1) {
                std::cin >> l >> r;
                qry[++qrytot] = (Query) {l - 1, r, updtot, qrytot};
            } else if (opt == 2) {
                std::cin >> p;
                upd[++updtot] = p;
            }
        }
        std::sort(qry + 1, qry + qrytot + 1, [&] (const Query &k1, const Query &k2) {
            if (k1.l / block != k2.l / block) return k1.l < k2.l;
            if (k1.r / block != k2.r / block) return k1.r < k2.r;
            return k1.t < k2.t;
        });
        cur = 0;
        int l = 0, r = -1, t = 0;
        for (int i = 1; i <= qrytot; ++i) {
            while (l < qry[i].l) Sub(l++);
            while (l > qry[i].l) Add(--l);
            while (r < qry[i].r) Add(++r);
            while (r > qry[i].r) Sub(r--);
            while (t < qry[i].t) Modify(++t, i);
            while (t > qry[i].t) Modify(t--, i);
            ans[qry[i].id] = 1ll * (r - l + 1) * (r - l) / 2 - cur;
        }
        for (int i = 1; i <= qrytot; ++i) std::cout << ans[i] << '\n';
    }
    return 0;
}
Last modification:September 4th, 2019 at 03:49 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment