Description：

给一个网格，标记很多长或宽为 $1$ 的矩形，求前 $v$ 行有多少个标记的格子，以及这些格子形成了多少联通块。

$1\leqslant n\leqslant 10^5$

Solution：

第一问只要对于每行统计一下有多少楼盘，然后做个前缀和就可以 $O(1)$ 回答了。

第二问要麻烦一点，首先把所有矩形分成横着的和竖着的，然后分类讨论：

$1$ 、两个横着的在头或尾处相接。

$2$ 、两个横着的在相邻两行有公共边。

$3$ 、两个竖着的在头或尾处相接。

$4$ 、两个竖着的在相邻两列有公共边，

$5$ 、一个横着的和一个竖着的在横着的末端相接。

$6$ 、一个横着的和一个竖着的在竖着的末端相接。

对于 $1$ 和 $3$ 情况把所有矩形输入进来后能合并的合并，这样不会影响答案。

然后既然每次询问前几行，那么肯定是从上到下一行一行做，对于每一行，有三种情况：

$1$ 、有一个竖着的从这里开始。

$2$ 、有一个横着的在这一行。

$3$ 、有一个竖着的到这一行结束。

所以可以每行开三个桶，分别记录每行上述三个矩形的情况，到这一行时按照上面的顺序依次处理，同时维护一个 $set$ 记录当前有哪些竖着的矩形还没有结束，对于从这一行开始的竖着的，统计一下第 $4$ 类和第 $6$ 类的情况，也就是说在 $set$ 里查一下他相邻两列有没有矩形，在上一行的横着的桶中查一下有没有矩形和他相交，有的话就在并查集里把他们连起来，然后枚举这一行的横着的，统计一下第 $2,5,6$ 种情况，这个分别可以在上一行的横着的，在上一行结束的竖着的桶中和当前 $set$ 中查一下，最后把到这一行结束的竖着的删掉就行了，同时用一个并查集维护联通块个数，这样就预处理出了所有答案，也可以 $O(1)$ 回答。

分析一下会发现每一类统计均摊下来都是 $O(n\log n)$ 的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int id,n,m,k,q;

#define MAXN 100010

struct col

{

	int cx,cy1,cy2,id;

	bool operator < (col b)const

	{

		return cx < b.cx;

	}

}c[MAXN];

int totc = 0;

bool cmp_c(col a,col b)

{

	if(a.cx != b.cx)return a.cx < b.cx;

	else return a.cy1 < b.cy1;

}

bool cmp_c_pos(col a,col b)

{

	return a.cy1 < b.cy1;

}

set<col> en[MAXN],st[MAXN],cur_col;

struct row

{

	int rx1,rx2,ry,id;

	bool operator < (row b)const

	{

		return rx1 < b.rx1;

	}

}r[MAXN];

int totr = 0;

bool cmp_r(row a,row b)

{

	if(a.ry != b.ry)return a.ry < b.ry;

	else return a.rx1 < b.rx1;

}

set<row> rs[MAXN];

bool tag[MAXN];

int f[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

int cnt = 0;

void merge(int a,int b)

{

	int p = find(a),q = find(b);

	if(p == q)return;

	--cnt;

	f[p] = q;

	return;

}

long long ans1[MAXN];

int ans2[MAXN];

int main()

{

	freopen("building.in","r",stdin);

	freopen("building.out","w",stdout);

	scanf("%d%d%d%d%d",&id,&n,&m,&k,&q);

	int xx1,yy1,xx2,yy2;

	for(int i = 1;i <= k;++i)

	{

		yy1 = read();xx1 = read();yy2 = read();xx2 = read();

		if(xx1 > xx2)swap(xx1,xx2);

		if(yy1 > yy2)swap(yy1,yy2);

		if(xx1 == xx2)c[++totc] = (col){xx1,yy1,yy2,i};

		else r[++totr] = (row){xx1,xx2,yy1,i};

	}

	sort(c + 1,c + 1 + totc,cmp_c);

	sort(r + 1,r + 1 + totr,cmp_r);

	memset(tag,false,sizeof(tag));

	for(int i = 1;i <= totc;++i)

	{

		if(i != 1 && c[i].cx == c[i - 1].cx && c[i - 1].cy2 + 1 == c[i].cy1)

		{

			tag[i - 1] = true;

			c[i].cy1 = c[i - 1].cy1;

		}

	}

	long long tot = totc;totc = 0;

	for(int i = 1;i <= tot;++i)

		if(!tag[i])c[++totc] = c[i];

	memset(tag,false,sizeof(tag));

	for(int i = 1;i <= totr;++i)

	{

		if(i != 1 && r[i].ry == r[i - 1].ry && r[i - 1].rx2 + 1 == r[i].rx1)

		{

			tag[i - 1] = true;

			r[i].rx1 = r[i - 1].rx1;

		}

	}

	tot = totr;totr = 0;

	for(int i = 1;i <= tot;++i)

		if(!tag[i])r[++totr] = r[i];

	sort(c + 1,c + 1 + totc,cmp_c_pos);

	for(int i = 1;i <= totc;++i)

		en[c[i].cy2].insert(c[i]);

	for(int i = 1;i <= totc;++i)

		st[c[i].cy1].insert(c[i]);

	for(int i = 1;i <= totr;++i)

		rs[r[i].ry].insert(r[i]);

	for(int i = 1;i <= m;++i)en[i].insert((col){0x3f3f3f3f,0,0,0});

	for(int i = 1;i <= m;++i)rs[i].insert((row){0x3f3f3f3f,0,0,0});

	for(int i = 1;i <= k;++i)f[i] = i;

	tot = 0;

	for(int i = 1;i <= m;++i)

	{

		tot += cur_col.size();

		for(set<col>::iterator it = st[i].begin();it != st[i].end();++it)

		{

			if(it -> cx == 0x3f3f3f3f)continue;

			++cnt;++tot;

			set<col>::iterator bes;

			bes = cur_col.lower_bound((col){it -> cx + 1,0,0,0});

			if(bes != cur_col.end() && bes -> cx == it -> cx + 1)merge(it -> id,bes -> id);

			bes = cur_col.lower_bound((col){it -> cx - 1,0,0,0});

			if(bes != cur_col.end() && bes -> cx == it -> cx - 1)merge(it -> id,bes -> id);

			cur_col.insert(*it);

			if(i != 1 && rs[i - 1].size() != 1)

			{

				set<row>::iterator up = rs[i - 1].upper_bound((row){it -> cx,0,0,0});

				if(up != rs[i - 1].begin())

				{

					--up;

					if(up -> rx1 <= it -> cx && it -> cx <= up -> rx2)

						merge(it -> id,up -> id);

				}

			}

		}

		for(set<row>::iterator it = rs[i].begin();it != rs[i].end();++it)

		{

			if(it -> rx1 == 0x3f3f3f3f)continue;

			++cnt;tot += it -> rx2 - it -> rx1 + 1;

			set<col>::iterator bes;

			bes = cur_col.lower_bound((col){it -> rx2 + 1,0,0,0});

			if(bes != cur_col.end() && bes -> cx == it -> rx2 + 1)merge(it -> id,bes -> id);

			bes = cur_col.lower_bound((col){it -> rx1 - 1,0,0,0});

			if(bes != cur_col.end() && bes -> cx == it -> rx1 - 1)merge(it -> id,bes -> id);

			if(i != 1 && en[i - 1].size() != 1)

			{

				set<col>::iterator lef,rig;

				lef = en[i - 1].lower_bound((col){it -> rx1,0,0,0});

				if(lef -> cx <= it -> rx2)

				{

					rig = en[i - 1].upper_bound((col){it -> rx2,0,0,0});

					for(set<col>::iterator las = lef;las != rig;++las)

						merge(it -> id,las -> id);

				}

			}

			if(i != 1 && rs[i - 1].size() != 1)

			{

				set<row>::iterator lef,rig;

				lef = rs[i - 1].upper_bound((row){it -> rx1,0,0,0});

				if(lef != rs[i - 1].begin())--lef;

				if(lef -> rx2 < it -> rx1)++lef;

				if(lef -> rx1 <= it -> rx2)

				{

					rig = rs[i - 1].upper_bound((row){it -> rx2,0,0,0});

					for(set<row>::iterator las = lef;las != rig;++las)

						merge(it -> id,las -> id);

				}

			}

		}

		for(set<col>::iterator it = en[i].begin();it != en[i].end();++it)

		{

			if(it -> cx == 0x3f3f3f3f)continue;

			cur_col.erase(*it);

		}

		ans2[i] = cnt;

		ans1[i] = tot;

	}

	int u,v;

	for(int i = 1;i <= q;++i)

	{

		u = read();v = read();

		if(u == 0)printf("%lld\n",ans1[v]);

		else printf("%d\n",ans2[v]);

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}