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

题解（序列分治）"/>

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

题目描述

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

分析

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

       s o l v e ( l , r ) = s o l v e ( l , m i d ) + s o l v e ( m i d + 1 , r ) + c a l c ( l , r , m i d ) solve(l, r) = solve(l, mid) + solve(mid + 1, r) + calc(l,r, mid) solve(l,r)=solve(l,mid)+solve(mid+1,r)+calc(l,r,mid)

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

       我们接下来考虑如何在 O ( l e n ) O(len) O(len) 的时间复杂度计算 c a l c ( l , r , m i d ) calc(l, r, mid) calc(l,r,mid)。

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

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

       设
       m a x x i = m a x ( a i , a i + 1 , a i + 2 , . . . , a m i d ) maxx_i = max(a_i, a_{i + 1}, a_{i + 2},..., a_{mid}) maxxi​=max(ai​,ai+1​,ai+2​,...,amid​)，
       m i n x i = m i n ( a i , a i + 1 , a i + 2 , . . . , a m i d ) minx_i = min(a_i, a_{i + 1}, a_{i + 2},..., a_{mid}) minxi​=min(ai​,ai+1​,ai+2​,...,amid​)，
       m a x x j = m a x ( a j , a j − 1 , a j − 2 , . . . , a m i d + 1 ) maxx_j = max(a_j, a_{j - 1}, a_{j - 2}, ..., a_{mid + 1}) maxxj​=max(aj​,aj−1​,aj−2​,...,amid+1​)，
       m i n x j = m i n ( a j , a j − 1 , a j − 2 , . . . , a m i d + 1 ) minx_j = min(a_j, a_{j - 1}, a_{j - 2}, ..., a_{mid + 1}) minxj​=min(aj​,aj−1​,aj−2​,...,amid+1​)。

       如果区间 [ l , r ] [l, r] [l,r]合法，那么有 m a x ( m a x x i , m a x x j ) − m i n ( m i n x i , m i n x j ) + 1 = j − i + 1 max(maxx_i, maxx_j) - min(minx_i, minx_j) + 1= j - i + 1 max(maxxi​,maxxj​)−min(minxi​,minxj​)+1=j−i+1。
       把左右加 1 1 1 消掉，得到 m a x ( m a x x i , m a x x j ) − m i n ( m i n x i , m i n x j ) = j − i max(maxx_i, maxx_j) - min(minx_i, minx_j) = j - i max(maxxi​,maxxj​)−min(minxi​,minxj​)=j−i。

       我们现在只考虑 m a x ( m a x i , m a x j ) max(max_i, max_j) max(maxi​,maxj​) 等于 m a x i max_i maxi​ 的情况。另一种情况可以把序列反转后做同样的统计。

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

       1 1 1. m i n ( m i n x i , m i n x j ) = m i n x i min(minx_i, minx_j) = minx_i min(minxi​,minxj​)=minxi​：这一种情况我们可以枚举 i i i，然后根据 m a x x i maxx_i maxxi​ 和 m i n x x i minxx_i minxxi​ 的大小算出来一个 j j j，然后检验一下是否满足 m i d + 1 ≤ j ≤ r mid + 1\leq j \leq r mid+1≤j≤r 以及 是否满足 m a x x j < m a x x i maxx_j < maxx_i maxxj​<maxxi​ 并且 m i n x j > m i n x i minx_j > minx_i minxj​>minxi​ 即可。计算和检验的复杂度都是 O ( 1 ) O(1) O(1) 的。

       2 2 2. m i n ( m i n x i , m i n x j ) = m i n x j min(minx_i, minx_j) = minx_j min(minxi​,minxj​)=minxj​：那么不难发现， 如果 [ i , j ] [i, j] [i,j] 合法，需要满足 :

       m a x x i − m i n x j = j − i ⇒ m a x x i + i = m i n x j + j maxx_i - minx_j = j - i \Rightarrow maxx_i + i = minx_j + j maxxi​−minxj​=j−i⇒maxxi​+i=minxj​+j。

       因为 m i n x j + j minx_j + j minxj​+j 是一个定值， 可以开 桶 记录数量。我们从 m i d mid mid 到 l l l 枚举 i i i， 那么 m a x x i maxx_i maxxi​ 是不降的， m i n x i minx_i minxi​ 是不增的。那么由于需要满足 m a x x i > m a x x j maxx_i > maxx_j maxxi​>maxxj​ 并且 m i n x i > m i n x j minx_i > minx_j minxi​>minxj​，所以我们考虑这两个限制条件相当于是给 j j j 的选择划定了一个范围。

       具体来讲，我们维护一个双指针 l t lt lt， r t rt rt。表示在 枚举到 i i i 时 j j j 的范围。 m a x x i maxx_i maxxi​ 增大那么 r t rt rt 向右移动，在桶里面让 m i n x r t + r t minx_{rt} + rt minxrt​+rt 的位置加 1 1 1。 m i n x i minx_i minxi​ 减小那么让 l t lt lt 向右移动，同时在桶里面让 m i n x l t + l t minx_{lt} + lt minxlt​+lt 的位置减 1 1 1。指针稳定后统计 桶里面 m a x x i + i maxx_i + i maxxi​+i 位置的数量就好了。

       复杂度计算十分典型：
       最多递归 l o g 2 n log_2n log2​n 层，每一层的总复杂度是 O ( n ) O(n) O(n)。所以算法复杂度是 O ( n l o g 2 n ) O(nlog_2n) O(nlog2​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;
}