【原題】 2120: 數顏色 Time Limit: 6 Sec Memory Limit: 259 MB Submit: 1201 Solved: 429 [Submit][Status] 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。 【分析】以前用莫隊算法做一直超時。今天意外聽說可以用很神的暴力A過去，於是打算去試試。 【基礎暴力代碼】 [cpp] #include<cstdio> #include<cstring> using namespace std; bool f[1000005]; int a[10005],l,r,n,m,i,j,ans; char c; int main() { scanf("%d%d",&n,&m); for (i=1;i<=n;i++) scanf("%d",&a[i]); for (i=1;i<=m;i++) { c=' ';while (c!='Q'&&c!='R') c=getchar(); scanf("%d%d",&l,&r); if (c=='R') {a[l]=r;continue;} ans=0;memset(f,0,sizeof(f)); for (j=l;j<=r;j++) if (!f[a[j]]) ans++,f[a[j]]=true; printf("%d\n",ans); } return 0; } 我們會發現，f數組的MEMSET太耗時間了。怎麼辦呢？用凌神的標號法！做到某個i操作時，從l到r掃描，若f[a[j]]還不是i就把他賦成i，並把ans加一。 可是這樣還是超時啊。事實證明，當數組開得很大時，尋址需要很多時間。 我們可以把顏色離散一下，使每次判重的數組f的元素只有11000（注意會改1000次），這樣2s妥妥地A了。 【代碼】 [cpp] #include<cstdio> using namespace std; int f[11005],l,r,n,m,i,j,ans,p,d[10005]; int a[1000005]; char c; int main() { scanf("%d%d",&n,&m); for (i=1;i<=n;i++) { int o; scanf("%d",&o); if (!a[o]) a[o]=++p; d[i]=a[o]; } for (i=1;i<=m;i++) { c=' ';while (c!='Q'&&c!='R') c=getchar(); scanf("%d%d",&l,&r); if (c=='R') {if(!a[r])a[r]=++p;d[l]=a[r];continue;} ans=0; for (j=l;j<=r;j++) if (f[d[j]]!=i) ans++,f[d[j]]=i; printf("%d\n",ans); } return 0; }
