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

题目链接

传送门

题意

给你\(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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair 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"=["< 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;
}
迷之博弈论比赛题解感想谜之莫队

相关

标签