Educational Codeforces Round 62 F. Extending Set of Points 线段树分治+可撤销并查集

本文主要是介绍Educational Codeforces Round 62 F. Extending Set of Points 线段树分治+可撤销并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：有q次操作，每次操作 (x ,y)，如果S集合有(x ,y)，就删除这对数，如果没有就插入这对数，然后询问S集合在R规则下一共有多少对数（R规则：如果R集合中有(x1,y1) (x1,y2)(x2,y1)，且没有(x2,y2)，那么在计数的时候会加上(x2,y2)这对）。

思路：

我们仔细分析这个点加入的条件，很容易可以发现，对于一个点(x,y)，相当于把第x行和第y列给合并。最后的答案就是每个连通块内的行数与列数的乘积和。所以我们要维护的相当于就是行与列的合并，并且统计连通块中的行数与列数。这个用并查集去做即可。并查集合并计算贡献说明一下，举个例子，第一个集合的x有1 2，y有3 4，第二个集合x有3 4，y有5 6 7，原来两个集合贡献是2×2＋2×3＝10，现在你要把两个集合合并，就要先减去10加上4×5，撤销同理。

但是，注意到本题的点可以删除，直接并查集肯定是不行的。这里，我们用到了线段树的一种新姿势，本质上也是一种离线处理的方法，其实类似的做法以前也见过，但是没想到可以用在线段树上。对于n次的加入或者删除点的操作，我们可以用一棵线段树把它进行一个划分，注意这里的线段树仅仅是起到划分的作用，不维护区间的最值或者和。然后，对于一个插入点的操作，如果这个点后面会被删除，那么相当于这个点的存在周期是一个区间。于是，对应的，我们可以把这个区间在线段树中找到，把这个点放到对应区间的节点上面。如果后面没被删除，那么这个点存在的周期就是从出现到最后，同样也可以放到相应节点上面。

把每个点放到相应区间节点上之后，我们就可以进行dfs了。从根开始往下走，每走到一个节点，把节点上面存的点插入，也即合并点的行列。因为往下的区间都包含于上面的区间，这样当走到叶子节点后，当时的答案就是对应时刻的答案。而当一条分支走完之后，需要恢复原本的操作，把原本的合并重新删除。

参考博客：https://blog.csdn.net/u013534123/article/details/89010251

 

代码：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 600010;
int f[N],cntx[N],cnty[N],sz[N],n;
typedef pair<int,int> PII;
vector<PII> T[N<<2];
map<PII,int> mp;
LL ans[N],res=0;
///插入线段树相应区间
void ins(int i,int l,int r,int L,int R,PII tmp){if (l==L&&R==r){T[i].push_back(tmp);return;}int mid=(L+R)>>1;if (mid>=r) ins(i<<1,l,r,L,mid,tmp);else if (mid<l) ins(i<<1|1,l,r,mid+1,R,tmp);else{ins(i<<1,l,mid,L,mid,tmp);ins(i<<1|1,mid+1,r,mid+1,R,tmp);}
}inline int find(int x){return f[x]==x?x:find(f[x]);
}
///并查集合并 + 计算贡献
inline void Merge(int x,int y,stack<PII> &st){x=find(x),y=find(y);if (x!=y){if (sz[x]<sz[y]) swap(x,y);st.push(PII(x,y));res-=(LL)cntx[x]*cnty[x];res-=(LL)cntx[y]*cnty[y];sz[x]+=sz[y]; f[y]=x;cntx[x]+=cntx[y];cnty[x]+=cnty[y];res+=(LL)cntx[x]*cnty[x];}
}
///删除贡献
inline void Delete(stack<PII> &st){while(!st.empty()){int x=st.top().first;int y=st.top().second;res-=(LL)cntx[x]*cnty[x];f[y]=y; st.pop();sz[x]-=sz[y];cntx[x]-=cntx[y];cnty[x]-=cnty[y];res+=(LL)cntx[x]*cnty[x];res+=(LL)cntx[y]*cnty[y];}
}
///线段树上搜索，离线处理所有询问
void dfs(int i,int l,int r){stack<PII> st;for(int j=0;j<T[i].size();j++)Merge(T[i][j].first,T[i][j].second,st);if (l==r) ans[l]=res;else{int mid=(l+r)>>1;dfs(i<<1,l,mid);dfs(i<<1|1,mid+1,r);}Delete(st);
}int main(){scanf("%d",&n);for(int i=1;i<=n;i++){int x,y;scanf("%d%d",&x,&y);PII tmp=PII(x,y+300000);if (!mp[tmp]) mp[tmp]=i;else{ins(1,mp[tmp],i-1,1,n,tmp);mp.erase(tmp);}}for(auto x:mp)ins(1,x.second,n,1,n,x.first);for(int i=1;i<=300000;i++)f[i]=i,cntx[i]=sz[i]=1;for(int i=300001;i<=600000;i++)f[i]=i,cnty[i]=sz[i]=1;dfs(1,1,n);for(int i=1;i<=n;i++)printf("%lld%c",ans[i]," \n"[i==n]);return 0;
}

 

这篇关于Educational Codeforces Round 62 F. Extending Set of Points 线段树分治+可撤销并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---