洛谷 P1972 分析（别看）

科技起源的小号1

2026-10-09 21:37:43

发布于：天津

3阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最大值

1.2 题目背景、允许、禁止与限制

背景：有一个长度为 $n$ 的序列，其中有一些数字
允许：求某段区间内有多少种不同的数字

1.3 题目数据范围与猜测

$1 \le n,m \le 10^6 \longrightarrow O(n~log~n)$

1.4 一句话概括题意

有一个由数字组成的序列 $a$ ，每次求某段下标区间中有多少不同的数字

2 题目破题推导

2.1 第一步：正向思维转逆向思维

正向思维：每次实时记录某个数字出现与否
逆向思维：对于每个位置 $i$ ，记录 $a_i$ 最后一次出现的地方为 $i$ 设置为 $1$ ，然后对于某个区间 $[l,r]$ ，求其中有多少个 $1$ 。这样能确保每个数字都只有至多一次记录并且一定是最新更新的

2.2 第二步：分情况讨论证明逆向思维的初步思路正确，还需扩充一点细节即可

假设有个数字 $a_i$ ，无非就三种情况

这个数字在 $[l,r]$ 内，但最后一次出现的位置在 $l$ 之前？
不可能，既然最后一次出现的位置在 $l$ 之前，说明根本没在 $[l,r]$ 内出现过！
这个数字在 $[l,r]$ 内，但最后一次出现的位置也在 $[l,r]$ 之间
这正是我们要统计的情况
额外地，不论在这个区间出现过几次，都只算有 $1$ ，这不正是“只统计最后一次出现的位置”的作用吗？
这个数字在 $[l,r]$ 内，但最后一次出现的位置在 $r$ 之后
确实有可能发生这样的情况，所以我们需要避免
因为题目给定的查询区间 $[l,r]$ 不一定按右端点有序，但是发现它若干次询问不修改原数组，那么考虑 $\huge{离线处理}$ ，即把询问区间右端点从小到大排序，这样每一次查询的一定不会出现“最后一次出现的位置在 $r$ 之后的情况”

3 模型匹配

关键词：单点修改，区间求和 $\longrightarrow$ $\huge{树状数组}$
实施方案：
vis数组： $vis_i$ 代表种类 $i$ 的贝壳最后一次的出现位置
tree树状数组：计算所有 $vis_{1 \rightarrow n}$ 在查询区间 $[i,j]$ 之间的（通过定义分析出）
关键点：
上方提到过的离线处理

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

int n, m;
const int N = 1e6 + 10;
int a[N];
int vis[N];
int tree[N];// 树状数组 
int ans[N];// 答案数组 
// 离线操作 
struct node{
	int l, r;
	int id;
}query[N]; 
bool cmp(node x, node y){
	// cmp比较逻辑: 按右端点 r 从小到大排序，这样右端点可以单调向右扫，避免重复遍历
	return x.r < y.r; 
}
int lowbit(int num){
	return num & (-num);
}
void add(int idx, int num){
	int t = idx;
	while(t <= n){
		tree[t] += num;
		t += lowbit(t);
	}
	return ;
}
int getsum(int r){
	if (r == 0){
		return 0;
	}
	return tree[r] + getsum(r - lowbit(r));
}
int getans(int r, int l){
	return getsum(r) - getsum(l);
}

int main(){
	
	scanf("%d", &n); 
	for (int i = 1;i <= n;i++){
		scanf("%d", &a[i]);
	}
	scanf("%d", &m);
	for (int i = 1;i <= m;i++){
		scanf("%d%d", &query[i].l, &query[i].r);
		query[i].id = i;// 记录query[i].id的原因: 询问按 r 排序后顺序被打乱，用 id 记录原始输入顺序，最后按 id 输出答案
	}
	sort(query + 1, query + 1 + m, cmp);
	int next = 1;// next的作用: 双指针，记录上一次扫描到的位置+1，保证数组每个元素只被扫描一次
	for (int i = 1;i <= m;i++){
		for (int j = next;j <= query[i].r;j++){
			if (vis[a[j]]){// vis数组的作用: vis[x]记录数字x上一次出现的位置
				add(vis[a[j]], -1);// -1的原因: 当前数字x在位置j再次出现，上一次出现的位置不再是“最后一次出现”，把它的贡献抹掉
			}
			add(j, 1);// +1的原因: 当前位置j是数字x最新的“最后一次出现位置”，打上标记
			vis[a[j]] = j; 
		}
		next = query[i].r + 1;
		ans[query[i].id] = getans(query[i].r, query[i].l - 1);
	}
	for (int i = 1;i <= m;i++){
		printf("%d\n", ans[i]);
	}
	
	return 0;
}