洛谷—P1903—[国家集训队]数颜色 / 维护队列 离散化+暴力优化

· · 题解

前两天学莫队的时候，在余姚集训的好看小姐姐给小萌新推荐了一道带修莫队题。

当时觉得用莫队写应该不是很难，就放下了一直没写。没想到今天讲课的好看学姐就把这个题布置出来了qwq。

本来准备老老实实写带修莫队，结果在某blog上看到一篇题解说可以离散化+暴力。然后就attempt了一下，发现还真的能过。

去向小姐姐炫耀了一下结果被嘲讽交你咕会挂，顺带被小姐姐再次教育了一番要好好写莫队。

你咕数据有加强，刚开始爆彩虹，RE + TLE + WA，最后数组开大，加个快读，吸个氧气，cout改成printf就卡过去了（其实也不算卡啦，只用了不到一半的时间）

然后成功地俘获了小姐姐芳心，应她的要求才来写的题解[大雾]

好了进入正题（前面讲那么多只是为了让各位dalao注意到这篇暴力qwq）

这篇暴力和外面那些妖艳暴力可不一样（手动狗头）。

大体思路嘛······暴力还需要什么思路。在线做，如果要求修改就直接修改，如果要询问就从l\longrightarrow r扫一遍，bool一个vis数组记录扫到的数出现了没有，如果扫到的数没出现那么vis改为true，然后ans++。

但是这样子会T飞掉，所以要加两个小优化，不加也能拿高分但是没办法AC。（没办法AC\Longleftrightarrow不能得到小姐姐的夸赞qwq）

别的就真的没什么好说的了，暴力即可。

附上AC代码，数组开的比较匆忙，可能开大了。记得吸氧，不然90。

// luogu-judger-enable-o2
#include<stdio.h>
#define maxn 10000005
#define maxm 100005
using namespace std;
int n, m, l, r, ans, cnt = 0;
int a[maxn], b[maxm];
int vis[maxm + 10000];
char c;
inline int read() {
    int s = 0, w = 1; 
    char ch = getchar();
    while( ch < '0' || ch > '9' ) {
        if( ch == '-' ) w = -1;
        ch = getchar();
    }
    while( ch >= '0' && ch <= '9' ) {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * w;
} 
int main() {
    n = read(); m = read();
    for( int i = 1; i <= n; i ++ ) {
        int o = read();
        if( !a[o] ) a[o] = ++ cnt;
        b[i] = a[o];
    }
    for( int i = 1; i <= m; i ++ ) {
        c = ' ';
        while( c != 'Q' && c != 'R' ) c = getchar();
        l = read(); r = read();
        if( c == 'R' ) {
            if( !a[r] ) a[r] = ++ cnt;
            b[l] = a[r];
            continue;
        }
        ans = 0;
        for( int j = l; j <= r; j ++ ) {
            if( vis[b[j]] != i ) {
                ans ++;
                vis[b[j]] = i;
            }
        }
        printf( "%d\n", ans );
    }
}