洛谷 P1972 [SDOI2009]HH的項鍊 主席樹+區間不同數字個數
😊 | Powered By HeartFireY |
Problem Analysis
題目大意:給定 n n n個數的序列,以及随後的 m m m組詢問。回答對于每組詢問給出的 l , r l,r l,r,區間 [ l , r ] [l,r] [l,r]内不同數字的個數。
首先問題的形式與主席樹是十分相似的:先給定序列,然後給定多組區間查詢。但是顯然不是單純的維護區間第 k k k大的問題。
那麼考慮如何将問題轉化為主席樹可維護的問題:我們對每個點維護一個數組元素 n x t [ i ] nxt[i] nxt[i],表示最近的下一個同色點的下标。那麼現在不難發現對于給定區間 [ l , r ] [l,r] [l,r],如果 n x t [ i ] > r , i ∈ [ l , r ] nxt[i] > r,\ i \in [l,r] nxt[i]>r, i∈[l,r],那麼表示與 i i i相同顔色點位于區間之外。那麼求不同顔色問題便轉化為給定求所有滿足 l < = i < = r , n x t [ i ] > r l<=i<=r,\ nxt[i]>r l<=i<=r, nxt[i]>r的個數。
那麼我們隻需要處理出 n x t nxt nxt數組,然後用主席樹對每個節點維護權值數組,然後區間查詢數目即可。
Accepted Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], head[N], nxt[N];
int root[N], sum[N << 5], lc[N << 5], rc[N << 5], cnt;
inline int read(){
int f = 1, x = 0; char s = getchar();
while(s < '0'||s > '9'){ if(s =='-') f = -1; s = getchar(); }
while(s >= '0' && s <= '9'){ x = x * 10 + s - '0'; s = getchar();}
return x *= f;
}
void build(int &rt, int l, int r){
rt = ++cnt;
if(l == r) return;
int mid = l + r >> 1;
build(lc[rt], l, mid);
build(rc[rt], mid + 1, r);
}
void update(int &rt, int pre, int l, int r, int x){
rt = ++cnt, lc[rt] = lc[pre], rc[rt] = rc[pre], sum[rt] = sum[pre] + 1;
if(l == r) return;
int mid = l + r >> 1;
if(x <= mid) update(lc[rt], lc[pre], l, mid, x);
else update(rc[rt], rc[pre], mid + 1, r, x);
}
int query(int L, int R, int l, int r, int k){
if(l == r) return sum[R] - sum[L];
int mid = l + r >> 1, ans = 0;
if(k <= mid) ans += query(lc[L], lc[R], l, mid, k) + sum[rc[R]] - sum[rc[L]];
else ans += query(rc[L], rc[R], mid + 1, r, k);
return ans;
}
signed main(){
//ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n = 0; //cin >> n;
n = read();
for(int i = 1; i <= n; i++){
a[i] = read(); //cin >> a[i];
if(head[a[i]]) nxt[head[a[i]]] = i;
head[a[i]] = i;
}
for(int i = 1; i <= n; i++)
if(!nxt[i]) nxt[i] = n + 1;
build(root[0], 1, n + 1);
for(int i = 1; i <= n; i++) update(root[i], root[i - 1], 1, n + 1, nxt[i]);
int m = read();
while(m--){
int l = read(), r = read(); //cin >> l >> r;
//cout << query(root[l - 1], root[r], 1, n + 1, r + 1) << endl;
printf("%d\n", query(root[l - 1], root[r], 1, n + 1, r + 1));
}
return 0;
}