題目鏈接：點(diǎn)擊查看

題目大意：給出 $n$ 個(gè)點(diǎn)，初始時(shí)互相不存在連邊，需要執(zhí)行 $m$ 次操作，每次操作分為兩種類型：

$1xy$：如果 $(x,y)$ 之間沒(méi)有連邊，則增加連邊；如果 $(x,y)$ 之間存在連邊，則刪除連邊

$2xy$：詢問(wèn)點(diǎn) $x$ 和點(diǎn) $y$ 之間是否聯(lián)通

詢問(wèn)需要強(qiáng)制在線

題目分析：關(guān)于強(qiáng)制在線實(shí)現(xiàn)連邊與加邊，如果是在樹(shù)上進(jìn)行的話可以用 $LCT$，但如果放在圖上的話好像是可以用 $ETT$，不過(guò)這個(gè)題目需要看出這個(gè)強(qiáng)制在線是個(gè)假的，所以可以離線去做

之前做過(guò)一道類似的題目：牛客多校8 - All-Star Game

所以這個(gè)題目考慮用線段樹(shù)分治離線去做，將每個(gè)節(jié)點(diǎn)視為詢問(wèn)的時(shí)間點(diǎn)，遞歸的時(shí)候?qū)崿F(xiàn)并查集的加邊，回溯的時(shí)候?qū)崿F(xiàn)并查集的撤銷即可，訪問(wèn)到葉子節(jié)點(diǎn)時(shí)回答每個(gè)詢問(wèn)并且更新后續(xù)的詢問(wèn)

然后關(guān)鍵點(diǎn)就是如何將題目轉(zhuǎn)換成離線去做，因?yàn)?strong>上一次的答案只可能為 $0$ 或 $1$，所以對(duì)于一對(duì)詢問(wèn) $(x,y)$ 來(lái)說(shuō)，只可能是 $(x,y)$ 或 $(x\mathrm{m}\mathrm{o}\mathrm{d}n+1,y\mathrm{m}\mathrm{o}\mathrm{d}n+1)$，對(duì)于操作二的話無(wú)傷大雅，直接存起來(lái)下面會(huì)講如何更新，而對(duì)于操作一來(lái)說(shuō)，線段樹(shù)分治的本質(zhì)就是將 $(x,y)$ 這條邊的出現(xiàn)時(shí)間到刪除時(shí)間的這段區(qū)間打上標(biāo)記，所以我們可以在讀入時(shí)就將所有的 $(x,y)$ 點(diǎn)對(duì)都?jí)喝氲骄€段樹(shù)中

舉個(gè)很簡(jiǎn)單的例子，假設(shè) $(x,y)$ 這條邊的出現(xiàn)位置共有三次，分別是 $t_1,t_2,t_3$，我們先不用管哪個(gè)時(shí)間點(diǎn)是刪除，哪個(gè)時(shí)間點(diǎn)是增加，直接將所有的連續(xù)區(qū)間都打上標(biāo)記，諸如：$[t_1,t_2],[t_2,t_3],[t_3,m]$（ $m$ 是詢問(wèn)的個(gè)數(shù)，相當(dāng)于最后的一個(gè)時(shí)間點(diǎn)），然后在分治的過(guò)程中，根據(jù)實(shí)際的詢問(wèn)去選擇是否加邊

最后說(shuō)一下如何實(shí)時(shí)更新出實(shí)際的詢問(wèn)以及加邊，因?yàn)榫€段樹(shù)遞歸到葉子節(jié)點(diǎn)的順序一定是從左到右下去的，所以當(dāng)遞歸到葉子節(jié)點(diǎn) $x$ 時(shí)，$x?1$ 一定結(jié)束了，且 $x+1$ 一定還沒(méi)有被訪問(wèn)過(guò)，利用這個(gè)特點(diǎn)每次詢問(wèn)完葉子節(jié)點(diǎn) $x$ 后可以順便將 $x+1$ 位置的詢問(wèn)更新一下

代碼：

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=2e5+100; struct{int op,x,y;}q[N]; map<pair<int,int>,int>mp; int f[N],rk[N],ans[N],last,n,m; struct revo {int fax,fay;int rkx,rky; }; struct Node {int l,r;vector<pair<int,int>>node;//位于[l,r]這段時(shí)間內(nèi)的邊有哪些 }tree[N<<2]; int find(int x){return f[x]==x?x:find(f[x]);} revo merge(int x,int y)//并查集的合并，返回合并之前的信息revo用于撤銷 {revo ans;int xx=find(x),yy=find(y);ans.fax=xx,ans.fay=yy;ans.rkx=rk[xx],ans.rky=rk[yy];if(xx!=yy){if(rk[xx]>rk[yy]) swap(xx,yy);f[xx]=yy;rk[yy]=max(rk[yy],rk[xx]+1);}return ans; } void revocation(stack<revo>&st)//并查集的撤銷，將并查集恢復(fù)至node狀態(tài) {while(st.size()){revo a=st.top();f[a.fax]=a.fax,f[a.fay]=a.fay;rk[a.fax]=a.rkx,rk[a.fay]=a.rky;st.pop();} } void build(int k,int l,int r) {tree[k].l=l,tree[k].r=r;if(l==r) return;int mid=(l+r)>>1;build(k<<1,l,mid),build(k<<1|1,mid+1,r); } void update(int k,int l,int r,pair<int,int>val) {if(l>r) return;if(tree[k].l>r||tree[k].r<l) return;if(tree[k].l>=l&&tree[k].r<=r){tree[k].node.push_back(val);return;}update(k<<1,l,r,val),update(k<<1|1,l,r,val); } void dfs(int k)//線段樹(shù)分治 {stack<revo>st;for(auto it:tree[k].node) if(mp[it]) st.push(merge(it.first,it.second));//并查集的合并if(tree[k].l==tree[k].r){int id=tree[k].l;if(q[id].op==2) last=ans[id]=(find(q[id].x)==find(q[id].y));q[id+1].x=(q[id+1].x+last-1)%n+1,q[id+1].y=(q[id+1].y+last-1)%n+1;if(q[id+1].x>q[id+1].y) swap(q[id+1].x,q[id+1].y);if(q[id+1].op==1) mp[{q[id+1].x,q[id+1].y}]^=1;revocation(st);return;}else dfs(k<<1),dfs(k<<1|1);revocation(st); } void init(){for(int i=1;i<N;i++) f[i]=i,rk[i]=1;} int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);init();read(n),read(m);build(1,1,m);for(int i=1,x,y,op;i<=m;i++){read(op),read(x),read(y);q[i]={op,x,y};if(op==2) continue;if(x>y) swap(x,y);if(mp[{x,y}]) update(1,mp[{x,y}],i,{x,y});mp[{x,y}]=i;x=x%n+1,y=y%n+1;if(x>y) swap(x,y);if(mp[{x,y}]) update(1,mp[{x,y}],i,{x,y});mp[{x,y}]=i;}for(auto it:mp) update(1,it.second,m,it.first);mp.clear();if(q[1].op==1) mp[{min(q[1].x,q[1].y),max(q[1].x,q[1].y)}]=1;memset(ans,-1,sizeof(ans));dfs(1);for(int i=1;i<=m;i++) if(ans[i]!=-1) write(ans[i]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1217F Forced Online Queries Problem(线段树分治+并查集撤销)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。