Extending Set of Points[CF1140F][并查集]

题目

Luogu

思路

没什么可说的，线段树分治，观察是单点查询和区间修改就能统一处理询问
将点视为行和列的连接，那么就能和题目中扩展操作符合
注意这里方案数是并查集内的 $cntx?cnty$ ，并查集带撤回
以前打Atcoder最后一道题就是这个套路…没见过，然后就把它记着了

代码

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstring>
#include<climits>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
//char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf;
inline LL read() {
    bool f=0;LL x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c==EOF)exit(0);if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;
}
#define lch (rt<<1)
#define rch (rt<<1|1)
#define MAXN 600000
#define mp make_pair
#define INF 0x3f3f3f3f
#define pii pair<int,int>
vector<pii > tree[5*MAXN+5];
void Insert(int rt,int L,int R,int qL,int qR,pii x){
    if(qL<=L&&R<=qR){
    tree[rt].push_back(x);return ;}int Mid=(L+R)>>1;if(qL<=Mid)Insert(lch,L,Mid,qL,qR,x);if(Mid+1<=qR)Insert(rch,Mid+1,R,qL,qR,x);return ;
}
struct node{
    int u,v,dep,sizx,sizy;
}Stk[MAXN+5];
LL ans[MAXN+5],sum;
int tp,fa[MAXN+5],dep[MAXN+5],sizx[MAXN+5],sizy[MAXN+5];
int Find(int u){
    return fa[u]==u?u:Find(fa[u]);}
LL Cal(int u){
    return 1ll*sizx[u]*sizy[u];}
void Merge(int u,int v){
    u=Find(u),v=Find(v);if(u==v) return ;if(dep[u]<dep[v])swap(u,v);Stk[++tp]=(node){
    u,v,dep[u],sizx[u],sizy[u]};if(dep[u]==dep[v])dep[u]++;sum-=Cal(u)+Cal(v);fa[v]=u,sizx[u]+=sizx[v],sizy[u]+=sizy[v];sum+=Cal(u);return ;
}
void Restore(int ntp){
    while(tp>ntp){
    int u=Stk[tp].u,v=Stk[tp].v;sum-=Cal(u);fa[v]=v,dep[u]=Stk[tp].dep;sizx[u]=Stk[tp].sizx,sizy[u]=Stk[tp].sizy;sum+=Cal(u)+Cal(v),tp--;}return ;
}
void DFS(int rt,int L,int R){
    int ntp=tp;for(int i=0;i<(int)tree[rt].size();i++){
    int u=tree[rt][i].first,v=tree[rt][i].second;Merge(u,v);}if(L==R){
    ans[L]=sum;Restore(ntp);return ;}int Mid=(L+R)>>1;DFS(lch,L,Mid),DFS(rch,Mid+1,R);Restore(ntp);return ;
}
map<pii,int>Map;
int main(){
    int n=read();for(int i=1;i<=n;i++)fa[i]=i,sizx[i]=1;for(int i=n+1;i<=2*n;i++)fa[i]=i,sizy[i]=1;for(int i=1;i<=n;i++){
    int u=read(),v=n+read();if(Map[mp(u,v)])Insert(1,1,n,Map[mp(u,v)],i-1,mp(u,v)),Map.erase(mp(u,v));else Map[mp(u,v)]=i;}for(map<pii,int>::iterator it=Map.begin();it!=Map.end();it++)Insert(1,1,n,it->second,n,it->first);DFS(1,1,n);for(int i=1;i<=n;i++)printf("%lld ",ans[i]);return 0;
}