洛谷 P1972 [SDOI2009]HH的項鍊

洛谷 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;
}