CF1140F Extending Set of Points

一看到二维点之间的关系，首先考虑下转化成二分图的形式。即左边的点代表行，右边的点代表列，二分图的边代表原图上的点。题目描述的规则就变成了：对于任意一条边连接的点对$a,b$，与$a$点之间有边的点集为$A$，与$b$点之间有边的点集为$B$。 那么点集$A$和$B$中的点必定两两有边。所以对于一个二分图上连通块，二分图两边的点必定有边。

因为题意中的点是一个一个加入的，那就相当于每次加入一条边。我们只需要合并这两个边连接的连通块就好了。因为我们需要数二分图有多少边，所以我们需要只需要维护一下一个连通块左边和右边分别有多少个点即可。

问题转化为了：每次加边/删边，询问连通块的一些信息。那么显然用一个按秩合并可撤销并查集+线段树分治即可。

/*
                                                  
  _|_|                              _|  _|    _|  
_|    _|  _|  _|_|  _|_|_|_|        _|  _|  _|    
_|    _|  _|_|          _|          _|  _|_|      
_|    _|  _|          _|      _|    _|  _|  _|    
  _|_|    _|        _|_|_|_|    _|_|    _|    _|  
                                                                                                    
*/ 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#include<map>
#define ls (rt<<1)
#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=3e5+1000;
map<pii,int>lst;
ll tmpans;
struct dsu{
	int fa[2*maxn],size[2*maxn],rowsize[2*maxn],colsize[2*maxn];
	//row points idx :i
	//col  points idx:i+maxn 
	pii his[maxn];//<son,fa>
	int top;
	dsu(){
		top=0;
		rep(i,0,maxn*2-1)fa[i]=i,size[i]=1;
		rep(i,1,maxn)rowsize[i]=1,colsize[i+maxn]=1;
	}
	int get(int x){return (fa[x]==x)?x:get(fa[x]);}
	void merge(int s,int f){
		s=get(s),f=get(f);
		if(size[s]>size[f])swap(s,f);
		tmpans-=1ll*rowsize[f]*colsize[f]+1ll*rowsize[s]*colsize[s];
		size[f]+=size[s];rowsize[f]+=rowsize[s];colsize[f]+=colsize[s];
		tmpans+=1ll*rowsize[f]*colsize[f];
		fa[s]=f;his[++top]=mk(s,f);
	}
	void roll_back(int n){
		rep(i,1,n){
			int f=his[top].se,s=his[top].fi;top--;
			tmpans-=1ll*rowsize[f]*colsize[f];
			size[f]-=size[s];rowsize[f]-=rowsize[s];colsize[f]-=colsize[s];
			tmpans+=1ll*rowsize[f]*colsize[f]+1ll*rowsize[s]*colsize[s];
			fa[s]=s;
		}
	}
}d;
ll ans[maxn];

struct segment_tree{
	vector<pii> tag[maxn<<2];
	void add_op(int l,int r,int rt,int tl,int tr,pii val){
		if(tl<=l&&r<=tr){
			tag[rt].pb(val);return;
		}
		int mid=(l+r)>>1;
		if(tl<=mid)add_op(l,mid,ls,tl,tr,val);
		if(tr>=mid+1)add_op(mid+1,r,rs,tl,tr,val);
	}
	void vamos(int l,int r,int rt){
		int cnt=0;
	//	cout<<"IN:"<<l<<' '<<r<<' '<<tmpans<<endl;
		for(int i=0;i<tag[rt].size();i++){
			pii tmp=tag[rt][i];
			if(d.get(tmp.fi)!=d.get(tmp.se+maxn)){
				d.merge(tmp.fi,tmp.se+maxn);cnt++;
			}
		}
		if(l==r){ans[l]=tmpans;d.roll_back(cnt);return;}
		int mid=(l+r)>>1;
		vamos(l,mid,ls);
		vamos(mid+1,r,rs);
		d.roll_back(cnt);
		//cout<<"OUT:"<<l<<' '<<r<<' '<<tmpans<<endl;
		int gg=1;
	}
}t;
vector<pii>res;
int main(){
	ios::sync_with_stdio(0);
	int q;cin>>q;
	rep(i,1,q){
		pii tmp;cin>>tmp.fi>>tmp.se;res.pb(tmp);
		if(lst[tmp]){
			t.add_op(1,q,1,lst[tmp],i-1,tmp);
			lst[tmp]=0;
		}else{
			lst[tmp]=i;
		}
	}
	for(int i=0;i<res.size();i++){
		pii tmp=res[i];
		if(lst[tmp]){
			t.add_op(1,q,1,lst[tmp],q,tmp);
			lst[tmp]=0;
		}
	}
	t.vamos(1,q,1);
	rep(i,1,q)cout<<ans[i]<<' ';
	return 0;
}