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

Lauzun · 2019-07-18 12:10:39 · 题解

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

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

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

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

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

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

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

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

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

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

• 离散化，不需要sort + unique，只需要额外开个数组复制一下即可，简单粗暴（不然怎么叫暴力）

• 我们发现每次暴力查询l \longrightarrow r的时候都需要memset一遍vis数组，所以我们可以采用标号法，即扫的过程中若vis[a[ j ]]还不是i就把他赋成i，并把ans加一。

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

  附上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 );
  }
  }