[51nod1555][分治]布丁怪

Description

布丁怪这一款游戏是在一个n×n
的矩形网格中进行的，里面有n个网格有布丁怪，其它的一些格子有一些其它的游戏对象。游戏的过程中是要在网格中移动这些怪物。如果两个怪物碰到了一起，那么他们就会变成一个更大的怪物。（谁叫他们是布丁呢？）

据统计，如果每一行每一列都只有一个布丁怪，那么这样的布局是比较吸引玩家的。

所以为了产生多种多样的有趣布局，我们会从一个 n×n 的有趣的地图中选取一个k×k
(1≤k≤n)子矩形作为地图，而且这个子地图中恰好有k个布丁怪。

现在请你计算一下一个n×n 的有趣布局中，有多少种子地图是有趣的。

Input

单组测试数据。 第一行有一个整数n (1≤n≤3×10^5)，表示原始地图的大小。 接下来n行，表示怪物的原始座标。
第i行有两个整数ri,ci(1≤ri,ci≤n)，表示第i个怪物所在的行和列。 输入保证所有ri是不一样的，所有ci也是不一样的。

Output

输出一个整数，表示有多少种子地图是有趣的。

Sample Input

5
1 1
4 3
3 2
2 4
5 5

Sample Output

10

题解

很妙啊这题
我才不会说是因为我没看完题不会做…
保证ri及ci互不相同不就相当于每行每列只有一个布丁怪我怎么就没看到这句话
按x坐标排序
只需要连续一段的值域连续即可
这个可以大力分治
记录一个最大值与最小值
显然最大值减最小值+1等于这段长度就是可行的
分最大最小值在同一侧或者在异侧讨论即可
同侧很好搞
异侧开个桶双指针扫一遍即可

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#define LL long long
#define mp(x,y) make_pair(x,y)
using namespace std;
inline int read()
{
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void write(int x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
inline void print(int x){write(x);printf(" ");}
struct node{int x,y;}w[310000];int n;
bool cmp(node n1,node n2){return n1.x<n2.x;}
int cnt[1210000],gg[1210000],tim;
int mn[310000],mx[310000];
void ad(int pos,int op)
{
	if(gg[mn[pos]+op*pos+n]!=tim)gg[mn[pos]+op*pos+n]=tim,cnt[mn[pos]+op*pos+n]=0;
	cnt[mn[pos]+op*pos+n]++;
}
void dl(int pos,int op){cnt[mn[pos]+op*pos+n]--;}
LL sol(int l,int r)
{
	if(l>r)return 0;
	if(l==r)return 1;
	int mid=(l+r)/2;
	LL ret=0;
	mn[mid]=999999999;mx[mid]=0;
	for(int i=mid+1;i<=r;i++)mn[i]=min(mn[i-1],w[i].y),mx[i]=max(mx[i-1],w[i].y);
	mn[mid]=mx[mid]=w[mid].y;
	for(int i=mid-1;i>=l;i--)mn[i]=min(mn[i+1],w[i].y),mx[i]=max(mx[i+1],w[i].y);
	int u=mid;
	for(int i=mid;i>=l;i--)
	{
		while(w[u+1].y<mx[i]&&w[u+1].y>mn[i]&&u<r)u++;
		if(u>mid)ret+=(mx[i]-mn[i]+1==u-i+1);
	}//mx和mn都在左边 
	u=mid+1;
	for(int i=mid+1;i<=r;i++)
	{
		while(w[u-1].y<mx[i]&&w[u-1].y>mn[i]&&u>l)u--;
		if(u<mid+1)ret+=(mx[i]-mn[i]+1==i-u+1);
	}//mx和mn都在右边
	int L1=mid,L2=mid;tim++;
	for(int i=mid;i>=l;i--)
	{
		while(L1<r&&w[L1+1].y<mx[i])L1++,ad(L1,1);
		while(L2<=L1&&(L2==mid?999999999:mn[L2])>mn[i])
		{
			if(L2>mid)dl(L2,1);
			L2++;
		}
		if(L2>mid&&gg[mx[i]+i+n]==tim)ret+=cnt[mx[i]+i+n];
	}
	L1=L2=mid+1;tim++;
	for(int i=mid+1;i<=r;i++)
	{
		while(L1>l&&w[L1-1].y<mx[i])L1--,ad(L1,-1);
		while(L2>=L1&&(L2==mid+1?999999999:mn[L2])>mn[i])
		{
			if(L2<mid+1)dl(L2,-1);
			L2--;
		}
		if(L1<mid+1&&gg[mx[i]-i+n]==tim)ret+=cnt[mx[i]-i+n];
	}
	return ret+sol(l,mid)+sol(mid+1,r);
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)w[i].x=read(),w[i].y=read();
	sort(w+1,w+1+n,cmp);
//	printf("%lld\n",sol(4,5));
	printf("%lld\n",sol(1,n));
	return 0;
}