【洛谷P5652】基础博弈练习题
博弈
题目大意：
给定一个数列 $a_i$，每个数均为正整数。每次会取区间 $[l,r]$ 进行游戏。规则如下：
开始时棋子在 $l$ 位置，并使得 $a_l$ 减去 $1$。从先手开始，每次向右移动 $0\sim m$ 格（不能超过 $r$），并且满足移动到的格子的 $a_i>0$，然后令 $a_i$ 减去 $1$。不能移动者输。问先手是否必胜。
每次询问独立。
题解：
我们从最后一格开始考虑。
如果 $a_r$ 是奇数，那么先手走到了 $a_r$ 后，两人就只能在这个格子上一直跳。最终先手获胜。那么容易得到，先手走到 $a_{r-m}\sim a_{r-1}$ 都是必败的，就转化为看 $a_{r-m-1}$ 的奇偶性
如果 $a_r$ 是偶数，那么先手走到 $a_r$ 就会必败，所以双方都会避免走到最后一个格子上，那么就转化为看 $a_{r-1}$ 的奇偶性。
容易发现，区间中最后一个先手必胜的格子是 $\leq r$ 的最右边的奇数位置。然后，奇数位置 $i$ 上一个先手必胜的格子是 $\leq i-m-1$ 的最右边的奇数位置。依次类推。
那么，$a_l$ 是先手必胜位置，必须满足 $a_l$ 是奇数，且 $r$ 能通过上述方式恰好跳到位置 $l$。
令 $p_i$ 表示 $\leq i$ 的最右边的奇数位置。
我们把所有奇数结点拿出来，对于结点 $i$，从 $p_i$ 的最右边结点处向 $i$ 连边，表示可以转移。这样形成了一个树形结构。
那么，$r$ 能跳到 $l$，必须满足 $l$ 是 $p_r$ 的祖先。这个可以通过预处理 dfs 序以后 $O(1)$ 判断。
然后就可以 $O(n+q)$ 解决。
注意，我们上面讨论的先手，指的是先手到达这个位置并执行一次减 $1$ 操作。本题由于开始时先减去了 $1$，所以可以认为后手走到了这个点，相当于询问先手是否必败。要注意区别。
Code：
#include<iostream>
#include<vector>
using namespace std;
const int N=1e6+5;
int n,m,q,tp,A,B,C,P,pre[N],dfn[N],idx,sz[N];
inline int rnd(){return A=(A*B+C)%P;}
vector<int>G[N];
void dfs(int now){
dfn[now]=++idx,sz[now]=1;
for(int i=0;i<G[now].size();++i)
dfs(G[now][i]),sz[now]+=sz[G[now][i]];
}
inline bool islca(int x,int y){return dfn[x]<=dfn[y]&&dfn[y]<dfn[x]+sz[x];}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>q>>tp;
for(int i=1;i<=n;++i){
int x;
cin>>x;
if(x&1)G[i-m-1>=0?pre[i-m-1]:0].push_back(pre[i]=i);else pre[i]=pre[i-1];
}
dfs(0);
unsigned ans=0;
if(tp)cin>>A>>B>>C>>P;
for(unsigned T=1;T<=q;++T){
int l,r;
if(tp)l=rnd()%n+1,r=rnd()%n+1;else cin>>l>>r;
if(l>r)l^=r^=l^=r;
if(pre[l]!=l||!islca(l,pre[r]))ans+=T*T;
}
cout<<ans<<'\n';
return 0;
}