[2019银川网络赛-L] Continuous Intervals

发表于 | 更新于 | 分类于 ， ，
本文字数： 22k

链接

\(\text{2019银川网络赛-L.Continuous Intervals}\)

题意

  给定一个长度为\(n\)的正整数序列\(a\)，对于一个\([l,r]\)区间内排序后，区间内任意相邻两数的差的绝对值都小于1，这样的区间有多少个。

  输入格式：第一行一个\(t\)，表示\(t\)个样例，之后每个样例的第一行输入一个数\(n\)，第二行\(n\)个数表示序列\(a\)。

  数据范围：\(1\leq n\leq 10^6,1\leq a_i\leq 10^9\).

  输出格式：对于每个查询操作，输出一行一个结果Case #x: y，表示第\(x\)个样例的结果是\(y\)。

分析

  排序后的区间任意相邻两数的差小于等于1，\(max、min\)为区间最大值、最小值，\(cnt\)为区间数的种类，那么显然的，任意一个区间都有\(max-min-cnt\geq -1\)，而对于此题来说即是要求满足\(max-min-cnt= -1\)的区间的个数，我们可以枚举\(r\)，求满足条件的\(l\)的个数。

  我们可以用线段树动态的维护\(max-min-cnt\)的最小值，以及这个最小值的个数；

  当枚举\(r\)的过程中，我们需要考虑当前这个数\(a[x]\)，对于\(max、min、cnt\)产生的影响，即当\(a[x]\)作为区间最大值，作为区间最小值所影响到的区间，以及\(a[x]\)上一次出现到\(x\)位置的区间内对\(cnt\)的影响。

  使用两个单调栈能够求出\(a[x]\)作为区间最大值，作为区间最小值所影响到的区间，在这个区间内进行修改\(max-min-cnt\)，加上\(a[x]\)带来的影响

  https://blog.csdn.net/Cassie_zkq/article/details/100388082这篇博客讲的比较清楚。

代码

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define INF 0x7f7f7f7f
#define MAXN 100005
#define N 200005
#define P 2
//#define MOD 99991
#define MOD(a, b) a >= b ? a % b + b : a

typedef long long ll;

namespace fastIO {
    //#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin),
    // p1 == p2) ? EOF : *p1++) char buf[(1 << 22)], *p1 = buf, *p2 = buf;
    inline int read() {
        char c = getchar();
        int x = 0, f = 1;
        while (c < '0' || c > '9') {
            if (c == '-')
                f = -1;
            c = getchar();
        }
        while (c >= '0' && c <= '9')
            x = x * 10 + c - '0', c = getchar();
        return x * f;
    }
}  // namespace fastIO

namespace segment_Tree {
    struct Tree {
        int l, r, minm, lazy, sum;
    } tree[4 * MAXN];

    inline void push_up(int x) {
        int lmin = tree[x << 1].minm, rmin = tree[x << 1 | 1].minm;
        int lsum = tree[x << 1].sum, rsum = tree[x << 1 | 1].sum;
        tree[x].minm = std::min(lmin, rmin);
        if (lmin == rmin)
            tree[x].sum = lsum + rsum;
        else if (lmin < rmin)
            tree[x].sum = lsum;
        else
            tree[x].sum = rsum;
    }

    inline void push_down(int x) {
        int lz = tree[x].lazy;
        tree[x << 1].lazy += lz, tree[x << 1 | 1].lazy += lz;
        tree[x << 1].minm += lz, tree[x << 1 | 1].minm += lz;
        tree[x].lazy = 0;
    }

    inline void build(int x, int l, int r) {
        tree[x].l = l, tree[x].r = r;
        tree[x].minm = 0, tree[x].lazy = 0, tree[x].sum = r - l + 1;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(x << 1, l, mid);
        build(x << 1 | 1, mid + 1, r);
    }

    inline void update(int x, int l, int r, int val) {
        int l1 = tree[x].l, r1 = tree[x].r;
        if (l <= l1 && r1 <= r) {
            tree[x].minm += val;
            tree[x].lazy += val;
            return;
        }
        int mid = (l1 + r1) >> 1;
        push_down(x);
        if (l <= mid)
            update(x << 1, l, r, val);
        if (r > mid)
            update(x << 1 | 1, l, r, val);
        push_up(x);
    }

    /*inline int query(int x, int l, int r) {
        int le = tree[x].l, ri = tree[x].r;
        if (l <= le && ri <= r) {
            return tree[x].max;
        }
        int mid  = (le + ri) >> 1;
        int maxm = 0;
        if (l <= mid)
            maxm = max(maxm, query(x << 1, l, r));
        if (r > mid)
            maxm = max(maxm, query(x << 1 | 1, l, r));
        return maxm;
    }*/
}  // namespace segment_Tree

using namespace fastIO;
using namespace std;
using namespace segment_Tree;

int t, n, a[100005];
int st1[100005], st2[100005], t1, t2;

int main() {
    cin >> t;
    int cnt = 0;
    while (t--) {
        cnt++;
        cin >> n;
        t1 = 0, t2 = 0;
        memset(a, 0, sizeof(a));
        unordered_map<int, int> pos;
        build(1, 1, n);
        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            update(1, 1, n, -1);
            while (t1 && a[i] > a[st1[t1]]) {
                update(1, st1[t1 - 1] + 1, st1[t1], a[i] - a[st1[t1]]);
                t1--;
            }
            st1[++t1] = i;
            while (t2 && a[i] < a[st2[t2]]) {
                update(1, st2[t2 - 1] + 1, st2[t2], a[st2[t2]] - a[i]);
                t2--;
            }
            st2[++t2] = i;
            update(1, pos[a[i]] + 1, i, -1);
            pos[a[i]] = i;
            ans += 1ll * tree[1].sum;
        }
        printf("Case #%d: %lld\n", cnt, ans);
    }
}