线段树分治

Iceturky · 2024-07-01 21:36:59 · 个人记录

就是对于所有前缀查询，可以把操作序列放在线段树上进行维护，每一个操作序列都对应log个区间，对于每一个区间暴力放进去与拿出来。

模板的代码

const int N=2e5+5;

int n;

struct DSU{
    int fa[N<<1],sum[N<<1];
    struct hhh{
        int u,v;
        bool tag;
    }stk[N];int hd;
    void init(){
        for(int i=1;i<=2*n;i++)
            fa[i]=i,sum[i]=1;
    }
    int fd(int x){
        return fa[x]==x?x:fd(fa[x]);
    }
    void merge(int x,int y){
        int fx=fd(x),fy=fd(y);
        if(fx!=fy){
            fx=fd(x+n);
            if(sum[fx]<sum[fy])
                swap(fx,fy);
            hd++;
            stk[hd]={fx,fy,stk[hd-1].tag};
            sum[fx]+=sum[fy];
            fa[fy]=fx;
            fx=fd(x);
            fy=fd(y+n);
            if(sum[fx]<sum[fy])
                swap(fx,fy);
            hd++;
            stk[hd]={fx,fy,stk[hd-1].tag};
            sum[fx]+=sum[fy];
            fa[fy]=fx;
        }else
            stk[++hd]={0,0,1},stk[++hd]={0,0,1};
    }
    void del(){
        sum[stk[hd].u]-=sum[stk[hd].v];
        fa[stk[hd].v]=stk[hd].v;
        hd--;
        sum[stk[hd].u]-=sum[stk[hd].v];
        fa[stk[hd].v]=stk[hd].v;
        hd--;
    }
}D;

struct Seg_Tree{
    vector<pir>v[N<<2];
    void update(int x,int l,int r,int L,int R,pir a){
        if(L<=l&&r<=R)
            v[x].pb(a);
        else{
            if(L<=mid)
                update(ls,l,mid,L,R,a);
            if(R>mid)
                update(rs,mid+1,r,L,R,a);
        }
    }
    void calc(int x,int l,int r){
        for(pir i:v[x])
            D.merge(i.fi,i.se);
        if(l==r)
            printf(D.stk[D.hd].tag?"No\n":"Yes\n");
        else{
            calc(ls,l,mid);
            calc(rs,mid+1,r);
        }
        int tmp=v[x].size();
        while(tmp--)
            D.del();
    }
}T;

signed main(){
    n=read();int m=read(),k=read();
    D.init();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),l=read()+1,r=read();
        T.update(1,1,k,l,r,{u,v});
    }
    T.calc(1,1,n);
    return 0;
}