莫队 博弈论 NIM博弈    发布于 2019-07-30   348人围观   0条评论

题目大意

先手选出区间L-R的连续的石子堆,后手可以交换第pos 和 pos+1堆石子,然后再从L-R选出区间l-r的石子两人进行取石子博弈。

问在L-R中有多少种后手取l-r的方案能够使得先手必胜。

题解

这题是一个经典的NIM博弈。我们需要用SG函数来解决。

我们考虑前缀SG函数异或和,区间L-R内有多少选择l-r的方案使得先手必胜这一点我们可以转化为有都少方案使得先手必败(SG函数异或和为0)

l-r的SG函数异或和为0,即前缀异或和ssg满足ssg[r] = ssg[l-1],问题转化为统计区间中有多少ssg相等的点对数。

然后我们使用区间点对总数减去区间中ssg相等的点对数就是当前询问的答案。点对问题我们通常使用莫队的分治思想来处理。

然而此题还有交换石子堆的操作,我们能够发现,交换实际上只对一个前缀异或和有影响,所以交换操作实际上就是一个单点修改。

于是我们使用带修改莫队处理整个题目。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num<<3) + (num << 1) + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 1e5+5;
int n,m;
struct query{
    int l,r,t,id;
}q[maxn];
int belong[maxn];
int upd[maxn];
int qcnt,dcnt;
int a[maxn],b[ma
查看更多