[BZOJ2120]数颜色
试题描述
墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？
输入
第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。
输出
对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。
输入示例
6 5 1 2 3 4 5 5 Q 1 4 Q 2 6 R 1 2 Q 1 4 Q 2 6
输出示例
4 4 3 4
数据规模及约定
对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
题解
对于每一个位置 i 我们维护 pre[i] 表示上一个最近的同色的位置。然后用主席树维护 pre[i]；需要支持修改，所以得用树状数组套主席树。
对于修改相当于链表的插入和删除，我们对于每一种颜色用一个 set 维护位置集合，修改时需要查前驱后继。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <set>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 10010
#define maxcol 1000010
#define maxnode 7840010
int ToT, sumv[maxnode], lc[maxnode], rc[maxnode];
void update(int& y, int x, int l, int r, int p, int v) {
sumv[y = ++ToT] = sumv[x] + v;
if(l == r) return ;
int mid = l + r >> 1; lc[y] = lc[x]; rc[y] = rc[x];
if(p <= mid) update(lc[y], lc[x], l, mid, p, v);
else update(rc[y], rc[x], mid + 1, r, p, v);
return ;
}
int query(int o, int l, int r, int qr) {
if(r <= qr) return sumv[o];
int mid = l + r >> 1, ans = query(lc[o], l, mid, qr);
if(qr > mid) ans += query(rc[o], mid + 1, r, qr);
return ans;
}
int rt[maxn], Rt[maxn];
int n, A[maxn], pre[maxn], lst[maxcol];
void change(int p, int val) {
for(int x = p; x <= n; x += x & -x)
update(Rt[x], Rt[x], 0, n, pre[p], -1),
update(Rt[x], Rt[x], 0, n, val, 1);
pre[p] = val;
return ;
}
int Art[maxn], cntA, Drt[maxn], cntD;
void getrt(int A[], int& cnt, int x) {
cnt = 0;
for(; x; x -= x & -x) A[++cnt] = Rt[x];
return ;
}
int ask(int ql, int qr) {
getrt(Art, cntA, qr); Art[++cntA] = rt[qr];
getrt(Drt, cntD, ql - 1); Drt[++cntD] = rt[ql-1];
int sum = 0;
for(int i = 1; i <= cntA; i++) sum += query(Art[i], 0, n, ql - 1);
for(int i = 1; i <= cntD; i++) sum -= query(Drt[i], 0, n, ql - 1);
return sum;
}
set <int> colpos[maxcol];
int main() {
n = read(); int q = read();
for(int i = 0; i < maxcol; i++) colpos[i].insert(0);
for(int i = 1; i <= n; i++) {
A[i] = read();
pre[i] = lst[A[i]];
lst[A[i]] = i;
colpos[A[i]].insert(i);
}
for(int i = 1; i <= n; i++) update(rt[i], rt[i-1], 0, n, pre[i], 1);
char cmd[5];
while(q--) {
scanf("%s", cmd);
if(cmd[0] == 'Q') {
int l = read(), r = read();
printf("%d
", ask(l, r));
}
if(cmd[0] == 'R') {
int p = read(), col = read();
if(A[p] == col) continue;
// it -> next ttit -> now tit -> pre
set <int> :: iterator it = colpos[A[p]].lower_bound(p), tit = it, ttit;
it++; tit--;
if(it != colpos[A[p]].end()) change(*it, *tit);
colpos[A[p]].erase(p);
colpos[col].insert(p);
it = colpos[col].lower_bound(p); ttit = tit = it;
it++; tit--;
if(it != colpos[col].end()) change(*it, *ttit);
change(*ttit, *tit);
A[p] = col;
}
}
return 0;
}