连号区间数
题目：
问题描述
小明这些天一直在思考这样一个奇怪而有趣的问题：
在1~N的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是：
如果区间[L, R] 里的所有元素（即此排列的第L个到第R个元素）递增排序后能得到一个长度为R-L+1的“连续”数列，则称这个区间连号区间。
当N很小的时候，小明可以很快地算出答案，但是当N变大的时候，问题就不是那么简单了，现在小明需要你的帮助。
输入格式
第一行是一个正整数N (1 <= N <= 50000), 表示全排列的规模。
第二行是N个不同的数字Pi(1 <= Pi <= N)， 表示这N个数字的某一全排列。
输出格式
输出一个整数，表示不同连号区间的数目。
样例输入1
4
3 2 4 1
样例输出1
7
样例输入2
5
3 4 2 5 1
样例输出2
9
做法：
连号区间数：N<=5E4
给定一个N的排列，求有多少个区间满足区间排序后为连续的数列
有一个比较容易想到的O(N^2)的算法： 1 2 3 4 5
遍历排列的每个区间，如果区间的最大值maxx减去最小值minn等于区间长度减一，那么这个区间排序后就能成为连续的数列
伪代码如下：
ans = 0
for left in range(1,N+1):
maxx = minn = a[left]
for right in range(left,N+1): #当前的区间为a[left],a[left+1],a[left+2],...a[right]
maxx = max(maxx,a[right])
minn = min(minn,a[right])
if maxx-minn == right-left:
ans += 1
第二种思路，参照codeforces 193D(Two Segments)的做法：
定义函数f(L,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 且 f(L,R)为 1 的时候，给定的排列中存在一段可以排序后构成L,L+1,L+2,...R-1,R这个连续的数列，那么ans+=1
我们现在枚举排序后组成区间的左右端点L和R,如果 f(L,R)为 1，那么答案+1
那么我们考虑状态的转移：已知 f(L,R)==K如何求得 f(L,R+1)呢？
我们考虑R+1这个数在排列中出现的位置：
1.如果R+1这个数和[L,R]这个数列在排列中被分割成的任何一段都不相邻，那么 f(L,R+1) = f(L,R)+1 = K+1
2.如果R+1这个数和[L,R]这个数列在排列中被分割成的某一段相邻，那么f(L,R+1) = f(L,R) = K
3.如果R+1这个数连接了[L,R]这个数列在排列中被分割的某两段，那么f(L,R+1) = f(L,R)-1 = K-1
如果K<=2那么我们从f(L,R)到f(L,R+1)的转移就是O(1)的
基于这个思路，我们可以两重循环遍历L和R，得到一个O(N^2)的算法:
for L in range(1,N+1)：
map<pair<int,int>,int> mp;
mp.insert( make_pair(make_pair(1,1),1) )
pre = F[L][L] = 1; ans += 1
for R in range(L+1,N+1):
p = pos[R];
for(auto x:mp):
。。。不太清楚要咋搞~
我们要计算的是：
sum
{
for R from 1 to N:
for L from 1 to R:
f(L,R)==1 ? 1 : 0
}
我们可以从1到N遍历排序后的区间右端点R，然后用线段树处
理出f(1,R),f(2,R),f(3,R),...f(R,R)的信息
复杂度为O(NlogN)
在第二重循环每次结束后，我们都需要统计一次f(1,R),f(2,R),f(3,R),
...,f(R,R)的所有信息，把值为1的个数统计出来。我们用线段树来维护这些函数值的信息，
因为f(x,y)的最小值为1，我们要求的就是f(x,y)为1的个数，所以我们可以用线段树来维护
区间最小值，以及等于最小值的数的个数。线段树的某一段[left,right]记录的是f(left,R)
,f(left+1,R),...f(left+2,R),f(right-1,R),f(right,R)这几个函数的最小值和等于最小值的个数
我们只需要查询区间最小值等于1的个数并累加即可
每次循环的时候R+1,但目前记录的都是右端点等于R的信息，我们要做一些状态的转移
对于排序后的区间左端点i(1<=i<=R+1)来说，都要从线段树维护的都是f(i,R),都要转化
为f(i,R+1)
刚才我们已经分析过了R+1这个数的位置对于f(x,R)转移到f(x,R+1)的影响
我们可以先假设R+1这个数出现的位置和1,2,3...R都不相邻，那么对于i from 1 to R,就
都有: f(i,R+1) = f(i,R) + 1, 我们可以用线段树进行区间加1，add(1,R,1)
但是R+1在排列中的位置左右两边可能会有小于R+1的数与之相邻，设为x,y,这样的话,如果x<R+1(y同理)
那么f(1,R+1),f(2,R+1),...f(x,R+1)都等于原来右端点为R的值，我们多加了1，要减回来add(1,x,-1)
如果y<R+1,同理
如果x,y均小于R+1，那么区间应该分别做减法
伪代码如下：
ans = 0
build_SegmentTree()
for R from 1 to N:
add(1,R,1)
pos_R = toPos[R]
x = a[pos_R - 1]
y = a[pos_R + 1]
if(x&&x<R):
add(1,x,-1)
if(y&&y<R):
add(1,y,-1)
ans += query(1,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 build(int left,int right,int pos);
void push_up(int pos);
void push_down(int pos);
int query(int left,int right,int L,int R,int pos);
void update(int left,int right,int L,int R,int add,int pos);
int main()
{
int N;
while(cin>>N)
{
for(int i=1;i<=N;++i)
scanf("%d",a+i), pos[a[i]] = i;
a[0] = a[N+1] = 0;
build(1,N,1);
LL ans = 0;
for(int R=1;R<=N;++R)
{
int p = pos[R];
int x = a[p-1];
int y = a[p+1];
update(1,N,1,R,1,1);
if(x>0&&x<R) update(1,N,1,x,-1,1);
if(y>0&&y<R) update(1,N,1,y,-1,1);
ans += query(1,N,1,R,1);
}
printf("%lld
",ans);
}
return 0;
}
void push_down(int 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_up(int pos)
{
Min[pos] = min(Min[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 build(int left,int right,int pos)
{
Min[pos] = lazy[pos] = 0;
if(left==right)
return tot[pos] = 1;
int mid = (left+right)/2;
return tot[pos] = build(left,mid,pos*2)+build(mid+1,right,pos*2+1);
}
void update(int left,int right,int L,int R,int add,int pos)
{
if(left>R || right<L) return;
if(L<=left && right<=R)
{
Min[pos]+=add;
lazy[pos]+=add;
return;
}
push_down(pos);
int mid = (left+right)/2;
update(left,mid,L,R,add,pos*2);
update(mid+1,right,L,R,add,pos*2+1);
push_up(pos);
}
int query(int left,int right,int L,int R,int pos)
{
if(left>R||right<L) return 0;
if(L<=left && right<=R)
return (Min[pos]==1)*tot[pos];
push_down(pos);
int mid = (left+right)/2;
return query(left,mid,L,R,pos*2) + query(mid+1,right,L,R,pos*2+1);
}
