AC题解

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m,q;
struct Edge{
    int u,v;
    int nxt;
}edge[N<<1];
int head[N],tot=0;
int ind[N],outd[N];
bool ok[N];
int fa[2][N];
int rt[2][N];
struct Tree{
    int siz;
    int ch[2];
}t[N<<6];
int ttot=0,was[N<<5],wastot=0;
bool have[N];
queue<int> tq;
string ans;
inline void add_edge(int u,int v){
    tot++;
    edge[tot]=(Edge){u,v,head[u]};
    head[u]=tot;
    ind[v]++,outd[u]++;
}
#define lson t[id].ch[0]
#define rson t[id].ch[1]
inline void pushup(int id){
    t[id].siz=t[lson].siz+t[rson].siz;
}
inline int NewNode(){ // 加了空间回收，不然会 MLE
    if(wastot){
        return was[wastot--];
    }
    return (++ttot);
}
inline void addwas(int id){
    if(wastot>=(N<<5)) return ;
    t[id].siz=t[id].ch[0]=t[id].ch[1]=0;
    was[++wastot]=id;
}
void Add(int &id,int L,int R,int k,bool del){
    if(!id) id=NewNode();
    if(L==R){
        t[id].siz=del;
        if(!del) addwas(id),id=0;
        return ;
    }
    int mid=(L+R)>>1;
    if(k<=mid) Add(lson,L,mid,k,del);
    else Add(rson,mid+1,R,k,del);
    pushup(id);
    if(!t[id].siz) addwas(id),id=0;
}
bool Have(int id,int L,int R,int k){
    if(!id) return false;
    if(L==R&&t[id].siz) return true;
    int mid=(L+R)>>1;
    return (k<=mid)?Have(lson,L,mid,k):Have(rson,mid+1,R,k);
}
int Findson(int id,int L,int R){
    if(L==R) return L;
    int mid=(L+R)>>1;
    if(t[lson].siz) return Findson(lson,L,mid);
    else return Findson(rson,mid+1,R);
}
inline int find(int k,int x){
    if(x==fa[k][x]) return x;
    return fa[k][x]=find(k,fa[k][x]);
}
int shanx,shany;
void Merge(int &x,int y,int L,int R){
    if(!y) return ;
    if(!x) x=y;
    if(L==R){
        if(t[y].siz){
            Add(rt[1][shanx],1,n,L,1);
            int pp=find(0,L);
            Add(rt[0][pp],1,n,shany,0),Add(rt[0][pp],1,n,shanx,1);
            if(t[rt[0][pp]].siz==1 && !have[pp]) tq.push(pp);
        }
        t[x].siz=(t[x].siz|t[y].siz);
        return ;
    }
    int mid=(L+R)>>1;
    Merge(t[x].ch[0],t[y].ch[0],L,mid);
    Merge(t[x].ch[1],t[y].ch[1],mid+1,R);
    pushup(x);
}
inline int makemerge(int k,int x,int y){ // y merge in x
    int fx=find(k,x),fy=find(k,y);
    if(fx!=fy) fa[k][fy]=fx;
}
void Topo(){
    for(int i=1;i<=n;i++){
        if(!ind[i]) tq.push(i),ok[i]=true;
    }
    while(!tq.empty()){
        int tp=tq.front();tq.pop();
        for(int i=head[tp];i;i=edge[i].nxt){
            int v=edge[i].v;
            if(!(--ind[v])) tq.push(v),ok[v]=true;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add_edge(v,u);
    }
    Topo();
    for(int i=1;i<=m;i++){
        int u=edge[i].u,v=edge[i].v;
        if(ok[u] || ok[v]) continue;
        Add(rt[0][v],1,n,u,1);
        Add(rt[1][u],1,n,v,1);
    }
    for(int i=1;i<=n;i++){
        fa[0][i]=fa[1][i]=i;
        if(ok[i]) continue;
        if(t[rt[0][i]].siz==1) tq.push(i);
    }
    while(!tq.empty()){
        int tp=tq.front();tq.pop();
        int now=find(0,tp),now1=find(1,tp);
        if(t[rt[0][now]].siz!=1 || have[now]) continue;
        int to=Findson(rt[0][now],1,n),nowto=find(0,to),nowto1=find(1,to);
        makemerge(0,to,tp);
        if(Have(rt[0][nowto],1,n,now1)) Add(rt[0][nowto],1,n,now1,0),Add(rt[1][now1],1,n,nowto,0),have[nowto]=true;
        Add(rt[1][nowto1],1,n,now,0);
        if(t[rt[1][now1]].siz < t[rt[1][nowto1]].siz){
            makemerge(1,nowto1,now1);
            shanx=nowto1,shany=now1,Merge(rt[1][nowto1],rt[1][now1],1,n);
        }
        else{
            makemerge(1,now1,nowto1);
            shanx=now1,shany=nowto1,Merge(rt[1][now1],rt[1][nowto1],1,n);
        }
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(ok[u] || ok[v]){
            ans+='B';
            continue; 
        }
        int fu=find(0,u),fv=find(0,v);
        if(fu==fv) ans+='B';
        else ans+='H';
    }
    cout<<ans<<endl;
}