【51nod 连续区间】 题解（序列分治）

题目描述

       区间内的元素元素排序后 任意相邻两个元素值差为 $1$ 的区间称为“连续区间”。
       如 $3,1,2$ 是连续区间， $3,1,4$ 不是连续区间。
       给出一个 $1\sim n$ 的排列，问有多少连续区间。
       $n\le 10^6$

分析

       我们考虑对序列分治，设 $solve(l,r)$ 表示左右端点在区间 $[l,r]$ 内的 “连续区间” 的数量。那么显然， 有：

       $solve(l,r)=solve(l,mid)+solve(mid+1,r)+calc(l,r,mid)$

       其中 $calc(l,r,mid)$ 表示左端点在 $[l,mid]$， 右端点在 $[mid+1,r]$ 的 “连续区间” 数量。

       我们接下来考虑如何在 $O(len)$ 的时间复杂度计算 $calc(l,r,mid)$。

       因为给的序列是 排列，所以有一个性质：对于一个连续区间而言，设它的长度是 $k$，那么有 $max-min+1=k$，即最大值减最小值等于区间长度。

       我们考虑区间 $[i,j]$ 是否为合法区间，其中 $i\in [l,mid]，j\in [mid+1,r]$。

       设
       $max{x}_i=max(a_i,a_{i+1},a_{i+2},...,a_{mid})$，
       $min{x}_i=min(a_i,a_{i+1},a_{i+2},...,a_{mid})$，
       $max{x}_j=max(a_j,a_{j-1},a_{j-2},...,a_{mid+1})$，
       $min{x}_j=min(a_j,a_{j-1},a_{j-2},...,a_{mid+1})$。

       如果区间 $[l,r]$合法，那么有 $max(max{x}_i,max{x}_j)-min(min{x}_i,min{x}_j)+1=j-i+1$。
       把左右加 $1$ 消掉，得到 $max(max{x}_i,max{x}_j)-min(min{x}_i,min{x}_j)=j-i$。

       我们现在只考虑 $max(ma{x}_i,ma{x}_j)$ 等于 $ma{x}_i$ 的情况。另一种情况可以把序列反转后做同样的统计。

       那么现在还可以再分两种情况：

       $1$. $min(min{x}_i,min{x}_j)=min{x}_i$：这一种情况我们可以枚举 $i$，然后根据 $max{x}_i$ 和 $minx{x}_i$ 的大小算出来一个 $j$，然后检验一下是否满足 $mid+1\le j\le r$ 以及 是否满足 $max{x}_j<max{x}_i$ 并且 $min{x}_j>min{x}_i$ 即可。计算和检验的复杂度都是 $O(1)$ 的。

       $2$. $min(min{x}_i,min{x}_j)=min{x}_j$：那么不难发现， 如果 $[i,j]$ 合法，需要满足 :

       $max{x}_i-min{x}_j=j-i\Rightarrow max{x}_i+i=min{x}_j+j$。

       因为 $min{x}_j+j$ 是一个定值， 可以开 桶 记录数量。我们从 $mid$ 到 $l$ 枚举 $i$， 那么 $max{x}_i$ 是不降的， $min{x}_i$ 是不增的。那么由于需要满足 $max{x}_i>max{x}_j$ 并且 $min{x}_i>min{x}_j$，所以我们考虑这两个限制条件相当于是给 $j$ 的选择划定了一个范围。

       具体来讲，我们维护一个双指针 $lt$， $rt$。表示在 枚举到 $i$ 时 $j$ 的范围。$max{x}_i$ 增大那么 $rt$ 向右移动，在桶里面让 $min{x}_{rt}+rt$ 的位置加 $1$。 $min{x}_i$ 减小那么让 $lt$ 向右移动，同时在桶里面让 $min{x}_{lt}+lt$ 的位置减 $1$。指针稳定后统计 桶里面 $max{x}_i+i$ 位置的数量就好了。

       复杂度计算十分典型：
       最多递归 $lo{g}_{2}n$ 层，每一层的总复杂度是 $O(n)$。所以算法复杂度是 $O(nlo{g}_{2}n)$。可能带点常数。

       代码不难写。

CODE：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
typedef long long LL;
inline int read(){int x = 0, f = 1; char c = getchar();while(!isdigit(c)){if(c == '-') f = -1; c = getchar();}while(isdigit(c)){x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}return x * f;
}
int n, a[N], b[N], minx[N], maxx[N], barrel[N * 2];
LL res;
LL get(int l, int r, int k){//k是中间点，属于左边  算左边为主导的答案 maxx[k] = minx[k] = b[k]; maxx[k + 1] = minx[k + 1] = b[k + 1];for(int i = k - 1; i >= l; i--){maxx[i] = max(maxx[i + 1], b[i]);minx[i] = min(minx[i + 1], b[i]);}for(int i = k + 2; i <= r; i++){maxx[i] = max(maxx[i - 1], b[i]);minx[i] = min(minx[i - 1], b[i]);}LL ans = 0;for(int i = k; i >= l; i--){// 首先算左边既有最大，又有最小的答案 int rt = maxx[i] - minx[i] + i;if(rt > r || rt <= k) continue;if(maxx[rt] < maxx[i] && minx[rt] > minx[i]) ans++;}int rt = k + 1, lt = k + 1;for(int i = k; i >= l; i--){// 接下来算左边有最大值，右边有最小值的答案 while(maxx[i] > maxx[rt] && rt <= r){barrel[minx[rt] + rt]++;rt++;}while(minx[i] < minx[lt] && lt < rt){barrel[minx[lt] + lt]--;lt++;}ans += barrel[maxx[i] + i];}for(int i = k + 1; i <= r; i++) barrel[minx[i] + i] = 0;return ans;
}
void solve(int l, int r){if(l == r){res++; return ;}int mid = (l + r >> 1);solve(l, mid); solve(mid + 1, r);// 算出来左右两边的答案 for(int i = l; i <= r; i++) b[i] = a[i];res += get(l, r, mid);reverse(b + l, b + r + 1);res += get(l, r, l + r - mid - 1);
}
int main(){n = read();for(int i = 1; i <= n; i++)a[i] = read();solve(1, n);printf("%lld\n", res);return 0;
}