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

骑猪看日落 2022-04-25 09:12 144阅读 0赞

## 题意：有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][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;
    }

[https_blog.csdn.net_u013534123_article_details_89010251]: https://blog.csdn.net/u013534123/article/details/89010251