题解：P16929 迷向术式

· · 题解

注意到一个事情就是，如果 i 可以到 j，然后 j 可以到 k，那么把路径拼一起得到的恰好是一个合法解。

于是大喷菇的第一步操作必然可以击杀番茄，番茄能赢当且仅当大喷菇一步都走不了，于是考虑对于每个点维护最近的一个可达后继。

如果这个点的可达连通块内有奇环，那么显然每个连通块内的点都可以作为合法后继，于是我们对连通块维护一个栈状物，每次来新的点就把原先的顶端的后继设置为当前点，然后把这个点放上去。

如果这个连通块是二分图呢？

考虑把原先的一个栈换成四个，分别对黑色 / 白色的编号是奇数 / 偶数的各开一个，于是每次对号入座然后按照关系能连就连就好了。

一个点可能会在这个过程中多次连向后继，显然只需要保留第一次连的那个后继就好了。

询问的时候判断后继是否在范围内即可。

#include<bits/stdc++.h>
using namespace std;
vector<int>ve[200005];
int fa[200005];
bool h[200005];
bool vis[200005];
bool c[200005];
int tp;
void dfs(int x){
    fa[x]=tp;
    vis[x]=1;
    for(int i:ve[x])
    if(!vis[i])c[i]=c[x]^1,dfs(i);
    else if(c[i]==c[x])h[tp]=1;
}
int ed[200005];
int mx[200005][2][2];
int main(){
    int n,m,k,q;
    cin>>n>>m>>k>>q;
    while(m--){
        int u,v;
        cin>>u>>v;
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    if(!vis[i])tp++,dfs(i);
    for(int i=1;i<=k;i++)
    ed[i]=k+1;
    for(int i=1;i<=k;i++){
        int x;
        cin>>x;
        if(h[fa[x]])
        ed[mx[fa[x]][0][0]]=i,mx[fa[x]][0][0]=i;
        else{
            ed[mx[fa[x]][c[x]][i&1]]=min(i,ed[mx[fa[x]][c[x]][i&1]]);
            ed[mx[fa[x]][c[x]^1][(i&1)^1]]=min(i,ed[mx[fa[x]][c[x]^1][(i&1)^1]]);
            mx[fa[x]][c[x]][i&1]=i;
        }
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        if(ed[l]<=r)cout<<"Fern\n";
        else cout<<"Stark\n";
    }
    return 0;
}
// 把想要哭泣的心情藏在胸口，莫妮卡暧昧地回以微笑。