求解区间段数（区间查询）_题解

科技前沿 • 2025-02-21 18:49 • 阅读 41

大家好，我是讯享网，很高兴认识大家。

【题解提供者】吴立强

解法

思路

若从前往后给每一段的元素赋值，第 $i$ 段元素都赋值为 $i$ 那么单次查询的答案就是两个端点处元素值的差值加 1（等价于中间存在多少个不同的元素）。

例如数组 {2, 2, 3, 1, 3, 3} 就会被赋值为 {1, 1, 2, 3, 4, 4}，当完成这个转化之后答案即可 $O (1)$ 查询。

代码展示

#include <iostream> using namespace std; const int N = ; int a[N], d[N]; int main() { 
    int n, m; cin >> n >> m; for(int i = 1; i <= n; i ++) { 
    cin >> a[i]; d[i] = d[i - 1] + (a[i] != a[i - 1]); /// 给元素赋值，其实就是计算前缀和 } int l, r; while(m --) { 
    cin >> l >> r; cout << d[r] - d[l] + 1 << endl; /// 存在第 d[l], d[l]+1, d[l]+2, ..., d[r] 段 } return 0; }

讯享网

算法分析

程序时间复杂度为 $O (n + m)$ 。

讯享网

拓展

【思路】中只介绍了一种理解算法的角度，实际上可以将第 17 行式子理解成前缀和，而 +1 可以被理解成第一段必定存在。

还可以使用另一个式子来解决问题：

讯享网cout << d[r] - d[l-1] + (a[l-1] == a[l]) << endl;

上述式子则是完整的前缀和求区间（sum[r] - sum[l-1]），而被加上的部分则是前缀和算法漏算的部分，感兴趣的同学可以群内讨论或者自己思考。

求解区间段数（区间查询）_题解

【题解提供者】吴立强

解法

思路

代码展示

算法分析

拓展

相关推荐