2453: 維護隊列

Time Limit:?10 Sec??Memory Limit:?128 MB
Submit:?578??Solved:?247
[Submit][Status][Discuss]

Description

你小時候玩過彈珠嗎？ 小朋友A有一些彈珠，A喜歡把它們排成隊列，從左到右編號為1到N。為了整個隊列鮮艷美觀，小朋友想知道某一段連續彈珠中，不同顏色的彈珠有多少。當然，A有時候會依據個人喜好，替換隊列中某個彈珠的顏色。但是A還沒有學過編程，且覺得頭腦風暴太浪費腦力了，所以向你來尋求幫助。

Input

輸入文件第一行包含兩個整數N和M。 第二行N個整數，表示初始隊列中彈珠的顏色。 接下來M行，每行的形式為“Q L R”或“R x c”，“Q L R”表示A想知道從隊列第L個彈珠到第R個彈珠中，一共有多少不同顏色的彈珠，“R x c”表示A把x位置上的彈珠換成了c顏色。

Output

對于每個Q操作，輸出一行表示詢問結果。

Sample Input

2 3
1 2
Q 1 2
R 1 2
Q 1 2

Sample Output

2
1

HINT

?

對于100%的數據，有1 ≤ N ≤ 10000, 1 ≤ M ≤ 10000，小朋友A不會修改超過1000次，所有顏色均用1到10^6的整數表示。

?

Source

2011福建集訓

1 #include<bits/stdc++.h> 2 using namespace std; 3 #define MAXN 10010 4 #define MAXM 1000010 5 int n,a[MAXN],last[MAXN],pre[MAXM],block,pos[MAXN],h[MAXN]; 6 int read() 7 { 8 int s=0,fh=1;char ch=getchar(); 9 while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();} 10 while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();} 11 return s*fh; 12 } 13 void cl(int k) 14 { 15 int l=(k-1)*block+1,r=min(n,k*block),i; 16 for(i=l;i<=r;i++)a[i]=last[i]; 17 sort(a+l,a+r+1); 18 } 19 void Change(int x,int c) 20 { 21 int i,t; 22 for(i=1;i<=n;i++)pre[h[i]]=0; 23 h[x]=c; 24 for(i=1;i<=n;i++) 25 { 26 t=last[i]; 27 last[i]=pre[h[i]]; 28 if(t!=last[i])cl(pos[i]); 29 pre[h[i]]=i; 30 } 31 } 32 int Find(int k,int ll) 33 { 34 int l=(k-1)*block+1,r=min(k*block,n),mid,t=0; 35 while(l<=r) 36 { 37 mid=(l+r)/2; 38 if(a[mid]>=ll)r=mid-1; 39 else if(a[mid]<ll)t=mid,l=mid+1; 40 } 41 if(t==0)return 0; 42 else return t-((k-1)*block+1)+1; 43 } 44 int Query(int l,int r) 45 { 46 int ans=0,i; 47 if(pos[l]==pos[r]) 48 { 49 for(i=l;i<=r;i++)if(last[i]<l)ans++; 50 } 51 else 52 { 53 for(i=l;i<=pos[l]*block;i++)if(last[i]<l)ans++; 54 for(i=(pos[r]-1)*block+1;i<=r;i++)if(last[i]<l)ans++; 55 for(i=pos[l]+1;i<=pos[r]-1;i++)ans+=Find(i,l); 56 } 57 return ans; 58 } 59 int main() 60 { 61 int M,i,m,s1,s2; 62 char fh[2]; 63 n=read();M=read(); 64 block=(int)sqrt(n); 65 memset(last,0,sizeof(last)); 66 memset(pre,0,sizeof(pre)); 67 for(i=1;i<=n;i++) 68 { 69 h[i]=read(); 70 last[i]=pre[h[i]]; 71 pre[h[i]]=i; 72 pos[i]=(i-1)/block+1; 73 } 74 if(block*block==n)m=n/block; 75 else m=n/block+1; 76 for(i=1;i<=m;i++)cl(i); 77 for(i=1;i<=M;i++) 78 { 79 scanf("\n%s",fh);s1=read();s2=read(); 80 if(fh[0]=='Q') 81 { 82 printf("%d\n",Query(s1,s2)); 83 } 84 else Change(s1,s2); 85 } 86 return 0; 87 } View Code 1 #include<bits/stdc++.h> 2 using namespace std; 3 int a[10010]; 4 bitset<1000010> vis; 5 int main() 6 { 7 int n,m,i,l,r,sum,j; 8 char fh; 9 scanf("%d %d",&n,&m); 10 for(i=1;i<=n;i++)scanf("%d",&a[i]); 11 for(i=1;i<=m;i++) 12 { 13 scanf("\n%c %d %d",&fh,&l,&r); 14 if(fh=='Q') 15 { 16 vis.reset(); 17 sum=0; 18 for(j=l;j<=r;j++)if(vis[a[j]]==0){sum++;vis[a[j]]=1;} 19 printf("%d\n",sum); 20 } 21 else 22 { 23 a[l]=r; 24 } 25 } 26 return 0; 27 } View Code

?

轉載于:https://www.cnblogs.com/Var123/p/5269885.html

總結

以上是生活随笔為你收集整理的Bzoj 2453: 维护队列 Bzoj 2120: 数颜色 分块,bitset的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。