首页 > > 程序设计 > C/C++ >

bzoj2120&&2453 -- 带修改莫队

2018-06-17 22:45:26来源：未知阅读 ()

待修改莫队裸题。。。

当莫队有修改操作时，只要记录每个询问的时间，在两次询问之间修改就可以了。

可以证明时间复杂度是O(n^(5/3))的

具体看代码。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 #define N 10010
 8 #define M 1000010
 9 struct Q{
10     int l,r,f,F;
11 }a[N];
12 struct U{
13     int x,p,c;
14 }w[N];
15 int x,y,i,j,k,n,m,p,l,r,Res,Cnt,b[N],S,c[M],A[N],Ans[N],L[M];
16 char s[2];
17 bool B[N];
18 inline bool Cmp(Q x,Q y){
19     if(b[x.l]==b[y.l])return x.r<y.r;
20     return b[x.l]<b[y.l];
21 }
22 inline void Update1(int x){
23     B[x]=1;
24     if(++c[A[x]]==1)Res++;
25 }
26 inline void Update2(int x){
27     B[x]=0;
28     if(--c[A[x]]==0)Res--;
29 }
30 inline void Update(int x,int y){
31     if(B[x]){
32         Update2(x);
33         A[x]=y;
34         Update1(x);
35     }else A[x]=y;
36 }
37 int main(){
38     scanf("%d%d",&n,&m);S=sqrt((double)n);
39     for(i=1;i<=n;i++)scanf("%d",&A[i]),L[i]=A[i],b[i]=(i-1)/S+1;
40     for(i=1;i<=m;i++){
41         scanf("%s",s);
42         if(s[0]=='Q')a[++Cnt].f=i,a[Cnt].F=Cnt,scanf("%d%d",&a[Cnt].l,&a[Cnt].r);else scanf("%d%d",&w[i].x,&w[i].c),w[i].p=L[w[i].x],L[w[i].x]=w[i].c;
43     }
44     sort(a+1,a+Cnt+1,Cmp);
45     for(i=l=1,r=0;i<=Cnt;i++){
46         for(j=a[i-1].f+1;j<a[i].f;j++)Update(w[j].x,w[j].c);
47         for(j=a[i-1].f-1;j>a[i].f;j--)Update(w[j].x,w[j].p);
48         while(a[i].r>r)Update1(++r);
49         while(a[i].l<l)Update1(--l);
50         while(a[i].r<r)Update2(r--);
51         while(a[i].l>l)Update2(l++);
52         Ans[a[i].F]=Res;
53     }
54     for(i=1;i<=Cnt;i++)printf("%d\n",Ans[i]);
55     return 0;
56 }