对于一个点集 S ,定义 E(S) 为以下算法的结果:
如果 S 中存在 (x1, y1),(x1, y2),(x2, y1),并且不存在 (x2, y2)(x2,y2),那么把 (x2, y2) 加入点集。
循环这个操作直到不能做为止。
现在让你维护一个点集,支持插入删除,要求每次操作之后算出 E(S) 的大小。
q \leq 3 \times 10^5,\ 1 \leq x, y \leq 3 \times 10^5

考虑分别将行列建虚点,集合中每个店 (x,y) 就从左边的 x 号点向右边的 y 号点连边,则答案为每个联通块左边点的个数乘以右边点的个数。

加入点可以直接添加到并查集中,用线段树分治维护删除操作。其中并查集需要按秩合并。

时间复杂度 O(n \log^2 n)

#include<bits/stdc++.h>
template<class T> inline void read(T &x){
    x=0; register char c=getchar(); register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
template<class T> inline void print(T x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10); putchar(x%10+'0');
}
const int N=3e5+10;
int n; long long ans,out[N];
std::map<std::pair<int,int>,int> map;
struct info{int x,y,l,r;}; std::vector<info> q;
struct node{int u,l,r,mid; std::vector<std::pair<int,int>> vet;}p[N<<2];
struct atom{int f,a,b; long long s(){return (long long)a*b;}}f[N<<1];
int find(int x){return f[x].f==x?x:find(f[x].f);}
void merge(int u,int v,std::vector<std::pair<int,atom>> &rub){ // $u merge to $v
    // printf("merge %d[%d] %d[%d]\n",u,find(u),v,find(v));
    u=find(u),v=find(v); if(u==v)return; if(f[u].a+f[u].b>f[v].a+f[v].b)std::swap(u,v);
    ans-=f[u].s(),rub.push_back(std::make_pair(u,f[u]));
    ans-=f[v].s(),rub.push_back(std::make_pair(v,f[v]));
    f[u].f=v,f[v].a+=f[u].a,f[v].b+=f[u].b,ans+=f[v].s();
    // printf("-> %d %d : %lld\n",f[v].a,f[v].b,f[v].s());
}
void build(int u,int l,int r){
    p[u].l=l,p[u].r=r,p[u].mid=(l+r)>>1; if(l==r)return;
    build(u<<1,l,p[u].mid),build(u<<1|1,p[u].mid+1,r);
}
void insert(int u,int l,int r,std::pair<int,int> v){
    // if(u==1)printf("insert %d[%d %d] %d %d : %d %d\n",u,p[u].l,p[u].r,l,r,v.first,v.second);
    if(p[u].l==l&&p[u].r==r){p[u].vet.push_back(v);return;}
    if(r<=p[u].mid)insert(u<<1,l,r,v);
    else if(l>p[u].mid)insert(u<<1|1,l,r,v);
    else insert(u<<1,l,p[u].mid,v),insert(u<<1|1,p[u].mid+1,r,v);
}
void dfs(int u){
    // printf("dfs %d[%d %d]\n",u,p[u].l,p[u].r);
    std::vector<std::pair<int,atom>> rub; long long rubans=ans;
    for(const auto &x:p[u].vet)merge(x.first,x.second+N,rub);
    if(p[u].l==p[u].r)out[p[u].l]=ans; else dfs(u<<1),dfs(u<<1|1);
    for(const auto &x:(std::reverse(rub.begin(),rub.end()),rub))f[x.first]=x.second; ans=rubans;
}
int main(){
#ifdef memset0
    freopen("1.in","r",stdin);
#endif
    for(int i=0;i<N;i++)f[i]={i,1,0},f[i+N]={i+N,0,1};
    read(n);
    for(int x,y,i=1;i<=n;i++){
        read(x),read(y); auto it=std::make_pair(x,y);
        map[it]?(q.push_back({x,y,map[it],i-1}),map[it]=0):(map[it]=i);
    }
    for(const auto &it:map)if(it.second)q.push_back({it.first.first,it.first.second,it.second,n});
    build(1,1,n);
    for(const auto &it:q)insert(1,it.l,it.r,std::make_pair(it.x,it.y));
    dfs(1);
    for(int i=1;i<=n;i++)print(out[i]),putchar(' ');
}
Categories: OI

0 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *