題目

題目鏈接

題意

給你一個數列代表不同的顏色（可以修改）。
詢問一段區間內有多少種顏色。

題解

很容易想到的就是線段樹來維護bitset。

這里為了練習，使用分塊維護bitset。

* 事實上線段樹可以看成是無限分塊。*

修改的時候直接暴力將被修改位置所在的塊重新計算，形成新的bitset。

查詢的時候，直接按塊合并bitset即可。

注意細節：由于bitset不能開太大，因此有必要將給出的顏色進行離散化。

我采用的方法是使用unordered_map進行離散化，簡單易行。

代碼

#include <unordered_map> #include <bits/stdc++.h> using namespace std; int n,m,L,R; int a[10007]; bitset<12007> block[107]; bitset<12007> now; int Base = 100; unordered_map<int,int> mpid; inline int getid(int x){if(mpid.count(x)) return mpid[x];return mpid[x] = mpid.size()+1; } int main(){scanf("%d%d",&n,&m);for(int i = 1;i <= n;++i){if(i % Base == 0 && i != 0) {block[i/Base-1] = now;now.reset();}scanf("%d",&a[i]);now.set(getid(a[i]));}block[n/Base] = now;char op;while(m--){scanf(" %c%d%d",&op,&L,&R);if(op == 'Q'){now.reset();for(;L % Base != 0 && L <= R;++L){now.set(getid(a[L]));}for(;(R+1) % Base != 0 && R >= L;--R){now.set(getid(a[R]));}if(L >= R) {printf("%d\n",now.count());continue;}int bl = L / Base,br = R / Base;for(;bl <= br;++bl)now |= block[bl];printf("%d\n",now.count());}else {a[L] = R;int bl = L / Base;block[bl].reset();for(int i = bl*Base;i < (bl+1)*Base;++i)block[bl].set(getid(a[i]));}} }

總結

以上是生活随笔為你收集整理的洛谷-P1903 数颜色 分块 bitset的全部內容，希望文章能夠幫你解決所遇到的問題。

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