Codeforces Round #493 Div1 E. Good Subsegments

给定一个长度为 $n$ 的排列,定义一个区间$(l,r)$是好的当且仅当其满足 $\max - \min = r - l$ 。有 $Q$ 次询问,每次询问一个区间内有多少个子区间是好的。

$n, Q\leq 1.2\times 10^5$

题解给的分治加莫队做法没怎么看懂,复杂度是 $\mathcal{O(n \sqrt n \log n)}$ 的。搜了一下发现有 $\mathcal{O(n\log n)}$ 的做法,就去学习了一下

思路还是类似的,首先考虑当只有一个询问时怎么做。有一种分治做法,这里不再细说,很多地方都出过,我们考虑线段树扫描线的做法。

我们枚举一个左端点$l$,统计所有合法的右端点。类似于这一道题,我们定义一个右端点$r$的权值为 $\max - \min - (r - l)$,显然,任何时候一个点的权值不会小于 $-1$,且一个右端点合法当且仅当其权值为 $-1$。

那么我们直接对于线段树,统计一下其中的最小值和最小值出现的次数,若最小值为 $-1$ 则计入答案。

发现我们每次向左移动一次左端点时,会改变若干个区间的 $\max,\min$,以及其长度。但是容易发现所有的修改数量是 $\mathcal{O(n)}$ 级别的。

然后考虑对于任意区间时怎么处理,我们考虑如果可以记录每个区间的历史贡献和,那么答案也是容易计算的。将询问离线后单次区间查询即可。考虑如何记录区间的历史贡献,我们对于线段树每个节点,维护区间最小值,最小值出现次数,总贡献以及当前的最小值出现次数作为历史合法答案贡献了几次,当一个标记传下来时,因为我们保证了区间最小值不会超过 $-1$,所以直接合并标记即可。值得注意的时候,最后一个标记下传时,需要满足其最小值是作为父亲线段中最小值出现的。

复杂度 $O((n + q)\log n)$

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}
template<typename T> inline T dmax(T x, T y){return x > y ? x : y;}
template<typename T> inline T dmin(T x, T y){return x < y ? x : y;}

const int MAXN = 2e5 + 5;
const ll oo = 2e18;

struct Query {
    int le, ri, o;
    inline Query (int le = 0, int ri = 0, int o = 0) : 
    le(le), ri(ri), o(o) {} 
    inline bool operator < (const Query & w) const {
        return le < w.le;
    }
}qry[MAXN];

int N, Q, a[MAXN];

ll ans[MAXN];

struct tree {
    int mn, cnt, tag, upd;
    ll sum;
}t[MAXN << 2];

inline void rel(int k){
    t[k].mn = dmin(t[k << 1].mn, t[k << 1 | 1].mn);
    t[k].sum = t[k << 1].sum + t[k << 1 | 1].sum;
    t[k].cnt = 0;
    if (t[k << 1].mn == t[k].mn) t[k].cnt += t[k << 1].cnt;
    if (t[k << 1 | 1].mn == t[k].mn) t[k].cnt += t[k << 1 | 1].cnt;
}

void cg(int k, int tag, int upd){
    if (tag != 0) {
        t[k].mn += tag;
        t[k].tag += tag;
    }
    if (t[k].mn == t[k >> 1].mn || t[k].mn == 0) {
        t[k].sum += (ll)t[k].cnt * upd;
        t[k].upd += upd;
    }
}

void Pushdown(int k){
    cg(k << 1, t[k].tag, t[k].upd);
    cg(k << 1 | 1, t[k].tag, t[k].upd);
    t[k].tag = t[k].upd = 0;
}

void Build(int le, int ri, int k){
    if (le == ri) {
        t[k].mn = 1; t[k].cnt = 1;
        return;
    }
    int mi = (le + ri) >> 1;
    Build(le, mi, k << 1);
    Build(mi + 1, ri, k << 1 | 1);
    rel(k);
}

void cg(int le, int ri, int k, int L, int R, int tag, int upd){
    if (le != ri)    Pushdown(k);
    if (L <= le && ri <= R) return cg(k, tag, upd);
    int mi = (le + ri) >> 1;
    if (L <= mi)    cg(le, mi, k << 1, L, R, tag, upd);
    if (mi + 1 <= R)    cg(mi + 1, ri, k << 1 | 1, L, R, tag, upd);
    rel(k);
}

ll get(int le, int ri, int k, int L, int R){
    if (le != ri)    Pushdown(k);
    if (L <= le && ri <= R) return t[k].sum;
    int mi = (le + ri) >> 1;
    ll sum = 0;
    if (L <= mi)    sum += get(le, mi, k << 1, L, R);
    if (mi + 1 <= R)    sum += get(mi + 1, ri, k << 1 | 1, L, R);
    return sum;
}

deque<int> q_mx, q_mn;

int main(){
#ifdef cydiater
    freopen("input.in", "r", stdin);
#endif
    scanf("%d", &N);
    up (i, 1, N) scanf("%d", &a[i]);
    scanf("%d", &Q);
    up (i, 1, Q) {
        int le, ri; scanf("%d%d", &le, &ri);
        qry[i] = Query(le, ri, i);
    }
    sort(qry + 1, qry + Q + 1);
    Build(1, N, 1);
    int o = N + 1;
    down (i, Q, 1) {
        while (qry[i].le < o) {
            o--;
            while (!q_mx.empty() && a[o] > a[q_mx.back()]) {
                int cl = q_mx.back(), cr;
                q_mx.pop_back();
                cr = q_mx.empty() ? N : (q_mx.back() - 1);
                cg(1, N, 1, cl, cr, a[o] - a[cl], 0);
            }
            while (!q_mn.empty() && a[o] < a[q_mn.back()]) {
                int cl = q_mn.back(), cr;
                q_mn.pop_back();
                cr = q_mn.empty() ? N : (q_mn.back() - 1);
                cg(1, N, 1, cl, cr, a[cl] - a[o], 0);
            }
            cg(1, N, 1, o, N, -1, 0);
            cg(1, N, 1, o, N, 0, 1);
            q_mx.push_back(o);
            q_mn.push_back(o);
        }
        ans[qry[i].o] = get(1, N, 1, qry[i].le, qry[i].ri);
    }
    up (i, 1, Q) printf("%lld\n", ans[i]);
    return 0;
}