bzoj 2120 带修改莫队

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

Sample Output

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

 1 #pragma GCC optimize(2)
 2 #pragma G++ optimize(2)
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<cstdio>
 7 #include<cstring>
 8 
 9 #define N 10007
10 #define M 1000007
11 using namespace std;
12 inline int read()
13 {
14     int x=0,f=1;char ch=getchar();
15     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
16     while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
17     return x*f;
18 }
19 
20 int n,m,num,xgnum,ans,blo;
21 int ys[N],bl[N],col[M],res[N];
22 struct Node
23 {
24     int x,y,id,xg;
25 }a[N];
26 struct Node1
27 {
28     int ps,val;
29 }b[N];
30 
31 bool operator<(Node x,Node y)
32 {
33     if (bl[x.x]!=bl[y.x]) return bl[x.x]<bl[y.x];
34     if (x.y!=y.y) return x.y<y.y;
35     return x.xg<y.xg;
36 }
37 void del(int x){if(--col[x]==0)ans--;}
38 void ins(int x){if(++col[x]==1)ans++;}
39 void work(int wei,int i)
40 {
41     if(b[wei].ps>=a[i].x&&b[wei].ps<=a[i].y)
42     {
43         if(--col[ys[b[wei].ps]]==0)ans--;
44         if(++col[b[wei].val]==1)ans++;
45     }
46     swap(b[wei].val,ys[b[wei].ps]);
47     //十分巧妙
48     //对于操作3-7,下一次7-3
49     //所以直接交换两种颜色即可
50 }
51 void solve_modui()
52 {
53     int l=1,r=0,now=0;
54     for (int i=1;i<=num;i++)
55     {
56         while(l<a[i].x)del(ys[l++]);
57         while(l>a[i].x)ins(ys[--l]);
58         while(r<a[i].y)ins(ys[++r]);
59         while(r>a[i].y)del(ys[r--]);
60         while(now<a[i].xg)work(++now,i);
61         while(now>a[i].xg)work(now--,i);
62         res[a[i].id]=ans;
63     }
64 }
65 int main()
66 {
67     n=read(),m=read(),blo=sqrt(n);
68     for (int i=1;i<=n;i++)
69         ys[i]=read(),bl[i]=(i-1)/blo+1;
70     while(m--)
71     {
72         char ch[2];
73         scanf("%s",ch);
74         if(ch[0]=='Q')
75         {
76             a[++num].x=read(),a[num].y=read();
77             a[num].id=num,a[num].xg=xgnum;
78         }
79         else b[++xgnum].ps=read(),b[xgnum].val=read();
80     }
81     sort(a+1,a+num+1);
82     solve_modui();
83     for (int i=1;i<=num;i++)
84         printf("%d
",res[i]);
85 }

1376ms

 1 #pragma GCC optimize(2)
 2 #pragma G++ optimize(2)
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<cstdio>
 7 #include<cstring>
 8 
 9 #define N 10007
10 #define M 1000007
11 using namespace std;
12 inline int read()
13 {
14     int x=0,f=1;char ch=getchar();
15     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
16     while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
17     return x*f;
18 }
19 
20 int n,m,num,xgnum,ans,blo;
21 int ys[N],bl[N],col[M],res[N];
22 struct Node
23 {
24     int x,y,id,xg;
25 }a[N];
26 struct Node1
27 {
28     int ps,val;
29 }b[N];
30 
31 bool operator<(Node x,Node y)
32 {
33     if (bl[x.x]!=bl[y.x]) return bl[x.x]<bl[y.x];
34     if (bl[x.y]!=bl[y.y]) return bl[x.y]<bl[y.y];
35     return x.xg<y.xg;
36 }
37 void del(int x){if(--col[x]==0)ans--;}
38 void ins(int x){if(++col[x]==1)ans++;}
39 void work(int wei,int i)
40 {
41     if(b[wei].ps>=a[i].x&&b[wei].ps<=a[i].y)
42     {
43         if(--col[ys[b[wei].ps]]==0)ans--;
44         if(++col[b[wei].val]==1)ans++;
45     }
46     swap(b[wei].val,ys[b[wei].ps]);
47     //十分巧妙
48     //对于操作3-7,下一次7-3
49     //所以直接交换两种颜色即可
50 }
51 void solve_modui()
52 {
53     int l=1,r=0,now=0;
54     for (int i=1;i<=num;i++)
55     {
56         while(l<a[i].x)del(ys[l++]);
57         while(l>a[i].x)ins(ys[--l]);
58         while(r<a[i].y)ins(ys[++r]);
59         while(r>a[i].y)del(ys[r--]);
60         while(now<a[i].xg)work(++now,i);
61         while(now>a[i].xg)work(now--,i);
62         res[a[i].id]=ans;
63     }
64 }
65 int main()
66 {
67     n=read(),m=read(),blo=pow(n,2/3);
68     for (int i=1;i<=n;i++)
69         ys[i]=read(),bl[i]=(i-1)/blo+1;
70     while(m--)
71     {
72         char ch[2];
73         scanf("%s",ch);
74         if(ch[0]=='Q')
75         {
76             a[++num].x=read(),a[num].y=read();
77             a[num].id=num,a[num].xg=xgnum;
78         }
79         else b[++xgnum].ps=read(),b[xgnum].val=read();
80     }
81     sort(a+1,a+num+1);
82     solve_modui();
83     for (int i=1;i<=num;i++)
84         printf("%d
",res[i]);
85 }