题解：AT_abc424_f [ABC424F] Adding Chords

喜欢我们绿题拿和线段树差不多长的 1.2KB 树套树无脑场切掉吗？

但是真的可以拿树套树过，而且很快就能写完，虽然复杂度劣一点，不过我的树套树时限三秒能飞到一秒内。

注意到这个问题其实和环没啥关系，可以把它转化成在一条链上做。

然后画一下图就可以发现，一条新边不合法当且仅当它包含的区间有边连到外面的点，我们可以统计一下这种边的数量。

那么就只用树套树维护每个点连到后面各个点的边，然后加边时查询 \((1,l-1)\to (l+1,r-1)\) 以及 \((l+1,r-1)\to (r+1,n)\) 的边数是否为 \(0\) 即可，如果 \(l+1=r\) 直接默认加边，如果合法就在树套树上修改。

感觉树套树做法的代码一眼就能看出是在干啥吧。

#include<bits/stdc++.h>
#define N 1000005
using namespace std;
int cnt=0,n,q;
int lowbit(int u){return u&-u;}
struct Ty{int val,l,r;}y[N*75];
struct Ig{int root;void update(int &u,int l,int r,int id){if(!u)u=++cnt;y[u].val++;if(l==r&&l==id)return;int mid=(l+r)/2;if(id<=mid)update(y[u].l,l,mid,id);else update(y[u].r,mid+1,r,id);return;}int query(int u,int l,int r,int fl,int fr){if(!u)return 0;if(l==fl&&r==fr)return y[u].val;int mid=(l+r)/2;if(fr<=mid)return query(y[u].l,l,mid,fl,fr);else if(fl>mid)return query(y[u].r,mid+1,r,fl,fr);else return query(y[u].l,l,mid,fl,mid)+query(y[u].r,mid+1,r,mid+1,fr);}
}w[N];
void update(int u,int v){for(int i=u;i<=n;i+=lowbit(i))w[i].update(w[i].root,1,n,v);return;
}
int query(int u,int l,int r){int now=0;for(int i=u;i;i-=lowbit(i))now+=w[i].query(w[i].root,1,n,l,r);return now;
}
signed main(){scanf("%d%d",&n,&q);for(int i=1;i<=q;i++){int u,v;scanf("%d%d",&u,&v);if(u+1==v){printf("Yes\n");continue;}int flag=query(u-1,u+1,v-1)+query(v-1,v+1,n)-query(u,v+1,n);if(flag>0){printf("No\n");continue;}update(u,v);printf("Yes\n");}return 0;
}