Zth's Blog

记录学习路上的点滴

0%

好序列 Namomo 每日一题div1 03-25

发表于 分类于

题目链接

题目

题意

给出一个长度为$n$的序列$A_1, A_2, …, A_n$， 定义一个序列$\{A\}$是好的， 当且仅当他的每一个子区间$[l, r]$满足至少存在一个$x$只出现了一次

数据范围

$T$组数据， $1 \leq T \leq 10^4$

$1 \leq n \leq 2 \times 10^5, \sum n \leq 10^6, 1 \leq A_i \leq 10^9$

题解

解法1

我们找到所有这样的区间： $[l, r], A_l = A_r$

然后我们尝试确认这个区间是不是合法的， 如果是合法的， 那必然有一个$i$， 使得

其中$Pre_i$为$A_i$上一次出现的位置， $Next_i$为$A_i$下一次出现的位置

然后不会实现， 故放弃

正解

思路

既然只要存在一个区间$[l, r]$不符合条件就能判定答案， 那我们就尝试找出一个不符合条件的区间

具体的， 我们枚举$l$， 这里显然有$r > l$， 考虑我们的右端点的范围， 这部分是解决这个问题的核心

显然对于$i > l$的每一个$A_i$， $A_{l, r}$序列要么不包含$A_i$, 要么包含$A_i$至少两次， 假设$A_{l, n}$包含一个数$x$， $fst[x], scd[x]$分别是其第一次， 第二次出现的位置

那么应该有$r < fst[x] \ or \ r >= scd[x]$， 对于每一个$x$， 我们将它对应的$r$的范围取一个交集， 如果有一个$i > l$被每个$x$对应的范围覆盖了， 那么这就是我们要找的$r$

区间交集可以用线段树来实现， 其他东西都好处理

代码

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
142
143
144
145
146
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

#define root 1, n, 1
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1

int t;
int n, m;
int a[200005], b[200005];
int p[200005];

int Find(int x) // 离散化
{
    return std:: lower_bound(b + 1, b + m + 1, x) - b;
}

struct SegmentTree // 线段树
{
    std:: vector<int> mx, c;

    SegmentTree(): mx(4 * n + 1, 0), c(4 * n + 1, 0) {};

    void Update(int rt)
    {
        mx[rt] = std:: max(mx[rt << 1], mx[rt << 1 | 1]);
    }

    void Color(int l, int r, int rt, int v)
    {
        mx[rt] += v;

        c[rt] += v;
    }

    void PushDown(int l, int r, int rt)
    {
        if(c[rt])
        {
            int mid = (l + r) >> 1;

            Color(lson, c[rt]);
            Color(rson, c[rt]);

            c[rt] = 0;
        }
    }

    void Modify(int l, int r, int rt, int ql, int qr, int v)
    {
        if(l >= ql && r <= qr)
        {
            Color(l, r, rt, v);

            return;
        }

        PushDown(l, r, rt);

        int mid = (l + r) >> 1;

        if(ql <= mid) Modify(lson, ql, qr, v);
        if(qr > mid) Modify(rson, ql, qr, v);

        Update(rt);
    }

    int Query(int l, int r, int rt, int ql, int qr)
    {
        if(l >= ql && r <= qr) return mx[rt];

        PushDown(l, r, rt);

        int mid = (l + r) >> 1;

        if(qr <= mid)
            return Query(lson, ql, qr);
        else if(ql > mid)
            return Query(rson, ql, qr);
        else
            return std:: max(Query(lson, ql, qr), Query(rson, ql, qr));
    }
};

int main()
{
    scanf("%d", &t);
    while(t --)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; i ++)
            scanf("%d", &a[i]), b[i] = a[i];
				// 到99行都是离散化
        std:: sort(b + 1, b + n + 1);
        m = std:: unique(b + 1, b + n + 1) - b - 1；

        for(int i = 1; i <= n; i ++) p[i] = Find(a[i]);
      
        std:: vector<int> fst(m + 1, 0), scd(m + 1, 0);

        SegmentTree st;

        int tps = 0; // 表示出现了几种数， 对应我们查找的位置要被多少个集合包含
        bool judge = true;
				// 枚举左端点并更新
        for(int i = n; i >= 1; i --)
        {
            if(fst[p[i]])
            {
                st.Modify(root, 1, fst[p[i]] - 1, -1);

                if(scd[p[i]]) st.Modify(root, scd[p[i]], n, -1);

                scd[p[i]] = fst[p[i]];
                st.Modify(root, scd[p[i]], n, 1);

                fst[p[i]] = i;
                if(fst[p[i]] - 1) st.Modify(root, 1, fst[p[i]] - 1, 1); // 防止越界

                if(st.Query(root, i + 1, n) == tps)
                {
                    judge = false;

                    break;
                }
            }
            else
            {
              	// a[l]如果第一次出现， 肯定不会是我们要找的区间的左端点， 因为a[l]只出现了一次
                tps ++;

                fst[p[i]] = i;
                if(fst[p[i]] - 1) st.Modify(root, 1, fst[p[i]] - 1, 1); // 防止越界
            }
        }

        if(judge)
            printf("non-boring\n");
        else
            printf("boring\n");
    }

    return 0;
}

具体实现的话

对于集合求交， 我们使用线段树， 对于一个集合包含的范围$[l, r]$， 我们将线段树上的这段区间$+1$， 这样我们就知道了每个位置被多少个集合所包含

前面提到了， 我们需要找到一个位置被每个集合所包含， 那么我们只需要关心最大值就好了， 如果被包含次数最多的位置都没有被所有集合包含， 就说明一定找不到， 所以这里使用线段树维护区间最大值

因为对于每个$l$我们要向右找$r$，$l - 1$的查找范围包含$l$的， 可以由$l$的范围很容易的转移过来， 所以$l$倒序枚举要好一些， 枚举的时候维护一下$fst, scd$并用线段树增删一些对应集合就可以了

另外由于$A_i$很大， 我们使用离散化， 用$p$数组代表

浅谈线段树

线段树是一个很巧妙的数据结构， 能够在$O(log)$的时间复杂度内解决区间的修改和查询问题(虽然常数很大)

个人理解线段树是基于二分的数据结构， 通过将区间一分为二分成$log$层， 使查询的量级仅为$O(log)$， 这也导致了线段树至少要开四倍空间

而众所周知线段树的区间修改并不是直接进行修改， 而是通过打标记进行延迟修改

但是不管是区间修改还是单点修改， 线段树有一个原则

一但某个节点维护的信息被改变了， 必须通过回溯中Update()更新它的父节点， 从而更新他的所有祖先节点

这个原则保证了每次查询的时候只要当前节点代表的区间范围完全位于查询区间的范围内， 就可以直接返回该节点维护的信息了， 因为子孙节点的更改必然已经更新了本节点， 我将这称为自下而上的更新， 区间修改和单点修改都存在自下而上的更新

而区间修改的线段树引入了自上而下的更新， 通过打标记来实现

线段树中一个节点被打标记的含义为： 此节点的值已经被改变， 但是他的儿子并没有被改变。 为什么不设计成他的儿子也被改变？ 个人理解是儿子也改变的话需要特判最后一层的叶子结点

打标记让我们可以在查询的时候通过将标记下放， 进行自上而下更新， 最终返回正确的节点信息， 也就是说，查询的时候必须要下放标记

那么为什么更新的时候也要下放标记呢？

原因就是之前说过的， 线段树要遵从自下而上更新的原则， 所以修改的时候一定要Update()， 但是如果我们没有下放标记， 会出现下面这种情况：

当前有一个节点$rt$带有标记， 并且他的所有祖先都没有标记， 也就是说$rt$的信息是完全正确的

这个时候， 我们要修改$rt << 1$， 也就是$rt$的左儿子节点区间的值， 但是我们在修改的时候没有下放标记

这个时候来一个询问， 问$rt << 1$的信息， 是完全可以返回正确的结果的， 因为查询的时候下放了标记

但是如果这个时候来的询问不是问$rt << 1$， 而是$rt$的信息， 就会得到错误的结果

原因很简单， 我们修改完$rt << 1$信息的时候， $rt << 1$的信息并不是正确的， 因为我们修改的时候没有把$rt$的信息传给它， 虽然后续查询的时候会给， 但是我们说过线段树必须要有自下而上的更新， 也就是说我们修改完$rt << 1$的信息之后会用它来更新$rt$的信息， $rt$的信息本来是正确的， 现在就被不正确的$rt << 1$信息更新了， 这时候我们如果查询$rt$节点， 就会得到错误的信息

所以修改的时候一定要下放标记！！！ 保证每个节点都被正确的子节点更新

以上纯属个人理解， 博客也是写给自己看的， 不喜勿喷