Prelude
题目链接：萌萌哒传送门
Subtask 1 & 2
这是什么鬼题面。。。
首先要看出，这就是一个基环树博弈。 具体题意：给出一个基环内向树，一个棋子初始在\(1\)号节点，双方轮流操作，设棋子所在节点为\(u\)，每次可以从所有指向\(u\)的节点中选择一个，把棋子移动过去，不能操作者输，问先手是否有必胜策略，或者是否平局。 但是，这个图是可以变的，每次询问，假如我选择环上的两个点\(u\)和\(v\)，把\(u\)的出边指向\(v\)，那么游戏的结果如何？ 考虑如果只有一次询问，不修改的话怎么做。 这么裸的博弈随便做吧？先假设把环上的所有边断开，然后dp求出每个节点的状态，最后再考虑环上的情况，当环上所有点都是必败态的时候就是平局，否则两个人沿着环走，第一个走到必胜节点的人获胜。 求解一次是\(O(n)\)的，一共\(q\)次询问，总时间复杂度\(O(nq)\)。Subtask 3 & 4
首先我们可以预处理求出离环上每个点最近的必胜点是哪个，我这里用\(left_{i}\)表示。
每次对原图做修改，相当于把环缩小到原来的环的一个片段。 假如我们选了环上的\(u\)和\(v\)两个节点，并且把\(u\)的出边连接到\(v\)，那么\(f_{u}\)到\(v\)这一段的dp值都可能会改变。 我们可以用倍增预处理，用\(jump[x][s][k]\)表示假如点\(x\)的状态为\(s\)，那么\(x\)之后第\(2^{k}\)个点的状态是什么，这样，查询一个点的状态就是\(O(\log n)\)的了。 对于点\(1\)不在环上的情况，我们可以直接查询，\(O(\log n)\)解决。 如果点\(1\)在环上，我们因为有之前预处理的结果，所以只需要求出点\(v\)的新的dp值（\(O(\log n)\)），然后大力分类讨论（\(O(1)\)）解决。 总体复杂度就是\(O(n \log n)\)，能过87分辣~Subtask 5
LCA告诉我可以线性做，然而我并不会。
瓶颈是倍增，怎么去掉倍增？怎么降低查询的复杂度？ 我们离线所有的询问，这样就可以用并查集，在\(O(n \alpha(n))\)的时间内处理出所有的“对点\(v\)的dp值的询问”。 这样总体复杂度就变成了\(O(n \alpha(n))\)辣~ 因为我比较懒，所以离线询问的时候对询问排了序，复杂度还是\(O(n \log n)\)的，但是这个\(O(n \log n)\)比倍增的\(O(n \log n)\)要小得多了，也是能AC的。Conclusion
为了处理方便，我们通常把环拆开，拆成一条链来处理。
于是就少不了大量的分类讨论，我写了200行。 这件事告诉我们，LCA题不可做(╯‵□′)╯︵┻━┻。Code
#include#include #include #include #include using namespace std;const int MAXN = 1000010;const int LOGN = 21;int _w;int read() { int x = 0, ch; while( isspace(ch = getchar()) ); do x = x * 10 + ch - '0'; while( isdigit(ch = getchar()) ); return x;}int n, q, f[MAXN];int lp[MAXN], lpsz, pos[MAXN]; // lp为环上的每个节点，lpsz为环的大小，pos为原图中的节点在环中的位置void find_loop() { int u = 1; while( !pos[u] ) { pos[u] = ++lpsz; lp[lpsz] = u; u = f[u]; } int sz = 0; for( int i = pos[u]; i <= lpsz; ++i ) lp[++sz] = lp[i]; lpsz = sz; for( int i = 1; i <= n; ++i ) pos[i] = 0; // 不在环中的节点pos == 0 for( int i = 1; i <= lpsz; ++i ) pos[lp[i]] = i;}int pa[MAXN<<1]; // 并查集相关int find( int u ) { return pa[u] == u ? u : pa[u] = find(pa[u]);}int dp[MAXN], deg[MAXN], left[MAXN];queue bfsq;int toend[MAXN][2], to1[MAXN][2]; // to1[x][s]表示当x点的状态为s的时候，点1的状态是什么，toend类似，表示序列上最后一个点的信息void prelude() { find_loop(); for( int i = 1; i <= n; ++i ) ++deg[f[i]]; for( int i = 1; i <= n; ++i ) if( !deg[i] ) bfsq.push(i); while( !bfsq.empty() ) { int u = bfsq.front(); bfsq.pop(); if( !dp[u] ) dp[f[u]] = 1; if( --deg[f[u]] == 0 ) bfsq.push(f[u]); } for( int i = 1; i <= lpsz; ++i ) if( dp[lp[i]] ) left[i] = i; else left[i] = left[i-1]; for( int i = 1; i < lpsz; ++i ) { pa[i] = i+1+lpsz; pa[i+lpsz] = i+1 + dp[lp[i+1]] * lpsz; } pa[lpsz] = lpsz; pa[lpsz+lpsz] = lpsz+lpsz; for( int i = 1; i <= lpsz; ++i ) { toend[i][0] = find(i) > lpsz; toend[i][1] = find(i+lpsz) > lpsz; } if( pos[1] ) { for( int i = 1; i != pos[1]; ++i ) { pa[i] = i+1+lpsz; pa[i+lpsz] = i+1 + dp[lp[i+1]] * lpsz; } pa[pos[1]] = pos[1]; pa[pos[1]+lpsz] = pos[1]+lpsz; for( int i = 1; i != pos[1]; ++i ) { to1[i][0] = find(i) > lpsz; to1[i][1] = find(i+lpsz) > lpsz; } to1[pos[1]][0] = 0; to1[pos[1]][1] = 1; } for( int i = 1; i <= lpsz; ++i ) { pa[i] = i; pa[i+lpsz] = i+lpsz; }}int calc( int t, int v, int p ) { static int right = 1; if( t > p ) { // 把环拆成序列就要大力分类讨论。。。 v = toend[t][v]; t = 1; v = !v || dp[lp[1]]; } if( p == pos[1] ) return to1[t][v]; while( right < p ) { // 对所有询问按照查询位置排序 pa[right] = right+1+lpsz; pa[right+lpsz] = right+1 + dp[lp[right+1]] * lpsz; ++right; } return find(t + v*lpsz) > lpsz;}int solve( int l, int r ) { if( !pos[1] ) return dp[1]; // 点1不在环上 l = pos[l], r = pos[r]; int p = pos[1]; if( l >= r ) { // 下面都是分类讨论。。。 swap(l, r); if( p < l || p > r ) { // 点1不在环上 int t = r == lpsz ? 1 : r+1; return calc(t, dp[lp[t]], p); } else { int dpl = dp[lp[l]]; if( l > 1 || r < lpsz ) { int t = r == lpsz ? 1 : r+1; dpl = calc(t, dp[lp[t]], l); } if( left[p] >= l+1 ) { int q = left[p]; return (p-q+1)&1; } else if( dpl ) { return (p-l+1)&1; } else if( left[r] >= l+1 ) { int q = left[r]; return (p-l+1+r-q+1)&1; } else { return 2; } } } else { if( p > l && p < r ) { int t = l+1; return calc(t, dp[lp[t]], p); } else if( p <= l ) { int t = l+1; int dpr = calc(t, dp[lp[t]], r); if( left[p] ) { int q = left[p]; return (p-q+1)&1; } else if( left[lpsz] >= r+1 ) { int q = left[lpsz]; return (lpsz-q+1+p)&1; } else if( dpr ) { return (p+lpsz-r+1)&1; } else if( left[l] ) { int q = left[l]; return (lpsz-r+1+p+l-q+1)&1; } else { return 2; } } else { int t = l+1; int dpr = calc(t, dp[lp[t]], r); if( left[p] >= r+1 ) { int q = left[p]; return (p-q+1)&1; } else if( dpr ) { return (p-r+1)&1; } else if( left[l] ) { int q = left[l]; return (p-r+1+l-q+1)&1; } else if( left[lpsz] >= r+1 ) { int q = left[lpsz]; return (p-r+1+l+lpsz-q+1)&1; } else { return 2; } } }}int qu[MAXN], qv[MAXN]; // 存放询问的地方int rk[MAXN], ans[MAXN];bool cmp_qv( int i, int j ) { // 对询问按照点在序列上的位置排序 i = pos[qv[i]], j = pos[qv[j]]; return i < j;}int main() { n = read(), q = read(); for( int i = 1; i <= n; ++i ) f[i] = read(); prelude(); for( int i = 0; i < q; ++i ) qu[i] = read(), qv[i] = read(), rk[i] = i; sort(rk, rk+q, cmp_qv); for( int i = 0; i < q; ++i ) ans[rk[i]] = solve(qu[rk[i]], qv[rk[i]]); for( int i = 0; i < q; ++i ) printf( "%d\n", ans[i] ); return 0;}