11.CF522D Closest Equals 线段树+离线询问

11.CF522D Closest Equals 线段树+离线询问

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

给定序列，查询区间内距离最近的两个相等元素。

离线查询，按右端点加入贡献计算答案即可

洛谷传送门：CF522D Closest Equals - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：D. Closest Equals (codeforces.com)

题目分析

给定序列，查询区间内距离最近的两个相等元素。

此类涉及元素相等的问题，一般是维护每个元素上次出现的位置。

首先，我们可以对所有询问进行离线。然后按照右端点排序后开始加入贡献(与上次出现的距离)。然后固定右端点查询即可：

记录 p r e [ i ] pre[i] pre[i] 表示在 1 ∼ i − 11 1\sim i-11 1∼i−11 中跟 a [ i ] a[i] a[i]相同最近的位置。考虑离线，把询问按右端点排序，如果 p r e [ i ] ≠ 0 pre[i]\not =0 pre[i]=0 就把 p r e [ i ] pre[i] pre[i] 的位置修改为 i − p r e [ i ] i-pre[i] i−pre[i]，然后就是区间求最小值了，注意到数据范围很大，需要进行离散化。

怎么会是黑题？假的吧。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 5e5 + 10, MOD = 1e9 + 7;
int a[N], b[N];

namespace ffastIO {
	const int bufl = 1