【算法随笔：HDU 3333 Turing tree】(线段树 | 离线 | 离散化 | 贪心）

 https://acm.hdu.edu.cn/showproblem.php?pid=3333https://acm.hdu.edu.cn/showproblem.php?pid=3333https://vjudge.net.cn/problem/HDU-3333https://vjudge.net.cn/problem/HDU-3333

题目很简单，给出长度为N的数组，Q次询问，每次给出区间[x, y), 问该区间内不同数字的和

思路：

预处理, 记录每个a[i]对应的最近相等值(max { k | k < i && a[k] == a[i]）

for(int i {}; i < N; ++i) near[i] = last[a[i]], last[a[i]] = i;

只需在更新过程中，同时维护当前时刻，value of a[i]最后出现的下标即可

注意到这里的last[a[i]]有越界风险(max {a[i]} == INT_MAX)

需要离散化

枚举每个询问区间[x, y)，对于a[i], 如果有near[i] < x, 意味着原数组最近一次出现value of a[i]不在该区间[x, y)内，也就意味着a[i]是区间中第一个出现的元素，可以被记录

由于每个区间可能有重叠，这时需要采用贪心思路和区间合并的思路，对区间左端点排序，依照次序依次处理询问区间，得到答案

具体看代码

#include <array>
#include <cstdio>
#include <algorithm>
 
constexpr auto __MAX__ { static_cast<int>(1e5) };
//数组长度最大值
 
constexpr auto __QUERIES__ { static_cast<int>(1e3) };
//询问最大次数
 
std::array<int, __MAX__ + 1> sequence {};
 
std::array<int, __QUERIES__ + 1> x {};
//询问区间左端点（闭）
std::array<int, __QUERIES__ + 1> y {};
//询问区间右端点（开）
 
std::array<int, __QUERIES__ + 1> results {};
//询问答案
 
int N {};
//数组长度
int queries {};
//询问次数
 
std::array<int, __MAX__ + 1> uniques {};  
//用于离散化的辅助数组
std::array<int, __MAX__ + 1> last{};
//记录value: sequence[i] 最后一个出现（迭代过程）的下标
std::array<int, __MAX__ + 1> left{};
//记录与value: sequence[i] 相等的最近一次下标 
 
std::array<int, __MAX__ << 2 | 1> segments {};
//线段树
std::array<int, __QUERIES__ + 1> qtable {};
//询问表排序
std::array<int, __MAX__ + 1> stable {};
//数组表排序
 
constexpr int left(int index) noexcept { return x << 1; }
constexpr int right(int index) noexcept { return x << 1 | 1; }
 
//向上更新线段树，维护数组和
constexpr update(int index) noexcept {
	segments[index] = std::plus<int>(segments[left(index)], segments[right(index)]);
}
 
 
int query(int first, int last) noexcept {
	return query(first, last, 0, N, 0);
}
//递归询问区间数组和
int query(int first, int last, int current_first, int current_last, int index) noexcept {
	if(first <= current_first && last >= current_last) return segments[index];
	int middle { (current_first + current_last)/2 };
	return (
		first < middle ? query(first, last, current_first, middle, left(index)) : 0
	+	last >= middle ? query(first, last, middle, current_last, right(index)) : 0 );
}
 
void change(int position, int value) noexcept {
	change(position, value, 0, N, 0);
}
//单点修改（加上固定常数），并且返回时维护线段树
void change(int position, int value, int first, int last, int index) noexcept {
	if(first + 1 == last) return (void) (segments[index] += v);
	int middle { (first + last)/2 };
	if(position < middle) change(position, value, first, middle, left(index));
	else change(position, value, middle, last, right(index));
	update(index);
}
 
int main(void) {
	//读数组
	std::scanf("%d", &N);
	for(int i {}; i < N; (void) (uniques[i] = sequence[i ++])) 
		std::scanf("%d", &sequence[i]);
	//读询问
	std::scanf("%d", &queries);
	for(int i {}; i < queries; ++i) 
		std::scanf("%d%d", &x[i], &y[i]);
	
	//离散化
	std::sort(uniques.begin(), uniques.begin() + N);
	auto counter { static_cast<int>(
		std::distance(uniques.begin(),
			std::unique(uniques.begin(), uniques.begin() + N))) };
	for(int i {}; i < N; ++i)
		sequence[i] = static_cast<int>(
			std::distance(uniques.begin(),
				std::lower_bound(uniques.begin(), uniques.begin() + counter, sequence[i])));
	
	//初始化last数组
	std::fill_n(last.begin(), counter, -1);
	//更新left数组
	for(int i {}; i < N; ++i) {
		left[i] = last[sequence[i]];
		last[sequence[i]] = i;
	}
	
	/*
	**	对询问和数组进行表排序，保证：
	**		1: 询问区间左端点有序
	**		2: 迭代过程中，最早出现的元素最先被遍历
	*/
	for(int i {}; i < queries; ++i) qtable[i] = i;
	for(int i {}; i < N; ++i) stable[i] = i;
	std::sort(qtable.begin(), qtable.begin() + queries, [&](int i, int j) { return x[table[i]] < x[table[j]]; });
	std::sort(stable.begin(), stable.begin() + N, [&](int i, int j) { return left[stable[i]] < left[stable[j]]; });
	
	//离线处理询问
	int sentinel {};
	//遍历每个询问
	for(int i {}; i < queries; ++i) {
		//根据left数组，把在区间中的仅一次出现的元素，插入线段树
		while(sentinel < N && left[stable[sentinel]] < x[qtable[i]]) {
			change(stable[sentinel], uniques[sequence[stable[sentinel]]]);
			++ sentinel;
		}
		//更新答案
		results[qtable[i]] = query(x[qtable[i], y[qtable[j]]);
	}
	
	//输出
	for(int i{}; i < queries; ++i) std::printf("%d%c", results[i], " \n"[! (i == queries)]);
	return 0;
}