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

Data Range

对于 100% 的数据,\(n \leq 10000, m \leq 10000\), 修改操作不多于 \(1000\) 次, 所有的输入数据中出现的所有整数均大于等于 \(1\) 且不超过 \(10^6\).

Explanation

第一感觉是这道题可以用 \(O(n^\frac{5}{3})\) 的待修改莫队算法来做, 但是不会写, 所以 就放弃了.

然后发现有一个特性, 计某一个位置之前的和他相同的颜色为 \(pre_i\), 则在一段区间 \([L, R]\) 之内某一个颜色出现至少两次的充要条件为 \(pre_i \geq L\). 于是我们把整个数列分成 \(m\) 块, 然后对每一个块内的 \(pre_i\) 排一下序, 得到的就可以用二分查找来 获得 Query 的答案.

对于 Change, 由于修改次数不多, 所以每次把整个序列扫一遍就可以了 (虽然觉得很暴力但是这毕竟是 \(O(跑得过)\). ......

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 1001000;

class DuplicateFinder
{
public:
    int n, m, blk;
    int c[maxn], last[maxn], plast[maxn],
        pre[maxn], pos[maxn];
    void reset_blk(int x)
    {
        int l = (x - 1) * blk + 1,
            r = min(x * blk, n);
        for (int i = l; i <= r; i++)
            pre[i] = plast[i];
        sort(pre + l, pre + r + 1);
        return ;
    }
    int find(int x, int v)
    {
        int l = (x - 1) * blk + 1,
            r = min(x * blk, n);
        int first = l;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (pre[mid] < v)
                l = mid + 1;
            else
                r = mid - 1;
        }
        return l - first;
    }
    int query(int l, int r)
    {
        int res = 0;
        if (pos[l] == pos[r]) { // Same block
            for (int i = l; i <= r; i++)
                if (plast[i] < l)
                    res += 1;
        } else if (pos[l] != pos[r]) { // Different block
            for (int i = l; i <= pos[l] * blk; i++)
                if (plast[i] < l)
                    res += 1;
            for (int i = (pos[r] - 1) * blk + 1; i <= r; i++)
                if (plast[i] < l)
                    res += 1;
        }
        for (int i = pos[l] + 1; i < pos[r]; i++)
            res += find(i, l);
        return res;
    }
    void change(int x, int v)
    {
        for (int i = 1; i <= n; i++)
            last[c[i]] = 0;
        c[x] = v;
        for (int i = 1; i <= n; i++) {
            int tmp = plast[i];
            plast[i] = last[c[i]];
            if (tmp != plast[i])
                reset_blk(pos[i]);
            last[c[i]] = i;
        }
        return ;
    }
    void init(void)
    {
        blk = sqrt(n) + log(2*n) / log(2);
        m = ceil(n / blk);
        // Initializing all blocks
        for (int i = 1; i <= n; i++) {
            plast[i] = last[c[i]];
            last[c[i]] = i;
            pos[i] = (i - 1) / blk + 1;
        }
        for (int i = 1; i <= m; i++)
            reset_blk(i);
        return ;
    }
} dpf;

int n, Q;
char str[64];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &Q);
    dpf.n = n;
    for (int i = 1; i <= n; i++)
        scanf("%d", &dpf.c[i]);
    dpf.init();
    // Querying
    for (int idx = 1; idx <= Q; idx++) {
        int a, b;
        scanf("%s%d%d", str, &a, &b);
        if (str[0] == 'Q') {
            int res = dpf.query(a, b);
            printf("%d\n", res);
        } else if (str[0] == 'R') {
            dpf.change(a, b);
        }
    }
    return 0;
}