Sequence II

标签: #可持久化线段树 #线段树
原题目: hdu-5919
简要描述: 求区间内不同数的个数

题目大意

给定一个长度为 n 的序列。有 m 次在线查询，每次询问区间 [l, r] 内有多少个不同的数。

1. 核心转换：如何定义“首次出现”

要在区间 [l,r][l, r] 中找到“首次出现”的数字，我们可以利用前驱位置的概念。

定义 pre[i]pre[i] 为数组中第 ii 个位置的数字 a[i]a[i] 上一次出现的位置。如果 a[i]a[i] 之前没出现过，则 pre[i]=0pre[i] = 0。

推论：

对于查询区间 [l,r][l, r]，如果位置 ii (l≤i≤rl \le i \le r) 是该数字在区间内的首次出现，那么必须满足：

pre[i]<lpre[i] < l

原因： 如果 pre[i]≥lpre[i] \ge l，说明在区间 [l,r][l, r] 内，在 ii 的左边还有一个 a[i]a[i]，那么 ii 就不是第一次出现了。

这样就变成了查找区间 [l,r][l,r] 满足条件的pre[i]<lpre[i] < l个数

∣{x∣x∈[l,r],pre[x]<l}∣ | \{ x | x \in [l,r] , pre[x] < l \} |

2. 区间问题

假设数组 A=[1,2,1,3,2]A = [1, 2, 1, 3, 2]，下标从 1 开始。

A  : [1, 2, 1, 3, 2]
Pre: [0, 0, 1, 0, 2]

我们用一个数组（桶） p_group[v] 来存储所有 pre[i]==vpre[i] == v 的下标 ii。

  • p_group[0] 包含 prepre 为 0 的下标：{1, 2, 4}
  • p_group[1] 包含 prepre 为 1 的下标：{3}
  • p_group[2] 包含 prepre 为 2 的下标：{5}
  • p_group[3], p_group[4], p_group[5] 均为空。

得到pre[i]=k的位置分别是那些

时间演进法求区间内不同数字的数量

转成区间问题

这个表格展示了如何将原问题转化为一个可以用可持久化线段树解决的模型。

表格的每一行可以看作是一个版本。

  • 第 k 行 (pre[i] <= k)：是一个 0/1 序列。如果位置 j 上的 pre[j] 值小于等于 k，那么该序列的第 j 个位置就为 1，否则为 0。

我们的目标是查询区间 [l, r] 中 pre[i] < l 的个数，这等价于查询 pre[i] <= l-1 的个数。 这完美地对应到：使用版本为 l-1 的线段树，查询区间 [l, r] 的和。

1 2 3 4 5
pre[i] <= 0 1 1 0 1 0
pre[i] <= 1 1 1 1 1 0
pre[i] <= 2 1 1 1 1 1
pre[i] <= 3 1 1 1 1 1
1 2 3 4 5
pre[i] <= 2 1 [1] 1 1 1

这个[1]表示 位置 22 它的前驱的位置 pre[i]⩽2pre[i] \leqslant 2 是成立的

如果我们想要查询区间[2,4]内不同的数字的个数

那我们就去找 pre[i] <=1 对应的数组的 [2,4] 区间和

| `pre[i] <= 1` | 1 | 1 | 1 | 1 | 0 |

时间版本的区间01串 ,0代表不成立,1代表条件成立

用到的数学原理

  • true∨false=truetrue \lor false = true
  • pre[i]⩽k=(pre[i]==k)∨(pre[i]<k)pre[i] \leqslant k = (pre[i] == k) \lor (pre[i] <k)

求区间内第k个不同的元素

A  : [1, 2, 1, 3, 2]
Pre: [0, 0, 1, 0, 2]

求区间内第k个不同的元素,比如求区间 [2,4] 第二个不同的数字是那个

cpp
copy 
        
1
2
3
4
5
6
7
8
9
10
11
12

        int cnt =  0;
for(int i = 2 ;i<=4;i++){
{
    if( pre[i] < 2) {
      cnt++;
      if( cnt == 2) {
        cout << a[i] << endl;
        break;
      }
    }
}

上面代码表达的思路: 是1的时候统计,0的时候忽略

显然相同的数字被忽略,上面代码对应对应的数学描述:

设集合 SS 为所有满足条件的位置 ii 的集合：

S={i∣l≤i≤r∧pre[i]<l} S = \{ i \mid l \le i \le r \land pre[i] < l \}
我们将集合 SS 中的元素从小到大排序，得到有序序列 p1,p2,…,p∣S∣p_1, p_2, \dots, p_{|S|}。 我们要找的就是这个序列中的第 kk 个元素 pkp_k。

如果把S看成序列,那就是S[k]S[k]

这等价于在版本为 l-1 的可持久化线段树上，查询区间 [l, r] 内第 k 个 1 所在的位置。

在 root[l-1] 中，仅限于 [l,r][l, r] 范围内，找到第 kk 个出现的位置（下标）。

完全按照你提供的逻辑梳理，这个解法的核心在于：把“不同数字”的问题转化为了“前驱位置 pre”的二维点计数问题。

我们以 pre[i] 的值作为**时间轴（版本）**来构建可持久化线段树。

核心逻辑映射

  1. 数据预处理：

    • 计算每个位置 ii 的 pre[i]pre[i]（上一次出现的位置）。
    • 将所有位置 ii 按照 pre[i]pre[i] 的值进行分组（即你的 p_group）。

  2. 构建主席树：

    • 第 kk 个版本 root[k] 代表条件：pre[i]≤kpre[i] \le k。
    • root[k] 是在 root[k-1] 的基础上，把所有 pre[i]==kpre[i] == k 的位置 ii 在线段树中置为 1。
    • 这是一棵维护区间和的线段树（值为1代表该位置满足条件，0代表不满足）。

  3. 查询处理：

    • 查询区间 [l,r][l, r] 内不同的数 →\rightarrow 寻找区间内满足 pre[i]<lpre[i] < l 的数。
    • 这对应于查找 版本 root[l-1]。
    • 数量计算：在 root[l-1] 中查询区间 [l,r][l, r] 的和，记为 kcntk_{cnt}。
    • 位置查找：我们要找第 ⌈kcnt/2⌉\lceil k_{cnt} / 2 \rceil 个数。
      • 注意：在 root[l-1] 版本中，下标 11 到 l−1l-1 的位置肯定都是 1（因为对于 i<li < l，必然有 pre[i]<i<lpre[i] < i < l）。
      • 所以，区间 [l,r][l, r] 里的第 kk 小，其实就是**整棵树（全局）**里的第 (l−1)+k(l-1) + k 小。

C++ 代码实现

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

        #include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

const int MAXN = 200005;

// 线段树节点
struct Node {
    int l, r; // 左右子节点编号
    int sum;  // 区间内满足条件的个数 (即有多少个1)
} tree[MAXN * 40]; // 预估空间 N * logN

int root[MAXN]; // 版本入口：root[k] 表示 pre[i] <= k 的状态
int tot = 0;    // 节点分配计数
int a[MAXN];    // 原数组
int pre[MAXN];  // pre[i] 表示 a[i] 上一次出现的位置
vector<int> p_group[MAXN]; // 分组桶：p_group[v] 存储所有 pre[i] == v 的下标 i

int n, m;

// 构建/更新线段树
// prev_node: 上一个版本的节点
// curr_node: 当前版本的节点（引用，会被赋值）
// l, r: 当前节点覆盖的区间
// pos: 要把哪个位置置为 1
void update(int prev_node, int &curr_node, int l, int r, int pos) {
    curr_node = ++tot;
    tree[curr_node] = tree[prev_node]; // 复制上一个版本
    tree[curr_node].sum++;             // 计数值 +1

    if (l == r) return;

    int mid = (l + r) >> 1;
    if (pos <= mid) {
        update(tree[prev_node].l, tree[curr_node].l, l, mid, pos);
    } else {
        update(tree[prev_node].r, tree[curr_node].r, mid + 1, r, pos);
    }
}

// 查询区间 [ql, qr] 的和
// 在本题中，用来计算区间内有多少个满足 pre[i] <= version 的数
int query_sum(int node, int l, int r, int ql, int qr) {
    if (node == 0) return 0; // 空节点
    if (ql <= l && r <= qr) {
        return tree[node].sum;
    }
    int mid = (l + r) >> 1;
    int res = 0;
    if (ql <= mid) res += query_sum(tree[node].l, l, mid, ql, qr);
    if (qr > mid) res += query_sum(tree[node].r, mid + 1, r, ql, qr);
    return res;
}

// 查询整棵树中第 k 个 1 所在的位置（全局第 k 小）
int query_global_kth(int node, int l, int r, int k) {
    if (l == r) return l;
    
    int mid = (l + r) >> 1;
    int left_sum = tree[tree[node].l].sum; // 左子树有多少个 1
    
    if (k <= left_sum) {
        return query_global_kth(tree[node].l, l, mid, k);
    } else {
        return query_global_kth(tree[node].r, mid + 1, r, k - left_sum);
    }
}

void solve(int case_num) {
    scanf("%d%d", &n, &m);
    
    // 初始化
    tot = 0;
    for (int i = 0; i <= n; i++) {
        p_group[i].clear();
        root[i] = 0;
    }

    // 1. 预处理 pre 数组 和 分组
    map<int, int> last_pos; // 记录数值上一次出现的位置
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if (last_pos.count(a[i])) {
            pre[i] = last_pos[a[i]];
        } else {
            pre[i] = 0;
        }
        last_pos[a[i]] = i;
        
        // 将下标 i 加入到对应的 pre 值分组中
        p_group[pre[i]].push_back(i);
    }

    // 2. 构建可持久化线段树
    // root[v] 表示 pre[i] <= v 的版本
    // 我们的 v 从 0 遍历到 n (其实遍历到 n-1 即可，因为查询最大用到 root[n-1])
    for (int v = 0; v <= n; v++) {
        // 如果不是第0个版本，先继承上一个版本
        int prev_root = (v == 0 ? 0 : root[v-1]);
        root[v] = prev_root; 

        // 将所有 pre[i] == v 的位置 i 加入到当前版本
        // 注意：这里可能一次插入多个点，所以要循环更新
        for (int idx : p_group[v]) {
            int temp_root = root[v]; // 暂存当前根，用于迭代
            update(temp_root, root[v], 1, n, idx);
        }
    }

    printf("Case #%d:", case_num);
    int last_ans = 0;
    
    for (int i = 0; i < m; i++) {
        int l_in, r_in;
        scanf("%d%d", &l_in, &r_in);
        
        // 强制在线解码
        int l = (l_in + last_ans) % n + 1;
        int r = (r_in + last_ans) % n + 1;
        if (l > r) swap(l, r);

        // 3. 查询逻辑
        // 我们需要查询 pre[i] < l 的情况，即 pre[i] <= l-1
        // 所以使用版本 root[l-1]
        int ver = root[l-1];
        
        // 第一步：算出区间 [l, r] 内有多少个不同的数
        // 即在 root[l-1] 版本中查询区间 [l, r] 的和
        int count = query_sum(ver, 1, n, l, r);
        
        // 第二步：我们要找第 ceil(count / 2) 个数
        int k = (count + 1) / 2;
        
        // 第三步：找到对应的下标
        // 技巧：在 root[l-1] 中，区间 [1, l-1] 的所有位置全是 1。
        // 因为对于任何 x < l，显然 pre[x] < x < l，所以 pre[x] <= l-1 恒成立。
        // 所以，区间 [l, r] 里的第 k 个，等价于 全局 的第 (l-1) + k 个。
        int ans_index = query_global_kth(ver, 1, n, (l - 1) + k);
        
        last_ans = ans_index;
        printf(" %d", last_ans);
    }
    printf("\n");
}

int main() {
    int t;
    if (scanf("%d", &t) == 1) {
        for (int i = 1; i <= t; i++) {
            solve(i);
        }
    }
    return 0;
}

代码与你的逻辑对照

  1. 分组逻辑 (p_group)：

    • 代码中 p_group[pre[i]].push_back(i) 完全对应你的描述：把 pre[i]=kpre[i]=k 的位置归类。
    • 构建树时，外层循环遍历 v（即 pre 的值），内层将 p_group[v] 里的所有点插入。

  2. 版本定义：

    • 代码中 root[v] 继承自 root[v-1]，并加入了 pre[i] == v 的点。
    • 这完全实现了表格中的逻辑：root[v] 包含了所有 pre <= v 的点。

  3. 查询技巧 (Range K-th)：

    • 你提到了查询区间内的第 K 个。
    • 代码中使用了 (l - 1) + k 的偏移量技巧。
    • 解释：因为我们要找的是区间 [l, r] 内满足条件的第 k 个点。但是在 root[l-1] 这个版本的树里，左边 1 到 l-1 的所有位置都已经填充了 1（因为它们的 prepre 肯定小于 ll）。
    • 所以，相对于整个数组（1到N），我们要找的目标其实是第 (l-1) + k 个 1。这样就可以直接复用标准的 query_global_kth 函数，不需要编写复杂的区间内第 K 小函数。