DDOSvoid's Blog

Luogu P4065 [JXOI2017]颜色

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

题目描述

https://www.luogu.com.cn/problem/P4065

Solution

我们考虑枚举右端点，然后统计合法的左端点

我们令 $max_i$ 表示颜色 $i$ 的最靠右的位置，$min_i$ 同理

那么对于合法的区间 $[l,r]$，必须要满足 $l \le min_{col_i},max_{col_i}\le r$

我们考虑减少一个条件，对于枚举到的右端点 $r$，我们确定一个最小的 $l$，使得对于 $i\in [l,r],max_{col_i}\le r$

这个 $l$ 可以在枚举右端点的时候拿栈来维护

那么我们接下来要求有多少 $i\in [l,r],min_{col_i}\ge l$，这个东西可以拿主席树做

或者我们考虑对于一个 $max_{col_i} \le r$ 的一个颜色，$[min_{col_j}+1,max_{col_j}]$ 这些左端点不合法

且随着右端点的增大，这些左端点不会变得合法，所以我们每次将这些区间置 $0$ 即可，只需要线段树就行

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
#include <iostream>
#include <cstdio>
#include <stack>
#define maxn 300010
#define ll long long 
using namespace std;

int n, m, a[maxn], mx[maxn], mn[maxn];

#define lc i << 1
#define rc i << 1 | 1
struct Seg {
    int f0, v;
} T[maxn * 4];
inline void maintain(int i) { T[i].v = T[lc].v + T[rc].v; }

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

inline void Up(int i) { T[i].f0 = 1; T[i].v = 0; }

inline void pushdown(int i) {
    int &f0 = T[i].f0; if (!f0) return ; 
    Up(lc); Up(rc);
}

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

int 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].v;
    int m = l + r >> 1; pushdown(i);
    return query(lc, l, m, L, R) + query(rc, m + 1, r, L, R);
}

ll ans;
void init() {
    ans = 0; build(1, 1, n);
    for (int i = 1; i <= n; ++i) mn[i] = n + 1, mx[i] = 0; 
}

stack<int> S;
void work() {
    cin >> n; init(); 
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) mn[a[i]] = min(mn[a[i]], i), mx[a[i]] = max(mx[a[i]], i);
    for (int i = 1; i <= n; ++i) {
        if (mx[a[i]] == i) update(1, 1, n, mn[a[i]] + 1, i);
        else S.push(i); int p = 0; 
        while (!S.empty() && mx[a[S.top()]] <= i) S.pop();
        if (!S.empty()) p = S.top();
        ans += query(1, 1, n, p + 1, i); 
    } cout << ans << endl; 
    return ; 
}

int main() {
    int T; cin >> T;
    while (T--) work(); 
    return 0;
}