「成都七中D5T3」第三题 - 分治+Hash

题目大意

    这是第三题，有趣的是这套题都是送分题。
    给出一个$1$到$N$的排列，你需要求出有多少个区间$[L,R]$，满足这个区间的值是连续的。比如$2,3,1$是一个合法的区间，而$3,1$不是。

题目分析

原题维护的信息很难处理。
考虑转化维护的信息。
不难发现我们可以将问题转化为极差=区间长度。（achen：显然）
然后就和本题一模一样了。

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=300005,Delta=200000;

int n,LMin[maxn],LMax[maxn],RMin[maxn],RMax[maxn],a[maxn],Hash[maxn*4];
long long ans=0;

void Solve(int Left,int Right) {
	if(Left==Right) {
		ans++;
		return;
	}
	int mid=(Left+Right)>>1;
	for(int i=Left; i<=Right; i++)LMin[i]=RMin[i]=0x7fffffff/2,LMax[i]=RMax[i]=-0x7fffffff/2;
	for(int i=mid; i>=Left; i--)LMin[i]=min(LMin[i+1],a[i]),LMax[i]=max(LMax[i+1],a[i]);
	for(int i=mid+1; i<=Right; i++)RMin[i]=min(RMin[i-1],a[i]),RMax[i]=max(RMax[i-1],a[i]);
	int l=mid+1,r=mid+1;
	for(int i=mid; i>=Left; i--) {
		int pos=LMax[i]-LMin[i]+i; //Max/Min左 
		if(pos>mid&&pos<=Right&&LMax[i]>=RMax[pos]&&LMin[i]<=RMin[pos])ans++;
		while(r<=Right&&LMax[i]>=RMax[r]) {
			Hash[r+RMin[r]]++;
			r++;
		}
		while(l<=Right&&LMin[i]<RMin[l]) {
			Hash[l+RMin[l]]--;
			l++;
		}
		if(Hash[i+LMax[i]]>0)ans+=Hash[i+LMax[i]];
	}
	while(r>mid+1) {
		r--;
		Hash[r+RMin[r]]--;
	}
	while(l>mid+1) {
		l--;
		Hash[l+RMin[l]]++;
	}
	l=mid,r=mid;
	for(int i=mid+1; i<=Right; i++) {
		int pos=i-RMax[i]+RMin[i]; //Max/Min右
		if(pos>=Left&&pos<=mid&&RMax[i]>=LMax[pos]&&RMin[i]<=LMin[pos])ans++;
		while(l>=Left&&RMax[i]>=LMax[l]) {
			Hash[LMin[l]-l+Delta]++;
			l--;
		}
		while(r>=Left&&RMin[i]<LMin[r]) {
			Hash[LMin[r]-r+Delta]--;
			r--;
		}
		if(Hash[RMax[i]-i+Delta]>0)ans+=Hash[RMax[i]-i+Delta];
	}
	while(l<mid) {
		l++;
		Hash[LMin[l]-l+Delta]--;
	}
	while(r<mid) {
		r++;
		Hash[LMin[r]-r+Delta]++;
	}
	Solve(Left,mid);
	Solve(mid+1,Right);
}

int main() {
	n=Get_Int();
	for(int i=1; i<=n; i++)a[i]=Get_Int();
	Solve(1,n);
	printf("%lld\n",ans);
	return 0;
}