题意:初始有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。
参考博客:http://www.pianshen.com/article/600592796/
https://blog.csdn.net/ccsu_cat/article/details/83376921
线段树动态开点参考: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;
}