Codeforces

Codeforces 1000F

https://codeforces.com/contest/1000/problem/F
這題給定一個數列A，給定Q筆詢問區間[L, R]，有沒有重複的數字，如果有請輸出任意一個，否則輸出0。

這題做參考IONCamp 2019講義，用離線做法，先將所有詢問讀入，然後依右邊界讀入，維護一個陣列pre，紀錄該位置的值上一次出現的位置，如果該位置的值和其他同值的位置比，不是最右邊的，就位置的pre就設為無限大，對於每筆詢問[L, R]，只要查詢u=min(pre[L],pre[L + 1]...,pre[R])，如果u<L代表有一個值只在這區間出現一次。
將相同值不在最右邊的所有位置其pre值設為無限大的用意，在於最該值取min不會讓最終答案<L，他無法成為解答(在他右邊至少有一個相同值的位置)。

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
167
168
169
170
171
172
173
174
175
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int,int>;
const int MXN = 500005;
struct Node{
    int val, mn;
    Node *lc, *rc;
    Node()
    {
        lc = rc = nullptr;
        mn = MXN;
    }
    void pull()
    {
        if(lc == nullptr)
        {
            mn = rc->mn;
            val = rc->val;
        }
        else if(rc == nullptr && mn > rc->mn)
        {
            mn = lc->mn;
            val = lc->val;
        }
        else if(lc->mn < rc->mn)
        {
            mn = lc->mn;
            val = lc->val;
        }
        else
        {
            mn = rc->mn;
            val = rc->val;
        }
        return;
    }
};
struct Query{
    int L, R, i, ans;
};
vector<int> a, pre, last;
vector<Query> vq;

Node* build(int L, int R)
{
    Node *node = new Node();
    if(L == R)
    { 
        node->val = a[L];
        node->mn = pre[L];
        return node;
    }
    int M = (L + R) >> 1;
    node->lc = build(L, M);
    node->rc = build(M + 1, R);
    node->pull();
    return node;
}

void modify(Node *node, int L, int R, int p)
{
    if(L == R)
    {
        node->val = a[p];
        node->mn = pre[p];
        return;
    }
    int M = (L + R) >> 1;
    if(p <= M)
    {
        modify(node->lc, L, M, p);
    }
    else
    {
        modify(node->rc, M + 1, R, p);
    }
    node->pull();
    return;
}

PII query(Node *node, int L, int R, int qL, int qR)
{
    if(qL <= L && R <= qR)
    {
        return {node->mn, node->val};
    }
    int M = (L + R) >> 1;
    if(qR <= M)
    {
        return query(node->lc, L, M, qL, qR);
    }
    if(qL > M)
    {
        return query(node->rc, M + 1, R, qL, qR);
    }
    else
    {
        return min(query(node->lc, L, M, qL, qR), query(node->rc, M + 1, R, qL, qR));
    }
    
}

int main()
{
    cin.tie(nullptr); ios_base::sync_with_stdio(false);
    int n, q;
    cin >> n;
    a.resize(n + 5);
    pre.resize(MXN);
    last.resize(MXN);
    fill(pre.begin(), pre.end(), MXN);
    fill(last.begin(), last.end(), MXN);
    for(int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    Node *root = build(1, n);
    
    cin >> q;
    vq.resize(q + 5);
    for(int i = 0; i != q; ++i)
    {
        vq[i].i = i;
        cin >> vq[i].L >> vq[i].R;
    }
    sort(vq.begin(), vq.begin() + q, 
        [](Query lhs, Query rhs)
        {
            return lhs.R < rhs.R;
        });
    
    int ni = 1;
    for(int i = 0; i != q; ++i)
    {
        while(ni <= vq[i].R)
        {
            int tmp = last[a[ni]];
            if(tmp != MXN)
            {
                pre[tmp] = MXN;
                modify(root, 1, n, tmp);
                pre[ni] = tmp;
            }
            else
            {
                pre[ni] = 0;
            }
            last[a[ni]] = ni;
            
            modify(root, 1, n, ni);
            ++ni;
        }
        auto ans = query(root, 1, n, vq[i].L, vq[i].R);
        // cout << vq[i].L << ' ' << vq[i].R << '\n';
        // cout << ans.first << '-' << ans.second << '\n';
        if(ans.first < vq[i].L)
        {
            vq[i].ans = ans.second;
        }
        else
        {
            vq[i].ans = 0;
        }
    }
    
    sort(vq.begin(), vq.begin() + q, 
        [](Query lhs, Query rhs)
        {
            return lhs.i < rhs.i;
        });
    for(int i = 0; i != q; ++i)
    {
        cout << vq[i].ans << '\n';
    }
}

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Recommended Posts