本文主要是介绍Codeforces 1217 F. Forced Online Queries Problem —— 又见 线段树分治+并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
This way
题意：
每次给你两个操作：
1 x y 表示加/断点x和点y之间的连边
2 x y 问你x和y是否连通
题解：
在线的做法好像是什么ETT？不是很懂
这题是个假的强制在线，只需要一开始将所有情况处理出来放到线段树里面，dfs线段树的时候查看当前操作是否合法即可。
那么又是将询问当做叶子结点，操作当做区间更新，然后向下dfs的时候更新一下并查集即可。
#include<bits/stdc++.h>
using namespace std;
#define pa pair<int,int>
const int N=2e5+5;
vector<pa>vec[N*4];
int fa[N],siz[N];
int finds(int x){return x==fa[x]?fa[x]:finds(fa[x]);}
void add(int x,int y,stack<pa>& s){int fax=finds(x),fay=finds(y);if(fax==fay)return ;if(siz[fax]<siz[fay])swap(fax,fay);fa[fay]=fax;siz[fax]+=fay;s.push({fax,fay});
}
void del(stack<pa>& s){while(!s.empty()){int fax=s.top().first,fay=s.top().second;siz[fax]-=siz[fay];fa[fay]=fay;s.pop();}
}
int ls;
void update(int l,int r,int root,int ql,int qr,pa v){if(l>=ql&&r<=qr){vec[root].push_back(v);return ;}int mid=l+r>>1;if(mid>=ql)update(l,mid,root<<1,ql,qr,v);if(mid<qr)update(mid+1,r,root<<1|1,ql,qr,v);
}
int ans[N],n,m;
map<pa,int>mp;struct node{int op,x,y;
}e[N];
void dfs(int l,int r,int root){stack<pa>s;for(pa u:vec[root])if(mp[u]!=0)add(u.first,u.second,s);if(l==r){if(e[l].op==2)ans[l]=ls=finds(e[l].x)==finds(e[l].y);e[l+1].x=(e[l+1].x+ls-1)%n+1,e[l+1].y=(e[l+1].y+ls-1)%n+1;if(e[l+1].x>e[l+1].y)swap(e[l+1].x,e[l+1].y);if(e[l+1].op==1)mp[{e[l+1].x,e[l+1].y}]^=1,mp[{e[l+1].y,e[l+1].x}]^=1;del(s);return ;}int mid=l+r>>1;dfs(l,mid,root<<1),dfs(mid+1,r,root<<1|1);del(s);
}
int main()
{for(int i=1;i<N;i++)fa[i]=i;int x,y,op;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&op,&x,&y),e[i]={op,x,y};if(op==2)continue;//printf("%d\n",mp[{x,y}]);if(mp[{x,y}])update(1,m,1,mp[{x,y}],i,{x,y}),mp[{x,y}]=mp[{y,x}]=i+1;else mp[{x,y}]=mp[{y,x}]=i;x=x%n+1,y=y%n+1;if(x>y)swap(x,y);//printf("%d\n",mp[{x,y}]);if(mp[{x,y}])update(1,m,1,mp[{x,y}],i,{x,y}),mp[{x,y}]=mp[{y,x}]=i+1;else mp[{x,y}]=mp[{y,x}]=i;}for(map<pa,int>::iterator it=mp.begin();it!=mp.end();it++)if(it->second<=m)update(1,m,1,it->second,m,it->first);mp.clear();if(e[1].op==1)mp[{e[1].x,e[1].y}]=mp[{e[1].y,e[1].x}]=1;memset(ans,-1,sizeof(ans));dfs(1,m,1);for(int i=1;i<=m;i++)if(~ans[i])printf("%d",ans[i]);printf("\n");return 0;
}
这篇关于Codeforces 1217 F. Forced Online Queries Problem —— 又见 线段树分治+并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
