将询问离线，根据询问的区间$[l,r]$的按特定的顺序排序。一般是按$r$进行升序。
当没有询问时，可以当作是无数个区间，然后每次$r++$即可维护所有的区间，这个技术被某些人称为扫描线，但实质上是与计算几何中的扫描线不是一个东西，只是为了形象的描述而已。
eq1.P1972 HH的项链
题解
将询问离线，改成按$r$升序排序。发现同一个数字，只有最近出现的才会对答案有贡献。
维护一个树状数组，维护每个位置的贡献。对于新加入的区间的每个元素，每次对上一次位置的贡献减1（即变回0），对当前位置贡献加1（即变为1）。
然后查询$[l,r]$即可。
查看代码
struct qwq {
int l, r, id;
bool friend operator<(qwq a, qwq b) {
return a.r < b.r;
}
};
void Solve(int TIME) {
int n;cin >> n;
vi a(n + 1);for (int i = 1;i <= n;i++) cin >> a[i];
int m;cin >> m;
vc<qwq> v(m + 1);
for (int i = 1;i <= m;i++) {
int l, r;cin >> l >> r;
v[i] = { l,r,i };
}
sort(v.begin() + 1, v.end());
int lastR = 0;map<int, int> lst;vi ans(m + 1);
BIT tr(n + 1);
for (int i = 1;i <= m;i++) {
auto [l, r, id] = v[i];
for (int j = lastR + 1;j <= r;j++) {
if (lst.count(a[j])) tr.add(lst[a[j]], -1);
tr.add(j, 1);
lst[a[j]] = j;
}
lastR = r;
ans[id] = tr.query(l, r);
}
for (int i = 1;i <= m;i++) cout << ans[i] << endl;
}标签：int,询问,离线,区间,扫描线,升序,操作 From： https://www.cnblogs.com/mrsuns/p/17797683.html