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