数颜色 / 维护队列

题意：

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

  1. Q L R代表询问你从第L支画笔到第支画笔***有几种不同颜色的画笔。
  2. R P Col 把第支画笔替换为颜色。

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

题解：

带修莫队板子题，只是在普通莫队的基础上增加了一维经历的修改次数。
带修莫队的排序方法：

  • 第一关键字：左端点所在块编号，从小到大排序。
  • 第二关键字：右端点所在块编号，从小到大排序。
  • 第三关键字：经历的修改次数。也可以说是询问的先后，先询问的排前面。

不同与普通的莫队，带修莫队将块的大小从改为
复杂度为
带修莫队只适用于单点修改，而不是适用于区间修改
复杂度计算如下：
带修莫队的做法是设法消除值互不相等造成的时间戳摇摆，让值的分类粗一些，按块号、后块号、最后时间戳的顺序给查询排序。耗时由部分组成（假设）：

  1. 的转移耗时。
  2. 转移，在一个块内，的每个块内耗时，有块，耗时。再乘以块的个数，的转移总耗时。
  3. 还有时间戳耗时，对每个固定的块、块，时间戳已有序，其中无论查询次数多少，耗时，块、块共种组合，所以时间戳总耗时。
    三者合计耗时。该计算复杂性在时达到最小，最小耗时。

可能写得太烂了，在洛谷上只能开O2优化才能过

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 133333 + 5;
const int MAXN = 1e6 + 5;
//c1表示有多少个询问操作，c2表示有多少个更改操作
int n, m, block, c1, c2, ans;
//Q[i][0] 表示第i次操作需更改的位置
//Q[i][1] 表示第i次操作更改位置的现在颜色
//Q[i][2] 表示第i次操作要改成的颜色
int C[maxn], val[maxn], Ans[maxn], sum[MAXN], Q[maxn][3];
struct Node
{
   //l,r分别是询问的左右端点,c是该询问之前的修改操作次数，id是这个操作的位置
   int l, r, c, id;
   bool operator<(const Node a) const
   {
      if (l / block == a.l / block)
      {
         if (r / block == a.r / block)
            return id < a.id;
         return r < a.r;
      }
      return l < a.l;
   }
} q[maxn];
char op[10];
void Add(int x)
{
   if (!sum[x])
      ans++;
   sum[x]++;
}
void Del(int x)
{
   sum[x]--;
   if (!sum[x])
      ans--;
}
int main()
{
   scanf("%d%d", &n, &m);
   block = pow(n, (double)2 / (double)3);
   for (int i = 1; i <= n; ++i)
   {
      scanf("%d", &val[i]);
      C[i] = val[i];
   }
   for (int i = 1, a, b; i <= m; i++)
   {
      scanf("%s%d%d", op, &a, &b);
      if (op[0] == 'Q')
      {
         q[c1].l = a;
         q[c1].r = b;
         q[c1].id = c1;
         q[c1].c = c2;
         c1++;
      }
      else
      {
         Q[c2][0] = a;
         Q[c2][1] = C[a];
         Q[c2][2] = C[a] = b;
         c2++;
      }
   }
   sort(q, q + c1);
   int l = 1, r = 0, lst = 0;
   for (int i = 0; i < c1; ++i)
   {
      while (lst < q[i].c)
      {
         if (l <= Q[lst][0] && Q[lst][0] <= r)
         {
            Del(Q[lst][1]);
            Add(Q[lst][2]);
         }
         val[Q[lst][0]] = Q[lst][2];
         lst++;
      }
      while (lst > q[i].c)
      {
         if (l <= Q[lst - 1][0] && Q[lst - 1][0] <= r)
         {
            Del(Q[lst - 1][2]);
            Add(Q[lst - 1][1]);
         }
         val[Q[lst - 1][0]] = Q[lst - 1][1];
         lst--;
      }
      while (l > q[i].l)
         l--, Add(val[l]);
      while (r < q[i].r)
         r++, Add(val[r]);
      while (l < q[i].l)
         Del(val[l]), l++;
      while (r > q[i].r)
         Del(val[r]), r--;
      Ans[q[i].id] = ans;
   }
   for (int i = 0; i < c1; ++i)
      printf("%d\n", Ans[i]);
   return 0;
}