有一个长度为 \(n(n\le 10^5)\) 的序列 \(\{a\}(a_i\le 10^5)\)，你可以对它进行操作，操作如下：首先选择三个数 \(v, t, k\)，满足 \(a_v = a_{v+t} = a_{v + 2t} = \cdots = a_{v + kt}\)，然后将其删除，得到一个新的序列。每次操作结束后你都能将新数列重排。
现有 \(Q(Q\le 10^5)\) 个询问，每次询问 \([l, r]\) 表示问要把 \([l, r]\) 删除所需的最小步数。
（以上翻译改写自洛谷）
题解
感觉像是 HH 的项链 的升级版。
不难发现答案就是 \([l, r]\) 不同数的个数 \(+\) 第一次在 \([l,r]\) 中是否有一种数被删掉。
记两个数组 \(fa[i]\) 与 \(ffa[i]\)，\(fa[i]\) 表示上一次第 \(i\) 个数出现在了那里，\(ffa[i]\) 表示如果询问的 \(l\le ffa[i]\)，那么在 \([l, r]\) 区间内与第 \(i\) 个数相同的不可能被一次性删除。
大致就是这样一幅图：
上方实线表示 \(fa[i]\)，下方红色虚线表示 \(ffa[i]\)（如果 \(fa[i]\) 或 \(ffa[i]\) 连到了 \(0\) 就没画）。
不难得出如果 \(i - fa[i] = fa[i] - fa[fa[i]]\)，那么 \(ffa[i] = ffa[fa[i]]\)，否则 \(ffa[i] = fa[fa[i]]\)。
for(int i = 1, aa; i <= n; ++i)
{
scanf("%d", &aa);
fa[i] = lst[aa];
lst[aa] = i;
ffa[i] = (fa[i] - fa[fa[i]] == i - fa[i]) ? ffa[fa[i]] : fa[fa[i]];
}
我们考虑离线，让询问按 \(r\) 为关键字排序。
考虑查询 \([l, r]\)，如果是这样一段序列：\(1, 2, 2, 2, 3\)，我们发现 \(2\) 出现了 \(3\) 次，我们钦定最后一个 \(2\) 对答案有贡献。这样我们对所有相同的数，都钦定最后一个对答案有贡献，其余对答案即可。这样没加入一个数，就在线段树/树状数组对 \(i\) 位置加 \(1\)，在 \(fa[i]\) 位置减 \(1\) 即可（把前一个数的贡献删去）。
对于询问第一次能否完全删除一个数，我们只需查询有多少个数在 \([l, r]\) 上不是均匀分布即可。同理，我们钦定最后一个对答案有贡献，没加入一个 \(i\) 时，在 \(ffa[fa[i]]\) 上 \(-1\)，在 \(ffa[i]\) 上 \(+1\) 即可。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100005;
int n;
struct Tree
{
int no[maxn << 2];
int K;
inline void build_tree()
{
for(K = 1; K <= n; K <<= 1);
}
inline void add(int k, int x)
{
if(!k)
return;
for(k += K; k; k >>= 1)
no[k] += x;
}
inline int query(int l, int r)
{
int ans = 0;
for(l += K - 1, r += K + 1; l ^ r ^ 1; l >>= 1, r >>= 1)
{
if(~l & 1)
ans += no[l ^ 1];
if(r & 1)
ans += no[r ^ 1];
}
return ans;
}
} tr1, tr2;
int fa[maxn], ffa[maxn], lst[maxn];
struct ask
{
int l, r, id;
friend bool operator < (ask a, ask b)
{
return a.r < b.r;
}
} q[maxn];
int ans[maxn];
int main()
{
scanf("%d", &n);
tr1.build_tree(), tr2.build_tree();
for(int i = 1, aa; i <= n; ++i)
{
scanf("%d", &aa);
fa[i] = lst[aa];
lst[aa] = i;
ffa[i] = (fa[i] - fa[fa[i]] == i - fa[i]) ? ffa[fa[i]] : fa[fa[i]];
}
int Q;
scanf("%d", &Q);
for(int i = 1; i <= Q; ++i)
{
scanf("%d%d", &q[i].l, &q[i].r);
q[i].id = i;
}
sort(q + 1, q + Q + 1);
for(int i = 1, now = 0; i <= Q; ++i)
{
register int l = q[i].l, r = q[i].r;
while(now < r)
{
now++;
tr1.add(fa[now], -1);
tr1.add(now, 1);
tr2.add(ffa[fa[now]], -1);
tr2.add(ffa[now], 1);
}
int tt1 = tr1.query(l, r), tt2 = tr2.query(l, r);
ans[q[i].id] = tt1 + (tt1 == tt2);
}
for(int i = 1; i <= Q; ++i)
printf("%d\n", ans[i]);
return 0;
}