sloj.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支画笔中共有几种不同颜色的画笔。
样例
输入数据 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
数据规模与约定
所有速据n,m<=133333
所有的输入数据中出现的所有整数均大于等于1且不超过106。
如果不看第二个修改操作的话,很容易分析出这是一道莫队的题
那加上修改操作呢?用带修莫队啊!
所谓带修莫队,就是指莫队可以变到任意时间,再来进行询问
对于带修莫队莱说,他有三个维度l,r,tim
分别是询问左右端点与时间
照普通莫队来说,肯定是要排序的,
那就可以将tim视为普通莫队中的第二个维度
每次查询就挪移三个位置,每一次执行一个修改,一步步挪移过去
然后将左右端点都分块就可以了
需要注意的是,这时我们需要将块的大小开至n2/3
实现这个操作非常简单,只需pow(n,2.0/3)
必须写的是2.0/3或2.0/3.0或2/3.0
不然结果是整数类型而非浮点型
#include<bits/stdc++.h> #define ll long long using namespace std; int n,m,k,a[2000010],belong[2000010],qnum = 0,cnum = 0; int color[2000010],ans[2000010]; struct query{ int l,r,tim,id; }q[2000010]; struct node{ int pos,val; }c[2000010]; inline int read(){ char c = getchar();int x = 0,f = 1; while(c<'0'||c>'9'){ if(c=='-'){ f = -1; } c = getchar(); } while(c>='0'&&c<='9'){ x = x*10+c-'0'; c = getchar(); } return x*f; } int cmp(const query &a,const query &b){ if(belong[a.l]!=belong[b.l]) return a.l<b.l; if(belong[a.r]!=belong[b.r]) return a.r<b.r; return a.tim<b.tim; } void add(int &num,int x){ if(++color[x]==1) num++; } void del(int &num,int x){ if(--color[x]==0) num--; } void work(int &num,int now,int i){ if(c[now].pos>=q[i].l&&c[now].pos<=q[i].r){ if(--color[a[c[now].pos]]==0) num--; if(++color[c[now].val]==1) num++; } swap(c[now].val,a[c[now].pos]); } int main(){ n = read();m = read(); k = pow(n,2.0/3); for(int i = 1;i<=n;i++){ a[i] = read(); belong[i] = (i-1)/k+1; } while(m--){ char opt[5]; scanf("%s",opt); if(opt[0]=='Q'){ q[++qnum].l = read(); q[qnum].r = read(); q[qnum].tim = cnum; q[qnum].id = qnum; }else if(opt[0]=='R'){ c[++cnum].pos = read(); c[cnum].val = read(); } } sort(q+1,q+qnum+1,cmp); int l = 1,r = 0,now = 0,num = 0; for(int i = 1;i<=qnum;i++){ while(l<q[i].l) del(num,a[l++]); while(l>q[i].l) add(num,a[--l]); while(r<q[i].r) add(num,a[++r]); while(r>q[i].r) del(num,a[r--]); while(now<q[i].tim) work(num,++now,i); while(now>q[i].tim) work(num,now--,i); ans[q[i].id] = num; } for(int i = 1;i<=qnum;i++) printf("%d\n",ans[i]); return 0; }
标签:2000010,颜色,画笔,队列,莫队,P1903,int,num,国家集训队 From: https://www.cnblogs.com/cztq/p/17045461.html