[LOJ#531]「LibreOJ β Round #5」游戏

试题描述

LCR 三分钟就解决了问题，她自信地输入了结果……

> …… 正在检查程序 ……

> …… 检查通过，正在评估智商 ……

> 对不起，您解决问题的速度过快，与加密者的智商不符。转入精确匹配。

> 由于您在模糊匹配阶段的智商差距过大，需要进行精确匹配。

LCR 发现，精确匹配是通过与随机对手（称为「神犇」）游戏的方式，藉由游戏的决策来评定智商的机制。游戏规则如下：

有一个长为 (n)，下标为 ([1,n]) 的数组 (f[])，且满足 (f[i]in [1,n])。

有一个变量 (a) 初始值为 (1)。双方轮流操作，LCR 先手。

操作方法：每次在所有满足 (f[i]=a) 的 (i) 中选一个，并将 (a) 赋值为 (i)，不能不选。无法操作者输，若共 (2n) 次操作后仍未决出胜负，则为平局。

我们定义二元关系“到达”如下：

(i) 可以到达 (i)
(i) 可以到达 (f[i])
如果 (i) 能到达 (j)，(j) 能到达 (k)，则 (i) 能到达 (k)。

则 (f) 数组满足性质：对于任意 (i,j) 存在 (k) 使得 (i) 和 (j) 都能到达 (k)。

LCR 即将面对 (q) 局游戏。她发现每局游戏的 (f[]) 数组都和给定的「模板数组」很像。经过进一步研究她发现每局游戏可以描述如下：

给出两个整数 (u,v)，满足在模板数组中 (f[u]) 能到达 (u)，(f[v]) 能到达 (v)。则该局游戏的 (f[]) 是把模板数组的 (f[u]) 赋值为 (v) 后得到的。

现在 LCR 希望你帮她计算每局游戏的胜负状态。

输入

第一行两个正整数 (n,q)。

第二行 (n) 个整数表示 (f[])。

接下来 (q) 行每行两个整数 (u,v) 描述一局游戏。

输出

输出共 (q) 行。

每行一个整数 (r) 表示结果。 (r=1) 表示先手（LCR）有必胜策略，(r=0) 表示后手（神犇）有必胜策略，(r=2) 表示平局。

输入示例

7 3
3 1 2 3 4 3 2
1 1
2 3
2 1

输出示例

2
0
0

数据规模及约定

对于所有数据，(1le n,qle 10^6)。

题解

这题贼恶心。。。

首先题目 BB 半天就是在说明如果建立一个有向图，满足 (i) 到 (f[i]) 有一条有向边，则这个有向图是一个环套树，其中树上所有节点都是指向环的。然后每次询问都是改变环上的一条边，改后边的终点还是在原环上。

那么分情况讨论吧。

(1) 如果 (1) 号节点在树上，直接树形 dp，每次询问都不影响结果。

(2) 如果 (1) 号点在环上，再分情况讨论一下修改。主要是两大类（显然改变后会形成一个新环）：(1) 在改之后的新环上和不在新环上。首先我们从节点 (1) 顺着有向边给环依次标号，记原图中节点 (x) 的环标号为 (cid[x])，然后对于询问 ((u, v))，我们令 (U = cid[u])，(V = cid[v])（请记住一点，在博弈的时候是逆着原图方向走的，故以下“距离”等概念都是逆原图方向的）。

(1) 在新环上，则要么 (U < V)，要么 (V = 1)。在这里我们明确一点，就是在真正博弈的时候，双方都会逆着圆环走，直到碰到一个节点 (node)，满足以 (node) 为根的外向树的 dp 结果为先手必胜，就会往树上走（此时我们可以认为走到节点 (node) 的那一方获胜）；否则不会往树上走，如果不存在这样的 (node)，那么就分不出输赢（因为双方会不停地在环上绕啊绕啊绕）。想清楚这一点，所有情况画画图都可以解决了。
(1) 不在新环上，就是剩下的情况。

注意环形态的改变，会导致环上的一段被“甩”了出去，变成了树的一部分。这个时候我们需要重新处理一下树上点的 dp 值，手画一个样例，可以发现对于一段原 dp 值为 (10001110010001) 的环的一部分，在它断开之后，只有原来是 (0) 的部分的 dp 值可能改变，改变条件是前面有奇数个 (0)（可以想象从左往右有 (dp[i] = dp[i] exttt{ }or exttt{ }not(dp[i-1]))，于是一段连续的 (0) 会变成 (010101...)）。

还有就是我们需要维护一下距离环上每个节点最近的 dp 值为 (1) 的节点的位置（注意是逆着原图方向最近的），这样我们就能用距离的奇偶性出当移动到 dp 值为 (1) 的节点时是谁先手了。

我语言能力好差。。。看不懂的话丢链接跑。（标算方法可能和我的不太一样，目前(2017-10-13 23:09)我的做法最快）

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
	if(Head == Tail) {
		int l = fread(buffer, 1, BufferSize, stdin);
		Tail = (Head = buffer) + l;
	}
	return *Head++;
}
int read() {
	int x = 0, f = 1; char c = Getchar();
	while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
	while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
	return x * f;
}

#define maxn 1000010

int n, fa[maxn];

struct Graph {
	int m, head[maxn], nxt[maxn], to[maxn];
	Graph(): m(0) { memset(head, 0, sizeof(head)); }
	void AddEdge(int a, int b) {
		to[++m] = b; nxt[m] = head[a]; head[a] = m;
		return ;
	}
} gr, tr;

bool vis[maxn], is_cyc[maxn], has_tr[maxn], win[maxn];
int St[maxn], top, cps[maxn], cntc;
bool findcyc(int u) {
	if(vis[u]) {
		while(St[top] != u) is_cyc[cps[++cntc] = St[top--]] = 1;
		is_cyc[cps[++cntc] = u] = 1;
		return 1;
	}
	St[++top] = u; vis[u] = 1;
	for(int e = gr.head[u]; e; e = gr.nxt[e]) if(findcyc(gr.to[e])) return 1;
	return 0;
}
void dp(int u) {
	win[u] = 0;
	for(int e = tr.head[u]; e; e = tr.nxt[e]) if(!is_cyc[tr.to[e]]) {
		has_tr[u] = 1;
		dp(tr.to[e]);
		if(!win[tr.to[e]]) win[u] = 1;
	}
	return ;
}

int cid[maxn], pid[maxn], near[maxn];
bool winc[maxn], hastrc[maxn];
int Pre(int x) {
	return x - 1 ? x - 1 : cntc;
}
int Nxt(int x) {
	return x + 1 <= cntc ? x + 1 : 1;
}
int Dis(int a, int b) { // from a revers-cycle-steps to b
	if(a >= b) return a - b;
	else return a + cntc - b;
}
bool canwin(int a, int brk) {
	if(!near[a]) return (a == brk ? cntc : Dis(a, brk)) - 1 & 1;
	if(a == brk) return min(Dis(a, near[a]), cntc) - 1 & 1;
	return min(Dis(a, near[a]), Dis(a, brk)) - 1 & 1;
}

int main() {
	n = read(); int q = read();
	for(int i = 1; i <= n; i++) fa[i] = read(), tr.AddEdge(fa[i], i), gr.AddEdge(i, fa[i]);
	
	findcyc(1);
//	printf("cps: "); for(int i = 1; i <= cntc; i++) printf("%d%c", cps[i], i < cntc ? ' ' : '
');
	bool oncyc = 0;
	for(int i = 1; i <= cntc; i++) {
		dp(cps[i]);
		if(cps[i] == 1) oncyc = 1;
	}
	if(!oncyc) {
		while(q--) {
			read(); read();
			printf("%d
", win[1]);
		}
		return 0;
	}
	// remark id
	int onep, cnt = 0, ntr = -1;
	for(int i = cntc; i; i--) if(cps[i] == 1){ onep = i; break; }
	for(int i = onep; i; i--) cid[cps[i]] = ++cnt, pid[cnt] = cps[i], winc[cnt] = win[cps[i]], hastrc[cnt] = has_tr[cps[i]];
	for(int i = cntc; i > onep; i--) cid[cps[i]] = ++cnt, pid[cnt] = cps[i], winc[cnt] = win[cps[i]], hastrc[cnt] = has_tr[cps[i]];
//	for(int i = 1; i <= cntc; i++) printf("%d: %d %d
", i, hastrc[i], winc[i]);
	for(int i = 1; ; i = Nxt(i)) {
		if(hastrc[i] && winc[i]) ntr = i;
		if(ntr >= 0) near[i] = ntr;
		if(Nxt(i) == 1) break;
	}
	for(int i = 1; ; i = Nxt(i)) {
		if(hastrc[i] && winc[i]) ntr = i;
		if(ntr >= 0) near[i] = ntr;
		if(Nxt(i) == 1) break;
	}
//	for(int i = 1; i <= cntc; i++) if(hastrc[i] && winc[i]) printf("(1)%d ", i); putchar('
');
	for(int kase = 1; kase <= q; kase++) {
		int u = read(), v = read();
		u = cid[u]; v = cid[v];
		if(u < v) {
			if(winc[1]){ puts("1"); continue; }
			if(near[1] >= v){ puts((Dis(1, near[1]) & 1) ? "0" : "1"); continue; }
			if(winc[v] | canwin(v, u)){ puts((Dis(1, v) & 1) ? "0" : "1"); continue; }
			if(1 < near[u] && near[u] <= u){ puts((Dis(1, v) + 1 + Dis(u, near[u]) & 1) ? "0" : "1"); continue; }
			puts("2");
			continue;
		}
		if(v == 1) {
			if(winc[1] | canwin(1, u)) puts("1");
			else if(1 < near[u] && near[u] <= u) puts((Dis(u, near[u]) + 1 & 1) ? "0" : "1");
			else puts("2");
			continue;
		}
		if(winc[1] | canwin(1, u)) puts("1");
		else puts("0");
	}
	
	return 0;
}