描述

有n個位置(n ≤ 50000), 每個位置有一個顏色(顏色數 ≤ 200000).

詢問[L, R]區間的顏色種數.

分析

• 兩種解法都做了一下

• 1. 離線樹狀數組統計
• HZWER:
• 將所有詢問按照左端點進行排序,?將所有顏色的第一個點x, 將a[x]++,?然后從左往右掃,?掃到一個點x, 將a[next[x]]++,?碰到一個詢問l,r輸出sum[r]-sum[l-1],?其中sum是a數組的前綴和,?求前綴和可以用樹狀數組.
• 之所以這樣做關鍵就是避免同種顏色計算多次, 這也是用樹狀數組解決問題的關鍵. 在L前的一個位置x, 如果next[x]在L之前, 用樹狀數組統計query(R)-query(L-1)時被減掉沒有計算進去, 但之后一定會在結束對[L, R]的統計之前遇到這個next[x]; 如果next[x]在[L, R]的區間中, 那么更新next[x]之后query(R)-query(L-1)比原來大1, 也就是這個顏色被統計進去了, 而因為next[x]>L, 所以不會再遇到這個next[x]; 如果next[x]>R, 那么不會影響結果.
• 好巧妙的方式
• O(nlogn)

• 2. 莫隊算法
• 分塊的做法:
• 將詢問分 √n 塊, 每一塊內按R從小到大排序, 不同塊之間按L從小到大排序. 然后用兩個指針{p, q}掃描, 統計[p, q]區間內每個顏色的出現次數, 同時根據當前的答案統計對[L, R]區間的顏色種數造成的影響, 直到p==L&&q==R, 當前的答案就是[L, R]區間的答案.
• 感性的理解是這樣分塊讓指針p, q在統計某一詢問移動的次數盡可能少. 至于為什么我覺得沒必要證啦...
• O(n√n)

#include #include #include #include using namespace std;const int maxn = 50000 + 10; const int maxm = 200000 + 10;mapIDcache; int cnt, cur, blocks; int L, R; int ans[maxm]; int A[maxn], c[maxn]; struct Question { int L, R, id; bool operator < (const Question& rhs) const { if(L/blocks == rhs.L/blocks) return R < rhs.R; return L < rhs.L; } } questions[maxm]; #define q questions[i] int id(int x) { if(IDcache.count(x)) return IDcache[x]; return IDcache[x] = ++cnt; } int main() { int n, m; scanf("%d", &n); for(int i = 1; i <= n; i++) { int x; scanf("%d", &x); A[i] = id(x); } scanf("%d", &m); for(int i = 0; i < m; i++) scanf("%d %d", &q.L, &q.R), q.id = i; blocks = (int)(sqrt(n) + 0.5); sort(questions, questions + m); for(int i = 0; i < m; i++) { while(L > q.L) if(++c[A[--L]] == 1) ++cur; while(R < q.R) if(++c[A[++R]] == 1) ++cur; while(L < q.L) if(--c[A[L++]] == 0) --cur; while(R > q.R) if(--c[A[R--]] == 0) --cur; ans[q.id] = cur; } for(int i = 0; i < m; i++) printf("%d\n", ans[i]); return 0; } #include #include #include using namespace std; const int maxn = 50000 + 10; const int maxm = 200000 + 10; mapIDcache; int ID_cnt; int A[maxn]; int ans[maxm]; int first[maxn], next[maxn]; struct Question { int L, R, id; void init(int i) { id = i; scanf("%d %d", &L, &R); } bool operator < (const Question& rhs) const { if(L == rhs.L) return R < rhs.R; return L < rhs.L; } } questions[maxm]; struct BIT { int n; int c[maxn]; int lowbit(int x) { return x & (-x); } void modify(int x, int d) { for(; x <= n; x += lowbit(x)) c[x] += d; } int query(int x) { int ret = 0; for(; x > 0; x -= lowbit(x)) ret += c[x]; return ret; } } bit; int id(int x) { if(IDcache.count(x)) return IDcache[x]; return IDcache[x] = ++ID_cnt; } #define a A[i] #define q questions[i] int main() { int n, m; scanf("%d", &n); bit.n = n; for(int i = 1; i <= n; i++) { int x; scanf("%d", &x); A[i] = id(x); } for(int i = n; i >= 1; i--) { next[i] = first[a]; first[a] = i; } for(int i = 1; i <= ID_cnt; i++) if(first[i]) bit.modify(first[i], 1); scanf("%d", &m); for(int i = 0; i < m; i++) q.init(i); sort(questions, questions + m); int cur = 1; for(int i = 0; i < m; i++) { for(; cur < q.L; cur++) if(next[cur]) bit.modify(next[cur], 1); ans[q.id] = bit.query(q.R) - bit.query(q.L-1); } for(int i = 0; i < m; i++) printf("%d\n", ans[i]); return 0; }

總結

以上是生活随笔為你收集整理的BZOJ-1878-HH的项链-SDOI2009的全部內容，希望文章能夠幫你解決所遇到的問題。

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