51Nod 1555 布丁怪 分治

Description
一个n * n的矩阵有n个节点，它们纵坐标和横坐标互不相同，问有多少个k*k的矩阵存在有k个元素且每行每列互不相同。

---

Sample Input
5
1 1
4 3
3 2
2 4
5 5

---

Sample Output
10

---

问题可以变为问一个序列中有多少个子序列里面的数编号连续。
考虑分治，维护最大值最小值，分情况讨论。
1.最大值和最小值都在右边
这时只可能会出现一种情况，直接判断，还要判一下之前是否判过。
2.最大值和最小值分开在左右两侧
以最小值在右边为例：
$maxi-min+1=s+sli$maxi−min+1=s+sli
则对于左侧将每个$maxi-sli+1$maxi−sli+1的值放到权值数组中去即可。
3.最大值和最小值都在左侧
$maxi-mini+1=sli+s$maxi−mini+1=sli+s
将$maxi-mini+1-sli$maxi−mini+1−sli放入权值数组即可。
可能需要三个指针，稍微有点麻烦。

---

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
int _min(int x, int y) {return x < y ? x : y;}
int _max(int x, int y) {return x > y ? x : y;}
int read() {
	int s = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * f;
}

struct node {
	int x, y;
} q[310000]; int a[310000];
int s1[310000], s2[310000], s3[310000];
LL ans = 0;

bool cmp(node a, node b) {return a.x < b.x;}

void solve(int l, int r) {
	if(l == r) {ans++; return ;}
	int mid = (l + r) / 2;
	solve(l, mid), solve(mid + 1, r);
	int minn = 999999999, maxx = 0;
	for(int i = mid; i >= l; i--) {
		minn = _min(minn, a[i]), maxx = _max(maxx, a[i]);
		s3[_max(0, maxx - minn + 1 - (mid - i + 1))]++;
	} int tp1 = mid + 1, tp2 = mid + 1;
	int min1 = 999999999, max1 = 0, min2 = 999999999, max2 = 0, min3 = 999999999, max3 = 0;
	int hh = mid + 1; minn = 999999999, maxx = 0;
	for(int i = mid + 1; i <= r; i++) {
		min1 = _min(min1, a[i]), max1 = _max(max1, a[i]);
		while(tp1 > l && a[tp1 - 1] < max1) {
			min2 = _min(min2, a[--tp1]), max3 = _max(max3, a[tp1]);
			s1[_min(300001, (mid - tp1 + 1) + min2)]++;
			s2[_max(0, max3 - (mid - tp1 + 1) + 1)]--;
		}
		while(tp2 > l && a[tp2 - 1] > min1) {
			max2 = _max(max2, a[--tp2]), min3 = _min(min3, a[tp2]);
			s2[_max(0, max2 - (mid - tp2 + 1) + 1)]++;
			s1[_min(300001, (mid - tp2 + 1) + min3)]--;
		}
		while(hh > tp1 || hh > tp2) {
			minn = _min(minn, a[--hh]), maxx = _max(maxx, a[hh]);
			s3[_max(0, maxx - minn + 1 - (mid - hh + 1))]--;
		}
		int h1 = _max(tp1, tp2);
		if(i - h1 + 1 >= max1 - min1 + 1 && max1 - min1 > i - mid) ans++;
		if(h1 == tp2) ans += s1[_max(0, max1 - (i - mid) + 1)];
		else ans += s2[_min(300001, (i - mid) + min1)];
		ans += s3[i - mid];
	} minn = 999999999, maxx = 0;
	for(int i = mid; i >= l; i--) {
		minn = _min(minn, a[i]), maxx = _max(maxx, a[i]);
		s1[_min(300001, minn + (mid - i + 1))] = 0;
		s2[_max(0, maxx - (mid - i + 1) + 1)] = 0;
		s3[_max(0, maxx - minn + 1 - (mid - i + 1))] = 0;
	}
}

int main() {
	int n = read();
	for(int i = 1; i <= n; i++) q[i].x = read(), q[i].y = read();
	sort(q + 1, q + n + 1, cmp);
	for(int i = 1; i <= n; i++) a[i] = q[i].y;
	solve(1, n); printf("%lld\n", ans);
	return 0;
}