(CF940F)Machine Learning

发表于 | 分类于 ，

原题链接

思路:

带修莫队+暴力查询即可.

可以证明为何暴力查询能行:

假设答案为$x$, 则代表存在次数$1, 2, \cdots, x-1$都有, 数组的长度$n \ge x(x-1)/2 = O(x^2)$, 所以$x$是$O(\sqrt{n})$级别的.

代码:

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
#include <cstdio>
#include <cctype>
#include <cmath>
#include <algorithm>
using namespace std;
const int Mn(200500), Mq(100500);
template<typename T> void qrd(T& x) {
    x = 0;
    int c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + c - '0';
        c = getchar();
    }
}
template<typename T, typename... Ts> void qrd(T& x,Ts&... xs) { //快读
    qrd(x); qrd(xs...);
}

int ar[Mn], da[Mn]; //原数组, 离散化数组
int bln;    //块长
int getB(int x) {   //计算块编号
    return x/bln + (x%bln==0);
}
struct Qd { //查询
    int l, r, t, id;
    bool operator < (const Qd& rhs) const {
        if(getB(l)==getB(rhs.l)) {
            if(getB(r)==getB(rhs.r)) {
                return (getB(r)&1) ? t>rhs.t : t>rhs.t;
            }
            return (getB(l)&1) ? r<rhs.r : r>rhs.r;
        }
        return l<rhs.l;
    }
}aq[Mq];
struct Md { //修改
    int p, px, nx;
}am[Mq];
int cnt[Mn], ccnt[Mn];  //出现次数, 出现次数的出现次数
int ans[Mq];    //答案

int main() {
    int n,q;
    qrd(n,q);
    for(int i(1);i<=n;++i) {
        qrd(ar[i]);
        da[i] = ar[i];
    }
    /*处理修改与查询*/
    int cm(0), cq(0);
    for(int i(1);i<=q;++i) {
        int o, x, y;
        qrd(o, x, y);
        if(o==1) {
            aq[++cq] = {x,y,cm,cq};
        } else {
            am[++cm] = {x,ar[x],y};
            ar[x] = y;
            da[n+cm] = y;
        }
    }
    /*离散化*/
    sort(da+1,da+n+cm+1);
    int dl = unique(da+1,da+n+cm+1) - da - 1;
    for(int i(1);i<=n;++i) {
        ar[i] = lower_bound(da+1,da+dl+1,ar[i]) - da;
    }
    for(int i(1);i<=cm;++i) {
        Md& nm(am[i]);
        nm.px = lower_bound(da+1,da+dl+1,nm.px) - da;
        nm.nx = lower_bound(da+1,da+dl+1,nm.nx) - da;
    }
    bln = ceil( pow(1ll*n*(cm?cm:1), (cm?1./3:1./2)) );
    sort(aq+1,aq+cq+1);
    ccnt[0] = n+1;
    /*莫队*/
    int l(1), r(0), t(cm);
    for(int i(1);i<=cq;++i) {
        Qd& nq(aq[i]);
        while(l>nq.l) {
            --l;
            --ccnt[cnt[ar[l]]];
            ++cnt[ar[l]];
            ++ccnt[cnt[ar[l]]];
        }
        while(r<nq.r) {
            ++r;
            --ccnt[cnt[ar[r]]];
            ++cnt[ar[r]];
            ++ccnt[cnt[ar[r]]];
        }
        while(l<nq.l) {
            --ccnt[cnt[ar[l]]];
            --cnt[ar[l]];
            ++ccnt[cnt[ar[l]]];
            ++l;
        }
        while(r>nq.r) {
            --ccnt[cnt[ar[r]]];
            --cnt[ar[r]];
            ++ccnt[cnt[ar[r]]];
            --r;
        }
        while(t<nq.t) {
            ++t;
            if(am[t].p>=l && am[t].p<=r) {
                --ccnt[cnt[am[t].px]];
                --cnt[am[t].px];
                ++ccnt[cnt[am[t].px]];
                --ccnt[cnt[am[t].nx]];
                ++cnt[am[t].nx];
                ++ccnt[cnt[am[t].nx]];
            }
            ar[am[t].p] = am[t].nx;
        }
        while(t>nq.t) {
            if(am[t].p>=l && am[t].p<=r) {
                --ccnt[cnt[am[t].nx]];
                --cnt[am[t].nx];
                ++ccnt[cnt[am[t].nx]];
                --ccnt[cnt[am[t].px]];
                ++cnt[am[t].px];
                ++ccnt[cnt[am[t].px]];
            }
            ar[am[t].p] = am[t].px;
            --t;
        }
        for(int i(1);;++i) {    //暴力查询
            if(ccnt[i]==0) {
                ans[nq.id] = i;
                break;
            }
        }
    }
    for(int i(1);i<=cq;++i) {
        printf("%d\n",ans[i]);
    }
    return 0;
}