你写的这个是写挂了的按 size 合并吧。
by Aestas16 @ 2022-10-28 22:00:26
@[Aestas16](/user/128141) 欸好像没写挂,有没有完整代码啊 /kel
by Aestas16 @ 2022-10-28 22:03:27
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=100005;
int n,m,k,u[N<<1],v[N<<1],fa[N<<1],dep[N<<1],l,r;
vector<int>tree[N<<2];
stack<pii>s;
inline int read()
{
int ans=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
ans=(ans<<3)+(ans<<1)+(c^48);
c=getchar();
}
return ans*f;
}
inline void write(int x)
{
if(x>9) write(x/10);
putchar(x%10+'0');
}
void update(int now,int l,int r,int ql,int qr,int x)
{
if(r<ql||l>qr) return;
if(l>=ql&&r<=qr)
{
tree[now].push_back(x);
return;
}
int mid=l+r>>1;
if(ql<=mid) update(now*2,l,mid,ql,qr,x);
if(qr>mid) update(now*2+1,mid+1,r,ql,qr,x);
return;
}
int find(int x)
{
while(fa[x]^x) x=fa[x];
return x;
}
void merge(int u,int v)
{
if(u==v) return;
if(dep[u]<dep[v]) swap(u,v);
s.push(make_pair(v,dep[v]));
fa[v]=u;
dep[u]+=dep[v];
return;
}
void dfs(int now,int l,int r)
{
bool ok=0;
int sz=s.size();
for(int i=0;i<tree[now].size();i++)
{
int x=tree[now][i];
int uu=find(u[x]),vv=find(v[x]);
if(uu==vv)
{
ok=1;
for(int j=l;j<=r;j++)
{
puts("No");
}
break;
}
merge(u[x]+N,vv);
merge(v[x]+N,uu);
}
if(!ok)
{
if(l==r)
{
puts("Yes");
}
else
{
int mid=l+r>>1;
dfs(now*2,l,mid);
dfs(now*2+1,mid+1,r);
}
}
while(s.size()>sz)
{
pii now=s.top();
s.pop();
dep[now.first]-=now.second;
fa[now.first]=now.first;
}
return;
}
int main()
{
n=read(),m=read(),k=read();
for(int i=1;i<=n*2;i++)
{
fa[i]=i;
}
for(int i=1;i<=m;i++)
{
u[i]=read(),v[i]=read(),l=read(),r=read();
if(l!=r)
{
update(1,1,k,l+1,r,i);
}
}
dfs(1,1,k);
return 0;
}
```
这是TLE 80 的完整代码
by Eason2009 @ 2022-10-28 22:05:35
dep 其实是 siz 吧,但是不知道为啥挂了,有没有复原的代码?
by 王熙文 @ 2022-10-28 22:05:47
@[Eason2009](/user/286448) 你按秩合并写成按大小合并,然后大小一开始都为 $0$,不 TLE 才怪呢。。。
by LJ07 @ 2022-10-28 22:08:00
这是AC代码:https://www.luogu.com.cn/paste/0kjtspex
by Eason2009 @ 2022-10-28 22:08:03
[改了改,ac 了](https://www.luogu.com.cn/record/91964129)
by 王熙文 @ 2022-10-28 22:09:01
首先 merge 里没有 find 到祖先,其次在复原的时候应该传一个 u 的参数因为 depu 要减去 depv,最后 siz 最初应该赋值为 1
by 王熙文 @ 2022-10-28 22:09:43
@[王熙文](/user/353688) 能放一下代码吗/bx
by Eason2009 @ 2022-10-28 22:10:11
@[Eason2009](/user/286448) [code](https://www.luogu.com.cn/paste/rffh9znc)
by 王熙文 @ 2022-10-28 22:11:22