社区讨论

为啥这能过?!!!

P5787【模板】线段树分治 / 二分图参与者 4已保存回复 11

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
11 条
当前快照
1 份
快照标识符
@mliskbgv
此快照首次捕获于
2026/02/12 09:40
4 周前
此快照最后确认于
2026/02/12 10:55
4 周前
查看原帖
rt,这是我的代码。可以看到,我在并查集 find 函数中进行了一个路径压缩。然而众所周知,可撤销并查集时不能路径压缩的。所以究竟时这道题我的代码有一些特殊的性质保证这么做时对的,还是数据水了?
CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define c(x) cerr<<#x<<":"<<x<<"\n"
#define dbg cerr<<"\n--------------\n"
#define endl '\n'
#define fi first
#define sc second
#define ls x<<1
#define rs (x<<1)|1
#define pii pair<int,int>
const int inf=3e18;
const int mod=998244353;
const int N=1e5+5;
int T,n,m,k,l,r,st,ed,L,x,y,z,now,len,sum,ans,cnt,top;
vector<pii> e[N<<2];
int siz[N<<1],f[N<<1];
pii stk[N<<1];
//sc->fi
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void merge(int x,int y){
    y=find(y),x=find(x);
    if(siz[x]<siz[y]) swap(x,y);
    stk[++top]={x,y};
    siz[x]+=siz[y];f[y]=x;
}
void clr(){
    x=stk[top].fi,y=stk[top].sc;
    siz[x]-=siz[y],f[y]=y;
    top--;
}
void ins(int l,int r,int a,int b,int x,pii k){
    if(l>=a && r<=b){
        e[x].push_back(k);
        return ;
    }
    int mid=l+r>>1;
    if(mid>=a) ins(l,mid,a,b,ls,k);
    if(mid<b) ins(mid+1,r,a,b,rs,k);
}
void solve(int l,int r,int x){
    int last=top;
    int flag=1;
    for(pii u:e[x]){
        int x=u.fi,y=u.sc;
//        cout<<x<<' '<<y<<endl;
        if(find(x)==find(y) || find(x+n)==find(y+n)) {flag=0;break;}
        merge(x,y+n);
        merge(x+n,y);
    }
    if(!flag){
//        cout<<l<<' '<<r<<endl;
        for(int i=l;i<=r;i++) cout<<"No\n";
    }else{
        if(l==r) cout<<"Yes\n";
        else{
            int mid=l+r>>1;
            solve(l,mid,ls),solve(mid+1,r,rs);
        }
    }
    while(top>last) clr();
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
   // freopen(".in","r",stdin);
   // freopen(".out","w",stdout);
    //cin>>T;
    //while(T--){
    //
    //}
    cin>>n>>m>>k;
    for(int i=1;i<=2*n;i++) f[i]=i,siz[i]=1;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>l>>r;
        l++;
        ins(1,k,l,r,1,{x,y});
    }
    solve(1,k,1);
    cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
    return 0;
}

回复

11 条回复,欢迎继续交流。

正在加载回复...