求求求求求原题自动机

来个原题自动机看看我这份双 \(\log\) 代码能不能过原题。

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=1e5+10;
int n,m,q,fa[N],size[N],root[N],cnt;
std::vector<int>son[N];
inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
struct TREE{
    int ls,rs,ans;
}t[N<<6];
inline void update(int p){
    if(t[t[p].ls].ans==t[t[p].rs].ans){
        t[p].ans=t[t[p].ls].ans;
    }else{
        t[p].ans=-1;
    }
    return;
}
inline void build(int p,int l,int r){
    if(l==r){t[p].ans=l;return;}
    int mid=l+r>>1;
    build(t[p].ls=++cnt,l,mid);
    build(t[p].rs=++cnt,mid+1,r);
    update(p);
}
inline int query(int p,int l,int r,int x,int y){
    if(l>=x&&r<=y){return t[p].ans;}
    int mid=l+r>>1,res=0;
    if(x<=mid){
        int zc=query(t[p].ls,l,mid,x,y);
        if(!res){res=zc;}
        else if(res!=zc){res=-1;}
    }
    if(y>mid){
        int zc=query(t[p].rs,mid+1,r,x,y);
        if(!res){res=zc;}
        else if(res!=zc)res=-1;
    }
    return res;
}
inline void insert(int p,int l,int r,int last,int pos,int x){
    if(l==r){t[p].ans=x;return;}
    int mid=l+r>>1;
    t[p]=t[last];
    if(pos<=mid){
        insert(t[p].ls=++cnt,l,mid,t[last].ls,pos,x);
    }
    else{
        insert(t[p].rs=++cnt,mid+1,r,t[last].rs,pos,x);
    }
    update(p);
}
inline void add(int x,int y,int k){
    x=find(x),y=find(y);
    if(x==y){root[k]=root[k-1];return;}
    if(son[x].size()>son[y].size())std::swap(x,y);
    fa[x]=y;
    int last=k-1;
    for(int it:son[x]){
        son[y].push_back(it);
        fa[it]=find(it);
        cnt++;
        int zc=cnt;
        insert(zc,1,n,root[last],it,fa[it]);
        root[k]=zc;
        last=k;
    }son[x].clear();
}
inline void look(int p,int l,int r){
    if(l==r){
        std::cout<<t[p].ans<<' ';
        return;
    }
    int mid=l+r>>1;
    look(t[p].ls,l,mid);
    look(t[p].rs,mid+1,r);
}
signed main(){
	// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
	std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
	n=read(),m=read(),q=read();
    for(int i=1;i<=n;++i)fa[i]=i,son[i].push_back(i);
    root[0]=++cnt;
    build(root[0],1,n);
	for(int i=1;i<=m;++i){
        int x=read(),y=read();
        add(x,y,i);
    }
    for(int i=1;i<=q;++i){
        int x=read(),y=read();
        int l=0,r=m,ans=0;
        while(l<=r){
            int mid=l+r>>1;
            if(query(root[mid],1,n,x,y)!=-1)r=mid-1,ans=mid;
            else l=mid+1;
        }
        std::cout<<ans<<'\n';
    }
}