2120: 数颜色
Time Limit: 6 Sec Memory Limit: 259 MB
Submit: 7340 Solved: 2982
[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
题解：这道题，普通莫队也可以做，因为修改不多于1000次
直接10000000+n√n也可以做，这里还是用了带修改的莫队，
复杂度是O(n^(5/3))
这道题目貌似
排序方式，先按第一维块排，然后第二维位置，都一样才第三维时间。这样虽然是错的，但是速度快
因为m的大小是1000，这样√n个块，每次移动不会超过n，每个数之间就算修改为1000次，
那么复杂度是（√n+1000）×n 复杂度不高。
而第二种虽然是正解，因为受到修改次数影响，所以不如上一种优秀。
第一种 904ms
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring> #define N 10007
#define M 1000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,m,num,xgnum,ans,blo;
int ys[N],bl[N],col[M],res[N];
struct Node
{
int x,y,id,xg;
}a[N];
struct Node1
{
int ps,val;
}b[N]; bool operator<(Node x,Node y)
{
if (bl[x.x]!=bl[y.x]) return bl[x.x]<bl[y.x];
if (x.y!=y.y) return x.y<y.y;
return x.xg<y.xg;
}
void del(int x){if(--col[x]==)ans--;}
void ins(int x){if(++col[x]==)ans++;}
void work(int wei,int i)
{
if(b[wei].ps>=a[i].x&&b[wei].ps<=a[i].y)
{
if(--col[ys[b[wei].ps]]==)ans--;
if(++col[b[wei].val]==)ans++;
}
swap(b[wei].val,ys[b[wei].ps]);
//十分巧妙
//对于操作3-7,下一次7-3
//所以直接交换两种颜色即可
}
void solve_modui()
{
int l=,r=,now=;
for (int i=;i<=num;i++)
{
while(l<a[i].x)del(ys[l++]);
while(l>a[i].x)ins(ys[--l]);
while(r<a[i].y)ins(ys[++r]);
while(r>a[i].y)del(ys[r--]);
while(now<a[i].xg)work(++now,i);
while(now>a[i].xg)work(now--,i);
res[a[i].id]=ans;
}
}
int main()
{
n=read(),m=read(),blo=sqrt(n);
for (int i=;i<=n;i++)
ys[i]=read(),bl[i]=(i-)/blo+;
while(m--)
{
char ch[];
scanf("%s",ch);
if(ch[]=='Q')
{
a[++num].x=read(),a[num].y=read();
a[num].id=num,a[num].xg=xgnum;
}
else b[++xgnum].ps=read(),b[xgnum].val=read();
}
sort(a+,a+num+);
solve_modui();
for (int i=;i<=num;i++)
printf("%d\n",res[i]);
}
1376ms
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring> #define N 10007
#define M 1000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,m,num,xgnum,ans,blo;
int ys[N],bl[N],col[M],res[N];
struct Node
{
int x,y,id,xg;
}a[N];
struct Node1
{
int ps,val;
}b[N]; bool operator<(Node x,Node y)
{
if (bl[x.x]!=bl[y.x]) return bl[x.x]<bl[y.x];
if (bl[x.y]!=bl[y.y]) return bl[x.y]<bl[y.y];
return x.xg<y.xg;
}
void del(int x){if(--col[x]==)ans--;}
void ins(int x){if(++col[x]==)ans++;}
void work(int wei,int i)
{
if(b[wei].ps>=a[i].x&&b[wei].ps<=a[i].y)
{
if(--col[ys[b[wei].ps]]==)ans--;
if(++col[b[wei].val]==)ans++;
}
swap(b[wei].val,ys[b[wei].ps]);
//十分巧妙
//对于操作3-7,下一次7-3
//所以直接交换两种颜色即可
}
void solve_modui()
{
int l=,r=,now=;
for (int i=;i<=num;i++)
{
while(l<a[i].x)del(ys[l++]);
while(l>a[i].x)ins(ys[--l]);
while(r<a[i].y)ins(ys[++r]);
while(r>a[i].y)del(ys[r--]);
while(now<a[i].xg)work(++now,i);
while(now>a[i].xg)work(now--,i);
res[a[i].id]=ans;
}
}
int main()
{
n=read(),m=read(),blo=pow(n,/);
for (int i=;i<=n;i++)
ys[i]=read(),bl[i]=(i-)/blo+;
while(m--)
{
char ch[];
scanf("%s",ch);
if(ch[]=='Q')
{
a[++num].x=read(),a[num].y=read();
a[num].id=num,a[num].xg=xgnum;
}
else b[++xgnum].ps=read(),b[xgnum].val=read();
}
sort(a+,a+num+);
solve_modui();
for (int i=;i<=num;i++)
printf("%d\n",res[i]);
}