【BZOJ2120】【块状链表】数颜色

Description

墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？

Input

第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。

Output

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

Sample Input

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

Sample Output

4
4
3
4

HINT

对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。

【分析】

好吧，正解应该是树套树，但是...分块可以做....

我的方法很暴力...改了暴力重建..居然还可以过。。

 /*

 宋代

 辛弃疾

 青玉案·元夕

 东风夜放花千树。更吹落、星如雨。宝马雕车香满路。凤箫声动，玉壶光转，一夜鱼龙舞。

 蛾儿雪柳黄金缕。笑语盈盈暗香去。众里寻他千百度。蓦然回首，那人却在，灯火阑珊处。

 */

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <vector>

 #include <utility>

 #include <iomanip>

 #include <string>

 #include <cmath>

 #include <queue>

 #include <assert.h>

 #include <map>

 #include <ctime>

 #include <cstdlib>

 #include <stack>

 #include <set>

 #define LOCAL

 const int INF = ;

 const int MAXN =   + ;

 const int maxnode =  *  +  * ;

 const int MAXM=  + ;

 using namespace std;

 int tot;

 int n, q, block_size;

 int data[MAXN];

 int belong[MAXN], block[MAXN];

 int t[MAXN],last[MAXM];

 //寻找第x块内有多少个比v要小的

 int find(int x, int v){

     int l = (x - ) * block_size + , r = min(x * block_size, n);

     int first = l;

     while (l <= r){

           int mid = (l + r) >> ;

           if (block[mid] < v) l = mid + ;

           else r = mid - ;

     }

     return l - first;

 }

 int query(int l, int r){

     int ans = ;

     if (belong[l] == belong[r]){

        for (int i = l; i <= r; i++) if (t[i] < l) ans++;

     }else {

           for (int i = l; i <= block_size * belong[l]; i++) if (t[i] < l) ans++;

           for (int i = block_size * (belong[r] - ) + ; i <= r; i++) if (t[i] < l) ans++;

     }

     for (int i = belong[l] + ; i < belong[r]; i++) ans += find(i, l);

     return ans;

 }

 //处理块

 void build(int x){

     int l = (x - ) * block_size + , r = min(x * block_size, n);

     for (int i = l; i <= r; i++) block[i] = t[i];

     sort(block + l, block + r + );//对一个块的上一次出现的颜色进行排序

 }

 //将x的颜色改变为v

 void change(int x, int v){

      for (int i = ; i <= n; i++) last[data[i]] = ;//暴力重构

      data[x] = v;

      for (int i = ; i <= n; i++){

          int tmp = t[i];

          t[i] = last[data[i]];

          if (tmp != t[i]) build(belong[i]);

          last[data[i]] = i;

      }

 }

 void init(){

      scanf("%d%d", &n, &q);

      for (int i = ; i <= n; i++) scanf("%d", &data[i]);

      block_size = (int)(sqrt(n * 1.0));

      //tot记录总共块的个数

      tot = n / block_size;

      if (n % block_size) tot++;

      for (int i = ; i <= n; i++){

          //链表式插入

          t[i] = last[data[i]];

          last[data[i]] = i;

          belong[i] = (i - ) / block_size + ;

      }

      for (int i = ; i <= tot; i++){ build(i);

      }

 }

 void work(){

      for (int i = ; i <= q; i++){

          char str[];

          scanf("%s", str);

          if (str[] == 'Q'){

             int l, r;

             scanf("%d%d", &l, &r);

             printf("%d\n", query(l, r));

          }else{

             int l, x;

             scanf("%d%d", &l, &x);

             change(l, x);

          }

      }

 }

 int main(){

     init();

     work();

     return ;

 }

巴特西