CC

自然万物都趋向从有序变得无序

0%

bzoj - 2120 数颜色(带修改的莫队)

发表于 更新于 分类于 Valine：

题目链接

Time limit 6000 ms Memory limit 265216 kB

Problem 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。

题意:

中文题目！！！

思路:

裸的带修改的莫队。

莫队是一种用来暴力解决区间查询的算法，理论上算法的时间复杂度是O(n\sqrt(n))。

对于使用莫队的要求是我们当前查询的区间[L, R] 必须能够O(1)的转移到与之相邻的四个区间。那么这种查询问题就可以用莫队来做，具体来说就是维护一个当前查询到的区间，然后对于下一次查询我们直接暴力转移到对应的区间即可，

关于算法的时间复杂度，还不会证明

那么对于带修改的莫队其实也是一样的，对于当前次查询，我们维护当前已经修改到第几个修改，然后看当前查询的编号之前有几个修改，如果多了，就把多掉的修改还原，如果少了就继续修改。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
/*************************************************************************
    > File Name: bzoj-2120.cpp
    > Author: wood
    > Mail: cbcruel@gmail.com
    > Created Time: 2018年08月04日 星期六 09时06分44秒
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<string>

using namespace std;
typedef long long LL;
#define sqr(x) (x)*(x)
const double eps = 1e-8;
const double C = 0.57721566490153286060651209;
const double pi = acos(-1.0);
const LL mod = 1e9 + 7;
const int maxn = 1e4 + 10;

template <class T>
inline bool scan_d(T &ret) {
    char c; int sgn;
    if(c = getchar(),c == EOF) return 0; //EOF
    while(c != '-' && (c < '0' || c > '9')) c = getchar();
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c-'0');
    while(c = getchar(),c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    ret *= sgn;
    return 1;
}
inline void out(int x) {
    if(x > 9) out( x / 10);
    putchar( x % 10 + '0');
}

struct ask{
    int l, r, id, tim, bl, rl;
    ask(int l=0, int r=0, int id=0, int tim=0, int bl=0, int rl = 0)
    :l(l), r(r),id(id), tim(tim),bl(bl), rl(rl){};
    bool operator < (const ask &rhq)const{
        if(bl != rhq.bl) return bl < rhq.bl;
        if(rl != rhq.rl) return rl < rhq.rl;
        return tim < rhq.tim;
    }
}que[maxn];

struct modify{
    int x, y, pre;
    modify(int x=0, int y=0, int pre = 0)
    :x(x), y(y), pre(pre){};
}mo[maxn];

int a[maxn], last[maxn];
int num[maxn*100];

int tmp;
int ans[maxn];

void del(int x){
    num[a[x]]--;
    if(num[a[x]] == 0) tmp--;
}

void add(int x){
    num[a[x]]++;
    if(num[a[x]] == 1) tmp++;
}

void upd(int x, int y, int l, int r){
    if(l <= x && x <= r){
        del(x);
        a[x] = y;
        add(x);
    }else a[x] = y;
}

int main(){
    int n, m;
    scan_d(n);
    tmp = 0;
    scan_d(m);
    for(int i = 1; i <= n; ++i)
        scan_d(a[i]), last[i] = a[i];
    int cnt1 = 0, cnt2 = 0;
    int sz = sqrt(n);
    while(m--){
        char op;
        int x,y;
        scanf(" %c", &op);
        scan_d(x);
        scan_d(y);
        if(op == 'Q'){++cnt1;
            que[cnt1] = ask(x,y,cnt1,cnt2,(x-1)/sz+1, (y-1)/sz+1);
        }else mo[++cnt2] = modify(x, y, last[x]), last[x] = y;
    }sort(que+1,que+1+cnt1);
    int l = 1, r= 0,ti = 0;
    for(int i = 1; i <= cnt1; ++i){
        while(l < que[i].l) del(l),l++;
        while(l > que[i].l) l--, add(l);
        while(r > que[i].r) del(r), r--;
        while(r < que[i].r) r++,add(r);
        while(ti < que[i].tim) ti++, upd(mo[ti].x, mo[ti].y,l ,r);
        while(ti > que[i].tim) upd(mo[ti].x, mo[ti].pre, l,r), ti--; 
        ans[que[i].id] = tmp;
    }
    for(int i = 1; i <= cnt1; ++i)
        out(ans[i]),puts("");
    return 0;
}