(luogu1903) 数颜色

发表于 分类于 ，

原题链接

思路：

这题是带修莫队的模板题

实际上带修莫队的操作和普通莫队大致相同，区别在于带修莫队多了一个 “时间轴”。

首先将修改与查询分开记录。每个查询记录一个值表示查询前有多少次修改（即 “时间”）。处理查询时通过 “时间” 来决定修改或撤销修改。

根据计算，块大小为 \(\sqrt[3]{nt}\) 时可达最优的时间复杂度 \(O(\sqrt[3]{n^4t})\)，其中 \(t\) 为修改次数，需要注意 \(t=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
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int Mn(200500), Ma(1000500);

int bln;    //块长
int arr[Mn];    //原数组
inline int calcb(int x) {   //计算x所在分块编号
    return x/bln + (x%bln==0);
}
struct Qyd {
    int l, r, t, id;
    bool operator < (const Qyd& rhs) const {    //询问排序
        if(calcb(l)==calcb(rhs.l)) {
            if(calcb(r)==calcb(rhs.r)) {
                return t < rhs.t;
            }
            return r < rhs.r;
        }
        return l < rhs.l;
    }
}aq[Mn];    //所有询问
int ans[Mn];    //询问答案

struct Mfd {    //修改
    int p, x, prx;  //修改位置，修改后的数，修改前的数
}am[Mn];    //所有修改

int cnt[Ma];    //计数数组

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    for(int i(1);i<=n;++i) {
        cin >> arr[i];
    }
    int cq(0),ct(0);    //询问数，修改数
    for(int i(1);i<=m;++i) {
        char o;
        int x, y;
        cin >> o >> x >> y;
        if(o=='Q') {
            ++cq;
            aq[cq] = {x,y,ct,cq};
        } else {
            am[++ct] = {x,y,arr[x]};
            arr[x] = y; //记录修改时同时直接修改数组
        }
    }
    bln = ceil(pow(1ll*n*(ct==0?1:ct),(ct==0?1./2:1./3)));  //注意t==0的判断，此时退化为普通莫队
    sort(aq+1,aq+cq+1);
    int l(1),r(0),t(ct),tans(0);    //时间设置为ct可不还原数组
    for(int i(1);i<=cq;++i) {
        Qyd& q(aq[i]);
        while(l>q.l) {
            --l;
            ++cnt[arr[l]];
            if(cnt[arr[l]]==1) {
                ++tans;
            }
        }
        while(r<q.r) {
            ++r;
            ++cnt[arr[r]];
            if(cnt[arr[r]]==1) {
                ++tans;
            }
        }
        while(l<q.l) {
            --cnt[arr[l]];
            if(cnt[arr[l]]==0) {
                --tans;
            }
            ++l;
        }
        while(r>q.r) {
            --cnt[arr[r]];
            if(cnt[arr[r]]==0) {
                --tans;
            }
            --r;
        }
        while(t<q.t) {  //修改
            ++t;
            Mfd& f(am[t]);
            arr[f.p] = f.x;
            if(f.p>=l && f.p<=r) {  //修改位置在询问区间中需要对计数数组和临时答案进行修改
                --cnt[f.prx];
                ++cnt[f.x];
                if(f.prx!=f.x && cnt[f.prx]==0) {
                    --tans;
                }
                if(f.prx!=f.x && cnt[f.x]==1) {
                    ++tans;
                }
            }
        }
        while(t>q.t) {  //撤回
            Mfd& f(am[t]);
            arr[f.p] = f.prx;
            if(f.p>=l && f.p<=r) {  //同上
                --cnt[f.x];
                ++cnt[f.prx];
                if(f.prx!=f.x && cnt[f.x]==0) {
                    --tans;
                }
                if(f.prx!=f.x && cnt[f.prx]==1) {
                    ++tans;
                }
            }
            --t;
        }
        ans[q.id] = tans;
    }
    for(int i(1);i<=cq;++i) {
        printf("%d\n",ans[i]);
    }
    return 0;
}