CSU 2167

电玩女神 2022-01-26 14:55 203阅读 0赞

## 题意：初始有n\*m的点，矩形排列。有2种操作，第一种是将第i行的所有点联通（a<=i<=b）,第二种是将第i列的所有点联通（a<=i<=b）。每次操作后输出有多少个联通块。 ##

## 分析：在纸上画一下图，可以发现答案跟a,b所跨水平和垂直区间有关，如图，假设nn为水平方向所占用的区间，mm为垂直方向所占的区间，且共有n行m列，则它是把mm×m+nn×n-nn×mm个点连通成一个点，所以答案ans=n×m-(mm×m+nn×n-nn×mm)+1=n×m-mm×m-nn×n+nn×mm+1,但注意当水平方向占的区间为0时，是将mm行的点连通成mm个点，即mm×m个点连通成mm个点,此时ans=n×m-mm×m+mm,当垂直方向区间为0时也可想而知。普通线段树来统计空间肯定不行，可以用动态开点解决，每次更新最多新开几十个节点的空间，1e5次更新，最多只需几百万的空间足够，解决了这个问题就是水题了。这题也可以用离散化+线段树来做，不过麻烦一点，可以参考[https://blog.csdn.net/nudt\_spy/article/details/82682090][https_blog.csdn.net_nudt_spy_article_details_82682090]。 ##

![å¨è¿éæå¥å¾çæè¿°][d863db4e7ab38eab4e1461092dc24378.png]

## 参考博客：[http://www.pianshen.com/article/600592796/][http_www.pianshen.com_article_600592796] ##

## [https://blog.csdn.net/ccsu\_cat/article/details/83376921][https_blog.csdn.net_ccsu_cat_article_details_83376921] ##

## 线段树动态开点参考：[https://www.cnblogs.com/Miracevin/p/9582486.html][https_www.cnblogs.com_Miracevin_p_9582486.html] ##

## 动态开点的思想和主席树很像。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N = 2e6;
    int ls1[N],ls2[N],rs1[N],rs2[N],s1[N],s2[N];
    int n,m,q,op,a,b,ct1,ct2,rt1,rt2;
    
    void up1(int& o,int l,int r,int ql,int qr) {
        if(!o) o=++ct1;
        if(s1[o]==r-l+1) return ;///已经全部连通则直接返回
        if(ql<=l&&qr>=r) {
            s1[o]=r-l+1;
            return ;
        }
        int m=(l+r)/2;
        if(ql<=m) up1(ls1[o],l,m,ql,qr);
        if(qr>m) up1(rs1[o],m+1,r,ql,qr);
        s1[o]=s1[ls1[o]]+s1[rs1[o]];
    }
    
    void up2(int& o,int l,int r,int ql,int qr) {
        if(!o) o=++ct2;
        if(s2[o]==r-l+1) return ;
        if(ql<=l&&qr>=r) {
            s2[o]=r-l+1;
            return ;
        }
        int m=(l+r)/2;
        if(ql<=m) up2(ls2[o],l,m,ql,qr);
        if(qr>m) up2(rs2[o],m+1,r,ql,qr);
        s2[o]=s2[ls2[o]]+s2[rs2[o]];
    }
    
    int main() {
        while(~scanf("%d%d%d",&n,&m,&q)) {
            rt1=rt2=ct1=ct2=0;
            while(q--) {
                scanf("%d%d%d",&op,&a,&b);
                ll res=0;
                if(op==1) {
                    up1(rt1,1,n,a,b);
                    ///容斥
                    if(s2[1]==0) res=1LL*n*m-1LL*s1[1]*(m-1);
                    else res=1LL*n*m-1LL*s1[1]*m-1LL*s2[1]*n+1LL*s1[1]*s2[1]+1;
                }else {
                    up2(rt2,1,m,a,b);
                    if(s1[1]==0) res=1LL*n*m-1LL*s2[1]*(n-1);
                    else res=1LL*n*m-1LL*s1[1]*m-1LL*s2[1]*n+1LL*s1[1]*s2[1]+1;
                }
                printf("%lld\n",res);
            }
            ///清空 用了多少清空多少
            for(int i=1;i<=ct1;i++) ls1[i]=rs1[i]=s1[i]=0;
            for(int i=1;i<=ct2;i++) ls2[i]=rs2[i]=s2[i]=0;
        }
        return 0;
    }

[https_blog.csdn.net_nudt_spy_article_details_82682090]: https://blog.csdn.net/nudt_spy/article/details/82682090
[d863db4e7ab38eab4e1461092dc24378.png]: http://www.pianshen.com/images/176/d863db4e7ab38eab4e1461092dc24378.png
[http_www.pianshen.com_article_600592796]: http://www.pianshen.com/article/600592796/
[https_blog.csdn.net_ccsu_cat_article_details_83376921]: https://blog.csdn.net/ccsu_cat/article/details/83376921
[https_www.cnblogs.com_Miracevin_p_9582486.html]: https://www.cnblogs.com/Miracevin/p/9582486.html