社区讨论
为啥这能过?!!!
P5787【模板】线段树分治 / 二分图参与者 4已保存回复 11
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 11 条
- 当前快照
- 1 份
- 快照标识符
- @mliskbgv
- 此快照首次捕获于
- 2026/02/12 09:40 4 周前
- 此快照最后确认于
- 2026/02/12 10:55 4 周前
rt,这是我的代码。可以看到,我在并查集
CPPfind 函数中进行了一个路径压缩。然而众所周知,可撤销并查集时不能路径压缩的。所以究竟时这道题我的代码有一些特殊的性质保证这么做时对的,还是数据水了?#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 条回复,欢迎继续交流。
正在加载回复...