题解 P1903 【【模板】分块/带修改莫队（数颜色）】

huang_yue · 2017-11-16 21:13:12 · 题解

看了各位大大的题解，我发现我连“莫队”是什么都不知道……

但是我想说，暴力解法，也就是模拟，也可以AC（至少在我这里）

那么就没什么好说的，上代码

'''cpp

#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;
int a[10010]; //a[n]代表第n支画笔的颜色
bool basket[10010]; //作用在底下的代码中可以看出
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
    }
    for (int i = 0; i < m; ++i) {
        char op; int oa, ob;
        char v;
        while (isspace(v = fgetc(stdin))); //读掉所有空白字符，准备输入下一个操作
        ungetc(v, stdin); //重新放入刚刚读掉的字符，这是使isspace(v)为假的第一个字符，也即有效字符之一
        scanf("%c%d%d", &op, &oa, &ob);
        if (op == 'Q') { //查询
            int q = 0;
            memset(basket, 0, sizeof(basket));
            for (int i = oa; i <= ob; ++i) {
                if (!basket[a[i]]) {
                    basket[a[i]] = true;
                    ++q;
                } //这种颜色是否出现过，没有则颜色总数++
            }
            printf("%d\n", q);
        } else {
            a[oa] = ob; //设置颜色
        }
    }
    return 0;
}
'''