连号区间数
题目：
问题描述
小明这些天一直在思考这样一个奇怪而有趣的问题：
在1~N的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是：
如果区间[L, R] 里的所有元素（即此排列的第L个到第R个元素）递增排序后能得到一个长度为R-L+1的“连续”数列，则称这个区间连号区间。
当N很小的时候，小明可以很快地算出答案，但是当N变大的时候，问题就不是那么简单了，现在小明需要你的帮助。
输入格式
第一行是一个正整数N 1 <= N <= 50000), 表示全排列的规模。
第二行是N个不同的数字Pi1 <= Pi <= N)， 表示这N个数字的某一全排列。
输出格式
输出一个整数，表示不同连号区间的数目。
样例输入1
4
3 2 4 1
样例输出1
7
样例输入2
5
3 4 2 5 1
样例输出2
9
做法：
连号区间数：N<=5E4
给定一个N的排列，求有多少个区间满足区间排序后为连续的数列
有一个比较容易想到的ON^2)的算法： 1 2 3 4 5
遍历排列的每个区间，如果区间的最大值maxx减去最小值minn等于区间长度减一，那么这个区间排序后就能成为连续的数列
伪代码如下：
ans = 0
for left in range1,N+1):
maxx = minn = a[left]
for right in rangeleft,N+1): #当前的区间为a[left],a[left+1],a[left+2],...a[right]
maxx = maxmaxx,a[right])
minn = minminn,a[right])
if maxx-minn == right-left:
ans += 1
第二种思路，参照codeforces 193DTwo Segments)的做法：
定义函数fL,R)为数字L,L+1,L+2...R-1,R 这个连续的数列在给定的排列中被分割成的段数
比如输入为 1 5 3 4 2 6，那么[1,3]被分割成了3段，[2,4]被分割成1段，[5,6]被分割成2段
那么当L<=R 且 fL,R)为 1 的时候，给定的排列中存在一段可以排序后构成L,L+1,L+2,...R-1,R这个连续的数列，那么ans+=1
我们现在枚举排序后组成区间的左右端点L和R,如果 fL,R)为 1，那么答案+1
那么我们考虑状态的转移：已知 fL,R)==K如何求得 fL,R+1)呢？
我们考虑R+1这个数在排列中出现的位置：
1.如果R+1这个数和[L,R]这个数列在排列中被分割成的任何一段都不相邻，那么 fL,R+1) = fL,R)+1 = K+1
2.如果R+1这个数和[L,R]这个数列在排列中被分割成的某一段相邻，那么fL,R+1) = fL,R) = K
3.如果R+1这个数连接了[L,R]这个数列在排列中被分割的某两段，那么fL,R+1) = fL,R)-1 = K-1
如果K<=2那么我们从fL,R)到fL,R+1)的转移就是O1)的
基于这个思路，我们可以两重循环遍历L和R，得到一个ON^2)的算法:
for L in range1,N+1)：
map<pair<int,int>,int> mp;
mp.insert make_pairmake_pair1,1),1) )
pre = F[L][L] = 1; ans += 1
for R in rangeL+1,N+1):
p = pos[R];
forauto x:mp):
。。。不太清楚要咋搞~
我们要计算的是：
sum
{
for R from 1 to N:
for L from 1 to R:
fL,R)==1 ? 1 : 0
}
我们可以从1到N遍历排序后的区间右端点R，然后用线段树处
理出f1,R),f2,R),f3,R),...fR,R)的信息
复杂度为ONlogN)
在第二重循环每次结束后，我们都需要统计一次f1,R),f2,R),f3,R),
...,fR,R)的所有信息，把值为1的个数统计出来。我们用线段树来维护这些函数值的信息，
因为fx,y)的最小值为1，我们要求的就是fx,y)为1的个数，所以我们可以用线段树来维护
区间最小值，以及等于最小值的数的个数。线段树的某一段[left,right]记录的是fleft,R)
,fleft+1,R),...fleft+2,R),fright-1,R),fright,R)这几个函数的最小值和等于最小值的个数
我们只需要查询区间最小值等于1的个数并累加即可
每次循环的时候R+1,但目前记录的都是右端点等于R的信息，我们要做一些状态的转移
对于排序后的区间左端点i1<=i<=R+1)来说，都要从线段树维护的都是fi,R),都要转化
为fi,R+1)
刚才我们已经分析过了R+1这个数的位置对于fx,R)转移到fx,R+1)的影响
我们可以先假设R+1这个数出现的位置和1,2,3...R都不相邻，那么对于i from 1 to R,就
都有: fi,R+1) = fi,R) + 1, 我们可以用线段树进行区间加1，add1,R,1)
但是R+1在排列中的位置左右两边可能会有小于R+1的数与之相邻，设为x,y,这样的话,如果x<R+1y同理)
那么f1,R+1),f2,R+1),...fx,R+1)都等于原来右端点为R的值，我们多加了1，要减回来add1,x,-1)
如果y<R+1,同理
如果x,y均小于R+1，那么区间应该分别做减法
伪代码如下：
ans = 0
build_SegmentTree)
for R from 1 to N:
add1,R,1)
pos_R = toPos[R]
x = a[pos_R - 1]
y = a[pos_R + 1]
ifx&&x<R):
add1,x,-1)
ify&&y<R):
add1,y,-1)
ans += query1,R)
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4+10;
#define LL long long
int Min[maxn*4],tot[maxn*4],lazy[maxn*4],a[maxn],pos[maxn];
int buildint left,int right,int pos);
void push_upint pos);
void push_downint pos);
int queryint left,int right,int L,int R,int pos);
void updateint left,int right,int L,int R,int add,int pos);
int main)
{
int N;
whilecin>>N)
{
forint i=1;i<=N;++i)
scanf"%d",a+i), pos[a[i]] = i;
a[0] = a[N+1] = 0;
build1,N,1);
LL ans = 0;
forint R=1;R<=N;++R)
{
int p = pos[R];
int x = a[p-1];
int y = a[p+1];
update1,N,1,R,1,1);
ifx>0&&x<R) update1,N,1,x,-1,1);
ify>0&&y<R) update1,N,1,y,-1,1);
ans += query1,N,1,R,1);
}
printf"%lld
",ans);
}
return 0;
}
void push_downint pos)
{
if!lazy[pos]) return;
lazy[pos*2] += lazy[pos];
lazy[pos*2+1] += lazy[pos];
Min[pos*2] += lazy[pos];
Min[pos*2+1]+=lazy[pos];
lazy[pos] = 0;
}
void push_upint pos)
{
Min[pos] = minMin[pos*2],Min[pos*2+1]);
tot[pos] = Min[pos]==Min[pos*2])*tot[pos*2]+Min[pos]==Min[pos*2+1])*tot[pos*2+1];
}
int buildint left,int right,int pos)
{
Min[pos] = lazy[pos] = 0;
ifleft==right)
return tot[pos] = 1;
int mid = left+right)/2;
return tot[pos] = buildleft,mid,pos*2)+buildmid+1,right,pos*2+1);
}
void updateint left,int right,int L,int R,int add,int pos)
{
ifleft>R || right<L) return;
ifL<=left && right<=R)
{
Min[pos]+=add;
lazy[pos]+=add;
return;
}
push_downpos);
int mid = left+right)/2;
updateleft,mid,L,R,add,pos*2);
updatemid+1,right,L,R,add,pos*2+1);
push_uppos);
}
int queryint left,int right,int L,int R,int pos)
{
ifleft>R||right<L) return 0;
ifL<=left && right<=R)
return Min[pos]==1)*tot[pos];
push_downpos);
int mid = left+right)/2;
return queryleft,mid,L,R,pos*2) + querymid+1,right,L,R,pos*2+1);
}
