[SDOI2009] HH 的项链

标签: #树状数组 #可持久化线段树 #莫队
原题目: luogu-P1972
简要描述: 求区间内不同数的个数

显然可以使用 hdu-5919 Sequence II tags: [可持久化线段树,线段树] 的方法来做: 求区间内不同数的个数

莫队

交错区间

[26],[4,8][x1,y1],[x2,y2] [2 6],[4,8] [x_1,y_1] ,[x_2,y_2]

x1⩽x2,y1⩽y2x_1 \leqslant x_2 ,y_1 \leqslant y_2

经过我的尝试,莫队算法能的40分吧,因为常数太大

cpp
copy 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

        /**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * date: 2025-12-02 08:36:41
 * oj: luogu-1972
 * title: [SDOI2009] HH 的项链
 * description: 区间不同值的数量
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;


// 快读模板示例
inline int read() {
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

const int maxn = 2e6+5;
int n,m;
int a[maxn];
int cnt[maxn];// cnt[i] 数字i出现的次数
int cnt_diff; // 不同数字的数量
int ans[maxn]; // ans 序列

// 扩大区间到x
void add(int x) {
    int num = a[x];
    cnt[num]++;
    if( cnt[num] == 1) cnt_diff++;
}

void del(int x) {
    int num = a[x];
    cnt[num]--;
    if(cnt[num]==0) cnt_diff--;
}


// block
int pos[maxn]; // pos[i]表示 i所在的块
int block_size;

struct Quer{int l,r,idx;};
Quer qur[maxn];

bool cmp(Quer & a,Quer &b) {
    if( pos[a.l] != pos[b.l])
        return pos[a.l] < pos[b.l];
    // todo 奇偶性优化
    if(pos[a.l] & 1) return a.r > b.r;
    return a.r < b.r;
}

void init(){
    // scanf("%d",&n);
    n = read();
    block_size = sqrt(n);
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        a[i] = read();
    }
    // scanf("%d",&m);
    m = read();
    for(int i = 1;i <= m ;++i ) // i: 1->m
    {
        // scanf("%d%d",&qur[i].l,&qur[i].r);
        qur[i].l = read();
        qur[i].r = read();
        qur[i].idx = i;
    }

    // init block
    for(int i =1;i<=n;i++) {
        pos[i] = (i-1)/block_size + 1;
    }

    sort(qur+1,qur+1+m,cmp);

}

signed main (int argc, char *argv[]) {
    init();

    int L = 1,R=0; // why ? 这样初始化
    for(int i = 1;i <= m ;++i ) // i: 1->m
    {
        while(L < qur[i].l ) del(L++);
        while(R > qur[i].r ) del(R--);
        while(L > qur[i].l ) add(--L);
        while(R < qur[i].r ) add(++R);
        ans[qur[i].idx] = cnt_diff;
    }
    for(int i = 1;i <= m ;++i ) // i: 1->n
    {
        printf("%d\n",ans[i]);
    }

    return 0;
}

bit 树状数组

核心时间流动: pre[i]表示前第i个元素,前面出现的位置,pre[i]= 0 表示没有出现过

cpp
copy 
        
1
2
3
4
5
6
7

        int quer_range(int l,int r){
  int ans = 0;
  for(int i = l; i <= r; i++)
    if( pre[i] < l ) ans++;
  return ans;
}

于是发现quer_range(2,4),那么就是查询区间内pre[i] <= 2-1成立的数量

如果我把pre[i] <= 2-1的数字标记为1,其余标记为0,那么, 想要查询[2,6]区间的不同的数字,可以这样做

cpp
copy 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

        
void _true_arr[100];
// 创建 pre[i] <=l 的 01 数组
for init_true_arr(int l) {
  for(int i = 1; i <= n; i++)
    if( pre[i] <= l ) _true_arr[i] = 1;
    else _true_arr[i] = 0;
}

int quer_range(int l,int r){
  int ans = 0;
  init_true_arr(l-1);
  // 求区间内 1 的个数,也就是区间和
  for(int i = l; i <= r; i++) if( _true_arr[i] == 1 ) ans++;
  return ans;
}

问题转化成: 在对应的 true false 数组上求区间和

那么_true_arr[i-1]与_true_arr[i]的关系是怎样的呢?

如果 pre[i] <= l-1 成立,那么 pre[i] <= l 也成立,

也就是说: 如果位置i在_true_arr[l-1]上是1,那么在_true_arr[l]上也是1,这其实利用性质的是单调性

那我们就是可直接在_true_arr[l-1]上的基础上直接修改得到_true_arr[l]的值.总时间O(n), 因为: pre数组总共只有n个元素,每个元素最多导致一次修改.

那么现在只需要优化求区间和的问题, 也就是求_true_arr[l]上[l,r]区间内1的个数

cpp
copy 
        
1
2

          for(int i = l; i <= r; i++) if( _true_arr[i] == 1 ) ans++;

可以想到: 1. 树状数组 2. 线段树

这个使用树状数组更方便,因为树状数组代码简单一点:,

cpp
copy 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

        /**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * date: 2025-12-02 15:03:03
 * oj: luogu-1972
 * title: [SDOI2009] HH 的项链
 * description: 区间不同元素的数量
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
const int maxn = 2e6+5;
int n,m;
int a[maxn];
int pre[maxn];
int pre_bucket[maxn];

using ll = long long;
struct node {
    int l,r,idx;
    //按l排序
    bool operator<(const node & t) const {
        if( l == t.l) return r < t.r;
        return l < t.l;
    }
};
node q[maxn]; //查询
int ans[maxn]; //存答案
 
template<typename T,int N=maxn>
struct Bit {
    T c[N+5]; // 树状数组, 1-based
    //Bit(){}
    inline int lowbit(int x) { return x & -x;      } // lowbit
    inline int fa(int p)     { return p+lowbit(p); } // update a[p] 时, 下一个要更新的节点
    inline int left(int p)   { return p-lowbit(p); } // query a[1..p] 时, 下一个要求和的节点

    // 单点更新 a[p] += v
    void update(int p, T v){
        for( ; p <= N; p = fa(p) ) c[p] += v;
    }

    // 查询前缀和 a[1..p]
    T query(int p){ //前缀和
        T sum=0;
        for( ;p > 0 ; p = left(p)) sum+= c[p];
        return sum;
    }
};
Bit<ll> bit;

void init(){
    scanf("%d",&n);
    for(int i = 1;i <= n ;++i ) // i: 1->n
        scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i = 1;i <= m ;++i ) // i: 1->m
    {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].idx = i;
    }
    std::sort(q+1,q+1+m);
}

signed main (int argc, char *argv[]) {
    init();

    // 创建pre数组
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        int num = a[i];
        pre[i] = pre_bucket[a[i]];
        pre_bucket[a[i]] = i;
    }
    // pre 分组
    std::vector< std::vector<int> > vec(n+1);
    
    for(int i = 1;i<=n;i++) {
        //表示 pre[i] = 3
        // 前一个位置为3的放在 一组里
        vec[ pre[i] ].push_back(i);
    }

    int l_idx = 1; //遍历 query 数组使用,
    // l_idx 表明 `[l,r]` q[l_idx].l = l 时


    //枚举 pre[] 值
    for(int i = 1 ;i <=n;i++) {

        // 更新 true_arr 对应的BIT
        for( auto pos : vec[i-1]) {
            bit.update(pos, 1);
        }

        // --> 收缩对应的查询区间
        // 更新l_idx, 知道 q[l_idx].l > i
        while( q[l_idx].l <= i && l_idx <=m) {

            if( q[l_idx].l == i)
            {
                int ans_id = q[l_idx].idx;
                ans[ ans_id ] = bit.query(q[l_idx].r) - bit.query(q[l_idx].l - 1);
            }
            l_idx++;
        }
    }
    for(int i = 1;i <= m ;++i ) // i: 1->m
    {
        printf("%d\n",ans[i]);
    }
    
    return 0;
}

方法二:

来在: 这个题用树状数组，线段树等等都可以做，不过用树状数组写起来更方便。

此题首先应考虑到这样一个结论：

对于若干个询问的区间[l,r]，如果他们的r都相等的话，那么项链中出现的同一个数字，一定是只关心出现在最右边的那一个的，例如：

项链是：1 3 4 5 1

那么，对于r=5的所有的询问来说，第一个位置上的1完全没有意义，因为r已经在第五个1的右边，对于任何查询的[L,5]区间来说，如果第一个1被算了，那么他完全可以用第五个1来替代。

因此，我们可以对所有查询的区间按照r来排序，然后再来维护一个树状数组，这个树状数组是用来干什么的呢？看下面的例子：

1 2 1 3

对于第一个1，insert(1,1)；表示第一个位置出现了一个不一样的数字，此时树状数组所表示的每个位置上的数字（不是它本身的值而是它对应的每个位置上的数字）是：1 0 0 0

对于第二个2，insert(2,1)；此时树状数组表示的每个数字是1 1 0 0

对于第三个1，因为之前出现过1了，因此首先把那个1所在的位置删掉insert(1,-1),然后在把它加进来insert(3,1)。此时每个数字是0 1 1 0

如果此时有一个询问[2,3]，那么直接求sum(3)-sum(2-1)=2就是答案。

题解清楚么？

可持久化线段树

参考 hdu-5919 Sequence II tags: [可持久化线段树,线段树] 可持久化线段树的实现