DDOSvoid's Blog

CF 997E Good Subsegments

发表于 分类于
本文字数： 3.1k 阅读时长 ≈ 3 分钟

题目描述

http://codeforces.com/problemset/problem/997/E

简要题意：给定一个长度为 $n$ 的排列 $p$，现在有 $m$ 次询问，每次询问区间 $[l,r]$ 中有多少子区间是连续的，一个区间是连续的，当且仅当这个区间中的数排列后形成一个公差为 $1$ 的等差数列

$n,m\le 1.2\times 10^5$

Solution

对于连续区间这个定义，我们已经很熟悉了，如果一个区间是连续区间，那么一定满足 $max-min-(r-l)=0$，且我们注意到对于任何区间都有 $max-min-(r-l)\ge 0$

然后对于询问的形式，容易想到离线后扫描线然后维护一个历史值，这里我们注意到我们要求的是 $0$ 的个数且 $0$ 一定是历史最小值，另外关于 $max-min-(r-l)$ 这个东西可以利用单调栈，那么我们现在就需要维护区间加，求区间历史最小值的个数，为了维护这些东西，我们需要在线段树上维护：区间最小值、区间最小值的个数、区间历史最小值、区间历史最小值的个数、区间加标记、区间历史最小值加标记、区间历史最小值加标记的个数

时间复杂度 $O(n\log ^n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <stack>
#include <vector>
#define maxn 120010
#define ll long long
#define INF 1000000000
using namespace std;

int n, m, a[maxn];

#define lc i << 1
#define rc i << 1 | 1
struct Seg {
    ll mn, cmn, tmn, ctmn, add, tadd, ctadd;
    // mn 最小值
} T[maxn * 4];
inline void maintain(int i) {
    T[i].mn = min(T[lc].mn, T[rc].mn);
    T[i].tmn = min(T[lc].tmn, T[rc].tmn); 
    if (T[lc].mn == T[rc].mn) T[i].cmn = T[lc].cmn + T[rc].cmn;
    else T[i].cmn = T[lc].mn < T[rc].mn ? T[lc].cmn : T[rc].cmn; 
    if (T[lc].tmn == T[rc].tmn) T[i].ctmn = T[lc].ctmn + T[rc].ctmn;
    else T[i].ctmn = T[lc].tmn < T[rc].tmn ? T[lc].ctmn : T[rc].ctmn;
}

void build(int i, int l, int r) {
    if (l == r) return T[i] = { 0, 1, 0, 1 }, void(); 
    int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r); 
    maintain(i); 
}

inline void Update(int i, ll add, ll tadd, ll ctadd) {
    if (T[i].tmn > T[i].mn + tadd) {
        T[i].tmn = T[i].mn + tadd;
        T[i].ctmn = T[i].cmn * ctadd;
    } else if (T[i].tmn == T[i].mn + tadd) 
        T[i].ctmn += T[i].cmn * ctadd;
    T[i].mn += add;
    if (T[i].tadd > T[i].add + tadd) { 
        T[i].tadd = T[i].add + tadd;
        T[i].ctadd = ctadd;
    } else if (T[i].tadd == T[i].add + tadd) 
        T[i].ctadd += ctadd;
    T[i].add += add;
}

inline void pushdown(int i) {
    ll &add = T[i].add, &tadd = T[i].tadd, &ctadd = T[i].ctadd;
    Update(lc, add, tadd, ctadd); Update(rc, add, tadd, ctadd);
    add = tadd = ctadd = 0; 
}

void update(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return Update(i, v, v, 1);
    int m = l + r >> 1; pushdown(i);
    update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
    maintain(i); 
}

ll query(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return T[i].ctmn;
    int m = l + r >> 1; pushdown(i); 
    return query(lc, l, m, L, R) + query(rc, m + 1, r, L, R);
}

vector<pair<int, int>> A[maxn];
ll ans[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        A[y].emplace_back(x, i); 
    }
    stack<int> S, T; build(1, 1, n); S.push(0); T.push(0);
    for (int i = 1; i <= n; ++i) {
        
        while (S.size() > 1 && a[i] > a[S.top()]) {
            int tp = S.top(); S.pop(); 
            update(1, 1, n, S.top() + 1, tp, a[i] - a[tp]);
        } S.push(i); 
        
        while (T.size() > 1 && a[i] < a[T.top()]) {
            int tp = T.top(); T.pop();
            update(1, 1, n, T.top() + 1, tp, a[tp] - a[i]); 
        } T.push(i); 

        update(1, 1, n, 1, i - 1, -1); 
        for (auto [k, id] : A[i]) ans[id] = query(1, 1, n, k, i);
    }
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
    return 0;
}