洛谷 P1972 分析（别看）

科技起源

2026-07-09 12:31:11

发布于：河北

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 大拆小、小组大

2.2 正向思维转逆向思维，逆向思维转正向思维

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

2.3 分情况考虑

2.4 数学

2.5 以终为始、以始为终

2.6 手动推导

2.7 边界测试

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：单点修改，区间求和 $\longrightarrow$ $\huge{树状数组}$
实施方案：
vis数组： $vis_i$ 代表种类 $i$ 的贝壳最后一次的出现位置
tree树状数组：计算所有 $vis_{1 \rightarrow n}$ 在查询区间 $[i,j]$ 之间的（通过定义分析出）
关键点：
因为我们要确保不会出现形如先查询 $[2,4]$ 再查询 $[1,3]$ 的问题（否则会导致“到当前位置 $a_i$ 最后一次出现”计算错误）。因此离线处理，排序 $r$ 右端点，能时刻保证状态合法

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比较逻辑
	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的原因 
	}
	sort(query + 1, query + 1 + m, cmp);
	int next = 1;// next的作用 
	for (int i = 1;i <= m;i++){
		for (int j = next;j <= query[i].r;j++){
			if (vis[a[j]]){// vis数组的作用 
				add(vis[a[j]], -1);// -1的原因 
			}
			add(j, 1);// +1的原因
			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;
}