jsp建网站,唐山市住房城乡建设部网站主页,北京哪里做网站好,沃尔玛网上商城网址题目描述 区间内的元素元素排序后 任意相邻两个元素值差为 1 1 1 的区间称为“连续区间”。 如 3 , 1 , 2 3,1,2 3,1,2 是连续区间#xff0c; 3 , 1 , 4 3,1,4 3,1,4 不是连续区间。 给出一个 1 ∼ n 1 \sim n 1∼n 的排列#xff0c;问有多少连续区间。 …题目描述 区间内的元素元素排序后 任意相邻两个元素值差为 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(mid1,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] [mid1,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−min1k即最大值减最小值等于区间长度。 我们考虑区间 [ 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∈[mid1,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}) maxximax(ai,ai1,ai2,...,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}) minximin(ai,ai1,ai2,...,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}) maxxjmax(aj,aj−1,aj−2,...,amid1) 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}) minxjmin(aj,aj−1,aj−2,...,amid1)。 如果区间 [ 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)1j−i1。 把左右加 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 mid1≤j≤r 以及 是否满足 m a x x j m a x x i maxx_j maxx_i maxxjmaxxi 并且 m i n x j m i n x i minx_j minx_i minxjminxi 即可。计算和检验的复杂度都是 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−minxjj−i⇒maxxiiminxjj。 因为 m i n x j j minx_j j minxjj 是一个定值 可以开 桶 记录数量。我们从 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 maxximaxxj 并且 m i n x i m i n x j minx_i minx_j minximinxj所以我们考虑这两个限制条件相当于是给 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 minxrtrt 的位置加 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 minxltlt 的位置减 1 1 1。指针稳定后统计 桶里面 m a x x i i maxx_i i maxxii 位置的数量就好了。 复杂度计算十分典型 最多递归 l o g 2 n log_2n log2n 层每一层的总复杂度是 O ( n ) O(n) O(n)。所以算法复杂度是 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)。可能带点常数。 代码不难写。
CODE
#includebits/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;
}
