连续区间计数 [线段树, 单调栈]

$连续区间计数$

$color{grey}{最初想法}$

一个区间合法当且仅当 $max\_v-min\_v == r-l$ , 移项得 $min\_v == max\_v - (r-l)$ ,
可以想到枚举 $min\_v = A[i]$ , 记录左边第一个比 $i$ 小的位置和右边第一个比 $i$ 小的位置,
分别记为 $Ld[i], Rd[i]$ , 然后在 $(Ld[i], Rd[i])$ 中枚举左端点属于 $(Ld[i], p]$ , 右端点属于 $(p, Rd[i])$ ,
直接裸算时间复杂度期望 $O(nlog^2 n)$ ,
加上枚举右端点时的 “可行性剪枝”, 和对 $|A[i]-A[i+1]|=1$ 连续数字的加速, 跑随机数据 $0.3s$ 可出答案 .
$code$

$color{red}{正解部分}$

从左向右 枚举右端点 $r$ , 检查 $r$ 的左边有多少 $l$ 满足 $r = max\_v-min\_v + l$ ,
其中 $max\_v, min\_v$ 都是在 $[l, r]$ 区间意义下的,

这里有个性质: $max\_v-min\_v geq r-l ightarrow max\_v-min\_v + l geq r$ .
有了这个, 就可以考虑使用 线段树 维护 $max\_v-min\_v+l$ 的 区间最小值,
因为只有可能 最小值 满足 $max\_v-min\_v+l == r$ .

考虑 $r$ 向右移动一位对 $l ∈ [1, r+1]$ 的影响,
此时 $A[r+1]$ 可能成为关于 $[l, r+1]$ 的新的 最大值, 也可能成为新的 最小值,
而影响的区间又是连续的, 考虑使用 单调栈 维护,

$具体来说$ : 以维护 最大值 为例, 建立一个 单调递减 的 单调栈, 栈中存下标,
在弹出栈顶时在 线段树 中更新栈顶与 次栈顶 的差大小的 左端点们 代表的区间 .
单调递增 的 单调栈 也按此方法维护 最小值 .

对于 $r$ , 统计 线段树 的区间 $[1, r]$ 中有多少 最小值 等于 $r$ 即可 .

$color{red}{实现部分}$

#include<bits/stdc++.h>
#define reg register

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

const int maxn = 300005;

int N;
int top[2];
int A[maxn];
int stk[2][maxn];

struct Segment_Tree{

        struct Node{ int l, r, tag, min_v, min_n; } T[maxn<<3];

        void Push_up(int k){ 
                T[k].min_v = std::min(T[k<<1].min_v, T[k<<1|1].min_v);
                T[k].min_n = 0;
                if(T[k].min_v == T[k<<1].min_v) T[k].min_n += T[k<<1].min_n;
                if(T[k].min_v == T[k<<1|1].min_v) T[k].min_n += T[k<<1|1].min_n;
        }

        void Build(int k, int l, int r){
                T[k].l = l, T[k].r = r;
                if(l == r){ T[k].min_v = l, T[k].min_n = 1; return ; }
                int mid = l+r >> 1;
                Build(k<<1, l, mid), Build(k<<1|1, mid+1, r), Push_up(k);
        }

        void Push_down(int k){
                T[k].min_v += T[k].tag;
                int lt = k << 1, rt = k<<1 | 1;
                T[lt].tag += T[k].tag, T[rt].tag += T[k].tag;
                T[k].tag = 0;
        }

        void Modify(int k, const int &ql, const int &qr, const int &v){
                int l = T[k].l, r = T[k].r;
                if(T[k].tag) Push_down(k);
                if(l > qr || r < ql) return ;
                if(ql <= l && r <= qr){ T[k].tag += v, Push_down(k); return ; }
                int mid = l+r >> 1;
                Modify(k<<1, ql, qr, v), Modify(k<<1|1, ql, qr, v);
                Push_up(k);
        }

        int Query(int k, const int &ql, const int &qr){
                int l = T[k].l, r = T[k].r;
                if(T[k].tag) Push_down(k);
                if(ql <= l && r <= qr){ return T[k].min_v==qr?T[k].min_n:0; }
                int mid = l+r >> 1, s = 0;
                if(ql <= mid) s += Query(k<<1, ql, qr);
                if(qr > mid) s += Query(k<<1|1, ql, qr);
                return s;
        }

} seg_t;

int main(){
        N = read();
        for(reg int i = 1; i <= N; i ++) A[i] = read();
        seg_t.Build(1, 1, N);
        long long Ans = 0;
        for(reg int r = 1; r <= N; r ++){
                while(top[0] && A[stk[0][top[0]]] > A[r]){ // 1, 2, 3
                        seg_t.Modify(1, stk[0][top[0]-1]+1, stk[0][top[0]], A[stk[0][top[0]]] - A[r]);
                        -- top[0];
                }
                stk[0][++ top[0]] = r;
                while(top[1] && A[stk[1][top[1]]] < A[r]){
                        seg_t.Modify(1, stk[1][top[1]-1]+1, stk[1][top[1]], A[r] - A[stk[1][top[1]]]);
                        -- top[1];
                }
                stk[1][++ top[1]] = r;
                Ans += seg_t.Query(1, 1, r);
        }
        printf("%lld
", Ans);
        return 0;
}