CF1969E E. Unique Array题解

E. Unique Array

题目翻译

​ 题目给我们一个长度为n的数组，一个子段被称为独特的，当且仅当子段中存在一个元素只出现了一次。我们可以进行一种操作选择数组中的任意一个元素将其替换成任意数字。我们需要输出我们最少需要进行几次操作可以使得数组中的所有子段都是独特子段。

思路

​ 首先我们容易想到一个O(n ^ 2 * lgn)的解法我们可以暴力的处理除所有不好的子段，根据我们操作的性质容易发现我们只要对子段中任意一个元素进行操作我们就一定可以使得包含这个元素的子段独特，于是问题转换成了一些区间，我们要选择最少数量的点，满足每个区间中至少包含一个节点。这是一个经典的贪心问题，我们直接按左端点或右端点排序，顺着贪心的取最边界的点即可。

​ 我们发现实际上有效的区间数量实际上是不超过n个的，因为所有完全覆盖了某个区间的区间都是没有意义的，于是我们可以考虑处理出每个左端点对应的最小的不独特的区间，考虑如何处理出这些区间。我们可以对每个位置的数处理出其下一个相同的数的位置，我们枚举每个左端点，初始将所有的数的第一个进行区间[x, nxt[x] - 1] + 1的操作，这意味着从x到nxt[x] - 1被我们标记了，是不可以选择的右端点，因为其是独特的，我们找到（i，n）的最小的右端点，满足其元素为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
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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
template<class T>
class SegmentTree{
private:
    int n;
    struct node{
        T pos;
        T minn;
    };
    std::vector<node> tree;
    std::vector<T> tag;
    std::vector<T> a;
 
    int ls(int p){
        return p << 1;
    }
 
    int rs(int p){
        return p << 1 | 1;
    }
 
    node merge(node a, node b){
        auto res = node();
        res.minn = std::min(a.minn, b.minn);
        res.pos = n + 1;
        if(a.minn == res.minn)
            res.pos = std::min(res.pos, a.pos);
        if(b.minn == res.minn)
            res.pos = std::min(res.pos, b.pos);
        return res;
    }
 
    void push_up(int p){
        tree[p] = merge(tree[ls(p)], tree[rs(p)]);
    }
    
    void build(int p, int pl, int pr){
        if(pl == pr){
            tree[p] = node();
            tree[p].minn = 0;
            tree[p].pos = pl;
            return;
        }
        int mid = (pl + pr) >> 1;
        build(ls(p), pl, mid);
        build(rs(p), mid + 1, pr);
        push_up(p);
    }
 
    void add(node& p, T d){
        p.minn += d;
    }
 
    void addtag(int p, int pl, int pr, T d){
        tag[p] += d;
        add(tree[p], d);
    }
 
    void push_down(int p, int pl, int pr){
        if(tag[p]){
            int mid = (pr + pl) >> 1;
            addtag(ls(p), pl, mid, tag[p]);
            addtag(rs(p), mid + 1, pr, tag[p]);
            tag[p] = 0;
        }
    }
 
    void update(int L, int R, int p, int pl, int pr, T d){
        if(L <= pl && pr <= R){
            addtag(p, pl, pr, d);
            return;
        }
        push_down(p, pl, pr);
        int mid = (pl + pr) >> 1;
        if(L <= mid)
            update(L, R, ls(p), pl, mid, d);
        if(R > mid)
            update(L, R, rs(p), mid + 1, pr, d);
        push_up(p);
    }
 
    node query(int L, int R, int p, int pl, int pr){
        if(L <= pl && pr <= R)
            return tree[p];
        push_down(p, pl, pr);
        int mid = (pl + pr) >> 1;
        if(L <= mid && R > mid)
            return merge(query(L, R, ls(p), pl, mid), query(L, R, rs(p), mid + 1, pr));
        if(L <= mid)
            return query(L, R, ls(p), pl, mid);
        if(R > mid)
            return query(L, R, rs(p), mid + 1, pr);
    }
 
public:
 
    void update(int L, int R, T d){
        update(L, R, 1, 1, n, d);
    }
 
    node query(int L, int R){
        return query(L, R, 1, 1, n);
    }
 
    SegmentTree(int len){
        n = len;
        tree.assign(n << 2, node());
        tag.assign(n << 2, 0);
        build(1, 1, n);
    }
 
    SegmentTree(std::vector<T> cur){
        //cur 是 1序列
        int len = cur.size() - 1;
        n = len;
        tree.assign(n << 2, node());
        tag.assign(n << 2, 0);
        a = cur;
        build(1, 1, n);
    }
};

void solve(){
    int n;
    std::cin >> n;
    std::vector<int> cur(n + 1, 0);
    for(int i = 1; i <= n; i++)
        std::cin >> cur[i];
    std::vector<int> last(n + 1, n + 1);
    std::vector<int> nxt(n + 1, n + 1);
    for(int i = n; i >= 1; i--){
        nxt[i] = last[cur[i]];
        last[cur[i]] = i;
    }

    auto seg = SegmentTree<int>(n + 1);
    for(int i = 1; i <= n; i++){
        if(last[i] != n + 1){
            seg.update(last[i], nxt[last[i]] - 1, 1);
        }
    }

    std::vector<std::pair<int, int>> res;
    for(int i = 1; i <= n; i++){
        auto p = seg.query(i, n);

        if(p.minn == 0){
            res.push_back({i, p.pos});
        }

        seg.update(i, nxt[i] - 1, -1);
        if(nxt[i] != n + 1)
            seg.update(nxt[i], nxt[nxt[i]] - 1, 1);            
    }
    
    int ans = 0;
    int ls = 0;
    for(auto p : res){
        if(p.ff <= ls){
            ls = std::min(ls, p.ss);
            continue;
        }
        ans += 1;
        ls = p.ss;
    }
    std::cout << ans << endl;
}