bzoj2120: 数颜色 &&bzoj2453: 维护队列

题目大意：

　　　　你小时候玩过弹珠吗？ 　　　　小朋友A有一些弹珠，A喜欢把它们排成队列，从左到右编号为1到N。为了整个队列鲜艳美观，小朋友想知道某一段连续弹珠中，不同颜色的弹珠有多少。当然，A有时候会依据个人喜好，替换队列中某个弹珠的颜色。             但是A还没有学过编程，且觉得头脑风暴太浪费脑力了，所以向你来寻求帮助。 题解：莫队或者分块 代码： 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<cmath> 6 #define maxn 1000500 7 using namespace std; 8 int n,m,blo,num,q; 9 int pre[maxn],c[maxn],b[maxn],last[maxn],pos[maxn]; 10 int read() 11 { 12 int x=0; char ch; bool bo=0; 13 while (ch=getchar(),ch<'0'||ch>'9') if (ch=='-') bo=1; 14 while (x=x*10+ch-'0',ch=getchar(),ch>='0'&&ch<='9'); 15 if (bo) return -x; return x; 16 } 17 void resort(int x) 18 { 19 int l=(x-1)*blo+1,r=min(x*blo,n); 20 for (int i=l; i<=r; i++) pre[i]=b[i]; 21 sort(pre+l,pre+r+1); 22 } 23 int find(int x,int val) 24 { 25 int l=blo*(x-1)+1,r=min(blo*x,n); int first=l; 26 while (l<=r) 27 { 28 int mid=(l+r)>>1; 29 if (pre[mid]<val) l=mid+1; 30 else r=mid-1; 31 } 32 return l-first; 33 } 34 int ask(int l,int r) 35 { 36 int sum=0; 37 if (pos[l]==pos[r]) 38 { 39 for (int i=l; i<=r; i++) if (b[i]<l) sum++; 40 } 41 else 42 { 43 for (int i=l; i<=pos[l]*blo; i++) if (b[i]<l) sum++; 44 for (int i=r; i>=(pos[r]-1)*blo+1; i--) if (b[i]<l) sum++; 45 } 46 for (int i=pos[l]+1; i<pos[r]; i++) sum+=find(i,l); 47 return sum; 48 } 49 void change(int x,int y) 50 { 51 for (int i=1; i<=n; i++) last[c[i]]=0; 52 c[x]=y; 53 for (int i=1; i<=n; i++) 54 { 55 int t=b[i]; 56 b[i]=last[c[i]]; 57 last[c[i]]=i; 58 if (t!=b[i]) resort(pos[i]); 59 } 60 } 61 void init() 62 { 63 n=read(); q=read(); 64 blo=((int)sqrt(n)); 65 for (int i=1; i<=n; i++) c[i]=read(),pos[i]=(i-1)/blo+1; 66 for (int i=1; i<=n; i++) 67 { 68 b[i]=last[c[i]]; 69 last[c[i]]=i; 70 } 71 num=(n-1)/blo+1; 72 for (int i=1; i<=num; i++) resort(i); 73 } 74 void solve() 75 { 76 char ch[5]; int x,y; 77 for (int i=1; i<=q; i++) 78 { 79 scanf(" %s",ch+1); x=read(); y=read(); 80 if (ch[1]=='Q') printf("%d\n",ask(x,y)); 81 else change(x,y); 82 } 83 } 84 int main() 85 { 86 init(); 87 solve(); 88 } View Code