P1903「[国家集训队]数颜色」

1. 题目

题目链接：P1903「[国家集训队]数颜色」 。

题目描述

墨墨购买了一套 NN 支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：

  1. Q L R 代表询问你从第 L 支画笔到第 R 支画笔中共有几种不同颜色的画笔。

  2. R P Col 把第 P 支画笔替换为颜色 Col。

为了满足墨墨的要求，你知道你需要干什么了吗？

输入格式

第 11 行两个整数 N,MN,M，分别代表初始画笔的数量以及墨墨会做的事情的个数。

第 22 行 NN 个整数，分别代表初始画笔排中第 ii 支画笔的颜色。

第 33 行到第 2+M2+M 行，每行分别代表墨墨会做的一件事情，格式见题干部分。

输出格式

对于每一个 Query 的询问，你需要在对应的行中给出一个数字，代表第 L 支画笔到第 R 支画笔中共有几种不同颜色的画笔。

输入输出样例

输入 #1

1
2
3
4
5
6
7
6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

输出 #1

1
2
3
4
4
4
3
4

说明/提示

对于 30%30\% 的数据，n,m≤10000n,m \leq 10000。

对于 60%60\% 的数据，n,m≤50000n,m \leq 50000。

对于所有数据，n,m≤133333n,m \leq 133333。

所有的输入数据中出现的所有整数均大于等于 11 且不超过 10610^6。

2. 题解

分析

最近在学莫队算法，这是道带修改莫队的板子题。当然有其它更优的方法，但为了巩固最近所学其实是其它更优的方法还没学会，所以这里使用带修改莫队来解决这道题。

  • 首先将所有询问和修改离线存储下来，并根据修改次数记录每个询问的时间轴。
  • 然后对所有询问按照区间左边界 ll 所在块号为第一关键字，区间右边界 rr 所在块号为第二关键字，时间轴 tt 所在块号为第三关键字进行排序。
  • 接着维护一个计数数组 countcount，记录每种颜色的画笔数量，然后顺序处理每个询问。若当前询问的时间轴大于下一个询问的时间轴，则回滚修改；若当前询问的时间轴小于下一个询问的时间轴，则恢复修改。
  • 最后将答案按原询问顺序依次输出即可。

这里需要注意的是，在进行修改和回滚时，应该使用交换的方式，即将当前值和修改值进行交换，后面回滚时再交换回来。而不能仅仅通过事先维护的两个数组，即修改值数组和备份原值数组，来进行修改和回滚。因为有可能对同一个位置有多个修改，这样在回滚时需要回滚到上一次修改，而非原值。

代码

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
#include<bits/stdc++.h>
using namespace std;

#ifndef _MOBK_
#define _MOBK_
#define ll long long
#define il inline
#define re register
#define MAXN 2000100

char buf[200];

il ll read_number() {
    ll x = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x;
}

il ll read_capital() {
    char ch = getchar();
    while(ch < 'A' || ch > 'Z'){
        ch = getchar();
    }
    return ch;
}

il void write(ll x) {
    ll cnt = 0;
    while(x || !cnt) {
        buf[cnt++] = (x%10) + 48;
        x /= 10;
    }
    while(cnt) {
        putchar(buf[--cnt]);
    }
    putchar('\n');
}

// 分块大小
ll bz;
// 莫队
struct MOBK {
    // 查询区间
    struct Query {
        ll l, r, t, idx;
        bool operator < (const Query q) const {
            return l/bz != q.l/bz ? l < q.l : 
                r/bz != q.r/bz ? r < q.r : t < q.t;
                // (r/bz) & 1 ? t < q.t : t > q.t;
        }
    };
    // 修改记录
    struct Record {
        ll p, v;            // 下标，值
    };
    ll n, m, k;             // 数列长度，查询次数，修改次数
    ll curans;              // 当前查询答案
    ll count[MAXN];         // 计数数组
    ll result[MAXN];        // 答案数组（具体问题具体分析）
    Record modify[MAXN];    // 修改数组
    Query query[MAXN];      // 查询区间数组
    // 初始化
    MOBK() {
        curans = 0;
        memset(count, 0, sizeof(count));
    }
    MOBK(ll _n): n(_n) {
        bz = (ll)pow(n, 2.0/3);
        curans = 0;
        memset(count, 0, sizeof(count));
    }
    // 区间长度增一
    il void add(ll x) {
        curans += count[x] == 0 ? 1 : 0;
        ++count[x];
    }
    // 区间长度减一
    il void del(ll x) {
        --count[x];
        curans -= count[x] == 0 ? 1 : 0;
        
    }
    // 求解答案
    void solver(ll *a) {
        sort(query, query+m);
        re ll l = query[0].l;
        re ll r = query[0].l-1;
        re ll t = 0;
        for(re ll i = 0; i < m; ++i) {
            // printf("(%d,%d,%d)\n", query[i].l, query[i].r, query[i].t);
            while(l < query[i].l) {
                del(a[l++]);
            }
            while(l > query[i].l) {
                add(a[--l]);
            }
            while(r < query[i].r) {
                add(a[++r]);
            }
            while(r > query[i].r) {
                del(a[r--]);
            }
            while(t < query[i].t) {
                if(l <= modify[t].p && modify[t].p <= r) {
                    del(a[modify[t].p]);
                    add(modify[t].v);
                }
                swap(a[modify[t].p], modify[t].v);
                ++t;
            }
            while(t > query[i].t) {
                --t;
                if(l <= modify[t].p && modify[t].p <= r) {
                    del(a[modify[t].p]);
                    add(modify[t].v);
                }
                swap(a[modify[t].p], modify[t].v);
            }
            result[query[i].idx] = curans;
        }
        for(ll i = 0; i < m; ++i) {
            // write(result[i]);
            printf("%lld\n", result[i]);
        }
    }
};
#endif

int main()
{
    char option;
    ll q = 0, r = 0;
    ll n = read_number();
    ll m = read_number();
    static ll a[MAXN] = {0};
    static MOBK mobk = MOBK(n);
    for(re ll i = 0; i < n; ++i) {
        a[i] = read_number();
    }
    for(re ll i = 0; i < m; ++i) {
        option = read_capital();
        if(option == 'Q') {
            mobk.query[q].l = read_number() - 1;
            mobk.query[q].r = read_number() - 1;
            mobk.query[q].t = r;
            mobk.query[q].idx = q;
            ++q;
        } else {
            mobk.modify[r].p = read_number() - 1;
            mobk.modify[r].v = read_number();
            ++r;
        }
    }
    mobk.m = q;
    mobk.k = r;
    mobk.solver(a);
    return 0;
}