任意门:https://www.lydsy.com/JudgeOnline/problem.php?id=2120
2120: 数颜色
Time Limit: 6 Sec Memory Limit: 259 MB
Submit: 10095 Solved: 4222
[Submit][Status][Discuss]
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
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
4
3
4
HINT
对于100%的数据,N≤10000,M≤10000,修改操作不多于1000次,所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
2016.3.2新加数据两组by Nano_Ape
解题思路:
单点更新,xjb查询,莫队或者分块。
但是莫队需要离线,这里需要修改,怎么办呢?
引入第三个参数记录时间,根据时间点的不同更新答案。
AC code:
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int MAXN = 1e4+;
const int MAXM = 1e6+;
int N, M;
int h[MAXN], num[MAXN];
int ans[MAXN], sum[MAXM];
struct Query
{
int l, r, id, t;
}Q[MAXN]; struct Time
{
int ip, co, lt;
}t[MAXN];
int last[MAXN]; bool cmp(Query a, Query b)
{
if(h[a.l] != h[b.l]) return h[a.l] < h[b.l];
else{
if(h[a.r] != h[b.r]) return h[a.r] < h[b.r];
else return a.t < b.t;
}
} int update(int tt, int L, int R, int no)
{
int res = ;
int x = t[tt].ip, val = t[tt].co, lst = t[tt].lt;
if(t[tt].ip >= L && t[tt].ip <= R){
if(sum[num[x]] == ) res--;
sum[num[x]]--;
if(no == ){
if(sum[val] == ) res++;
sum[val]++;
}
else if(no == -){
if(sum[lst] == ) res++;
sum[lst]++;
}
}
if(no == ) num[x] = val;
else if(no == -) num[x] = lst;
return res;
} int add(int x, int val)
{
int res = ;
if(val == && sum[num[x]] == ) res++;
if(val == - && sum[num[x]] == ) res--;
sum[num[x]]+=val;
return res;
} int main()
{
scanf("%d %d", &N, &M);
for(int i = ; i <= N; i++){
scanf("%d", &num[i]);
last[i] = num[i];
}
int lim = pow(N, (double)/);
for(int i = ; i <= N; i++) h[i] = (i-)/lim+;
int cnt = , Tcnt = ;
char com[];
for(int i = ; i <= M; i++){
scanf("%s", com);
if(com[] == 'Q'){
cnt++;
scanf("%d %d", &Q[cnt].l, &Q[cnt].r);
Q[cnt].t = Tcnt;
Q[cnt].id = cnt;
}
else{
Tcnt++;
scanf("%d %d", &t[Tcnt].ip, &t[Tcnt].co);
t[Tcnt].lt = last[t[Tcnt].ip];
last[t[Tcnt].ip] = t[Tcnt].co;
//printf("%d %d\n", t[Tcnt].co, t[Tcnt].lt);
}
}
sort(Q+, Q++cnt, cmp); int L = , R = , T = , cur = ;
for(int i = ; i <= cnt; i++){
while(T < Q[i].t) cur+=update(++T, L, R, );
while(T > Q[i].t) cur+=update(T--, L, R, -);
while(L < Q[i].l) cur+=add(L++, -);
while(L > Q[i].l) cur+=add(--L, );
while(R < Q[i].r) cur+=add(++R, );
while(R > Q[i].r) cur+=add(R--, -);
ans[Q[i].id] = cur;
} for(int i = ; i <= cnt; i++){
printf("%d\n", ans[i]);
} return ; }