2167: Grid

Submit Page  Summary    Time Limit: 2 Sec     Memory Limit: 128 Mb     Submitted: 203     Solved: 32    

---

Description

Bobo has n × m points arranged into a matrix with n rows and m columns. The points in the intersection of the i-th row and the j-th column is labeled with (i, j). He is going to perform q operations of the following 2 kinds.

1. Given parameters a, b, add edges between points (i, j) and (i, j + 1) for all a ≤ i ≤ b and 1 ≤ j < m.
2. Given parameters a, b, add edges between points (i, j) and (i + 1, j) for all 1 ≤ i < n and a ≤ j ≤ b.

Bobo would like to know the number of connected components after each operation.

• 1 ≤ n, m ≤ 109
• 1 ≤ q ≤ 105
• ti ∈ {1, 2}
• If ti = 1, 1 ≤ ai ≤ bi ≤ n. If ti = 2, 1 ≤ ai ≤ bi ≤ m.
• The sum of q does not exceed 5 × 105.

Input

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains three integers n, m and q.

The i-th of the following q lines contains three integers ti, ai and bi where ti is the kind of the operation i and ai, bi are corresponding parameters.

Output

For each test case, print q integers which denote the number of connected components after each operation.

Sample Input

2 3 3
2 1 1
2 3 3
1 1 1
1000000000 1000000000 1
1 1 2

Sample Output

5
4
2
999999998000000002

Hint

Source

2018湖南省第14届大学生计算机程序设计竞赛

Author

ftiasch

今天学习了如何动态开点的线段树，感觉好妙啊，普通的线段树会由于数组大小的限制到达不了1e9，而这里正好需要从1到1e9且不能离散化。于是采用了动态开点，类似于主席树方法给每个节点赋值。只要更新的节点不会超过很多就可以了。

普通的线段树是这样的：

而动态开点后：

贴AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int s1[N],ls[N],rs[N],cnt1,rt1;
int s2[N],ls2[N],rs2[N],cnt2,rt2;
int n,m,q;
void init()
{
	for(int i=0;i<=cnt1;i++)
		s1[i]=ls[i]=rs[i]=0;
	for(int i=0;i<=cnt2;i++)
		s2[i]=ls2[i]=rs2[i]=0;
	cnt1=cnt2=rt1=rt2=0;
}
void up1(int &o,int l,int r,int ql,int qr)
{
	if(!o) o=++cnt1;
	if(s1[o]==r-l+1) return ;
	if(ql<=l&&r<=qr)
	{
		s1[o]=r-l+1;
		return ;
	}
	int mid=l+r>>1;
	if(ql<=mid) up1(ls[o],l,mid,ql,qr);
	if(qr>mid) up1(rs[o],mid+1,r,ql,qr);
	s1[o]=s1[ls[o]]+s1[rs[o]];
}

void up2(int &o,int l,int r,int ql,int qr)
{
	if(!o) o=++cnt2;
	if(s2[o]==r-l+1) return ;
	if(ql<=l&&r<=qr)
	{
		s2[o]=r-l+1;
		return ;
	}
	int mid=r+l>>1;
	if(ql<=mid) up2(ls2[o],l,mid,ql,qr);
	if(qr>mid) up2(rs2[o],mid+1,r,ql,qr);
	s2[o]=s2[ls2[o]]+s2[rs2[o]];
}
int main()
{
	while(~scanf("%d%d%d",&n,&m,&q))
	{
		init();
		while(q--)
		{
			int op,l,r;
			scanf("%d%d%d",&op,&l,&r);
			if(op==1)up1(rt1,1,n,l,r);
			else up2(rt2,1,m,l,r);
			ll ans;
			if(s1[1]==0) ans=1ll*(m-s2[1])*n+s2[1];
			if(s2[1]==0) ans=1ll*(n-s1[1])*m+s1[1];
			if(s1[1]!=0&&s2[1]!=0)
			{
				ans=1ll*n*m-(1ll*s1[1]*m+1ll*s2[1]*n-1ll*s1[1]*s2[1])+1;
			}
			printf("%lld\n",ans);
		}
	}
}