[国家集训队]数颜色 题解
题目地址:洛谷:【P1903】[国家集训队]数颜色 – 洛谷、BZOJ:Problem 2120. — 数颜色
题目描述
墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会向你发布如下指令:
- Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。
- R P Col 把第P支画笔替换为颜色Col。
为了满足墨墨的要求,你知道你需要干什么了吗?
题意简述
给一个颜色数组,每个位置有一个颜色,两种操作:
- 改变某位置颜色
- 查询区间颜色数
输入输出格式
输入格式:
第1行两个整数N,M,分别代表初始画笔的数量以及墨墨会做的事情的个数。
第2行N个整数,分别代表初始画笔排中第i支画笔的颜色。
第3行到第2+M行,每行分别代表墨墨会做的一件事情,格式见题干部分。
输出格式:
对于每一个Query的询问,你需要在对应的行中给出一个数字,代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。
输入输出样例
输入样例#1:
6 5 1 2 3 4 5 5 Q 1 4 Q 2 6 R 1 2 Q 1 4 Q 2 6
输出样例#1:
4 4 3 4
说明
对于100%的数据,N≤50000,M≤50000,所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
本题可能轻微卡常数
题解
我们可以求出每个位置的pre值,表示该位置颜色在该位置之前的最后一次出现位置。如果该位置之前没有出现过这种颜色了,则规定pre值为0。这个问题就可以转化成一个区间内查询pre值小于区间左端点数量的问题,显然可以用树状数组套主席树这样的形式来维护。
至于修改,我们可以用set维护每个颜色的出现位置,这样就可以利用lower_bound找前驱后继,从而维护线段树中的信息。
总复杂度O(n \log^2 n),不过这种写法跑的特别慢,还好卡进去了。
代码
// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <set>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(!isdigit(c)) {
if(c == '-') neg = -1;
c = fgc();
}
while(isdigit(c)) {
res = (res << 1) + (res << 3) + c - '0';
c = fgc();
}
return res * neg;
}
inline bool isop(char c) {
return c == 'Q' || c == 'R';
}
inline char readop() {
char c;
while(!isop(c = fgc())) {}
return c;
}
const int MAXN = 50005;
struct Node {
int lch, rch, val;
} tr[MAXN * 200];
int rt[MAXN], tot;
int sta[MAXN], stop;
inline int newnode() {
if(!stop) return ++tot;
int p = sta[--stop];
memset(tr + p, 0, sizeof(Node));
return p;
}
inline void delnode(int p) {
if(!p) return;
sta[stop++] = p;
}
inline void insert(int &o, int l, int r, int x) {
int p = newnode(); tr[p] = tr[o]; delnode(o); o = p;
tr[o].val++;
if(l == r) return;
int mid = (l + r) >> 1;
if(x <= mid) insert(tr[o].lch, l, mid, x);
else insert(tr[o].rch, mid + 1, r, x);
}
inline void erase(int &o, int l, int r, int x) {
int p = newnode(); tr[p] = tr[o]; delnode(o); o = p;
tr[o].val--;
if(l == r) return;
int mid = (l + r) >> 1;
if(x <= mid) erase(tr[o].lch, l, mid, x);
else erase(tr[o].rch, mid + 1, r, x);
}
inline int query(int o, int l, int r, int x) {
if(l == r) return 0;
int mid = (l + r) >> 1;
if(x <= mid) return query(tr[o].lch, l, mid, x);
else return tr[tr[o].lch].val + query(tr[o].rch, mid + 1, r, x);
}
int n, m;
inline int lowbit(int x) {
return x & -x;
}
inline void insert(int x, int v) {
for(int i = x; i <= n; i += lowbit(i)) {
insert(rt[i], 0, 1000000, v);
}
}
inline void erase(int x, int v) {
for(int i = x; i <= n; i += lowbit(i)) {
erase(rt[i], 0, 1000000, v);
}
}
inline int query(int x, int v) {
int res = 0;
for(int i = x; i; i -= lowbit(i)) {
res += query(rt[i], 0, 1000000, v);
}
return res;
}
std::set<int> col[1000005];
int col2[MAXN];
char op; int x, y;
int main() {
n = readint(); m = readint();
for(int i = 1; i <= 1000000; i++) {
col[i].insert(0);
}
for(int i = 1; i <= n; i++) {
x = readint();
col[x].insert(i); col2[i] = x;
if(col[x].empty()) col[x].insert(0);
std::set<int>::iterator it = col[x].lower_bound(i);
insert(i, *--it);
}
while(m--) {
op = readop(); x = readint(); y = readint();
if(op == 'Q') {
printf("%d\n", query(y, x) - query(x - 1, x));
} else {
std::set<int>::iterator it = col[col2[x]].lower_bound(x),
itp = --it, itn = ++++it; --it;
erase(x, *itp);
if(itn != col[col2[x]].end()) {
erase(*itn, x); insert(*itn, *itp);
}
col[col2[x]].erase(it); col2[x] = y;
col[col2[x]].insert(x); it = col[col2[x]].lower_bound(x);
itp = --it; itn = ++++it; --it;
insert(x, *itp);
if(itn != col[col2[x]].end()) {
erase(*itn, *itp); insert(*itn, x);
}
}
}
return 0;
}