题意
将颜色由浅到深用\(1\)到\(N\)标号（\(1\)是很浅的颜色，\(N\)是很深的颜色）。
从而她可以用一个长为\(N\)的整数数组来描述她想要给栅栏的每一小段涂上的颜色。
初始时，所有栅栏小段均未被上色。
一笔可以给任意连续若干小段涂上同一种颜色，但只能用较深的颜色覆盖较浅的颜色。
有\(Q\)个询问，每次询问区间\([l,r]\)之间的栅栏上色用的最少笔数。
\(100\%, 1≤N,Q≤2*10^5\)。
思路
先考虑如何暴力求出一个区间的答案。
对于两个相同的颜色\(x\)，它们如何可以用一笔来涂：当它们之间的最小值大于等于\(x\)。
如果比\(x\)小，那么涂了\(x\)后，最小值不能覆盖在\(x\)的上面。
对于每个区间，得出了一个\(O(N)\)的算法：
即枚举每一个数，找到上一个相同的数，判断区间最小值（利用ST表）与它们的关系。
可以先预处理\(sum_i\)代表\(1 \sim i\)的答案。
现在对于区间\([l,r]\)，我们可以考虑答案为\(sum_r-sum_{l-1}\)。
然而，这个区间存在一些涂色笔画是从\([1,l-1]\)中的颜色接着涂过来的，我们还要统计这些个数。
具体地，在预处理时算出当前点是从哪里涂过来的，对于每个询问即查询\([l,r]\)中\(\leq l-1\)的个数。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
int n, q, m, tot;
int a[200001], f[200001][19], lg[200001], las[200001], pre[200001], sum[200001], root[200001];
struct SegmentTree {
int lc, rc;
int dat;
} tree[20000001];
int ask(int now, int l, int r, int L, int R) {
if (L <= l && r <= R)
return tree[now].dat;
int mid = l + r >> 1, res = 0;
if (L <= mid)
res += ask(tree[now].lc, l, mid, L, R);
if (R > mid)
res += ask(tree[now].rc, mid + 1, r, L, R);
return res;//woshishabi
}
int query(int l, int r) {
if (l > r)
return a[l];
int x = lg[r - l + 1];
return std::min(f[l][x], f[r - (1 << x) + 1][x]);
}
int build(int l, int r) {
int p = ++tot;
if (l == r)
return p;
int mid = l + r >> 1;
tree[p].lc = build(l, mid);
tree[p].rc = build(mid + 1, r);
return p;
}
int insert(int now, int l, int r, int x) {
int p = ++tot;
tree[p] = tree[now];
if (l == r) {
tree[p].dat++;
return p;
}
int mid = l + r >> 1;
if (x <= mid)
tree[p].lc = insert(tree[now].lc, l, mid, x);
else
tree[p].rc = insert(tree[now].rc, mid + 1, r, x);
tree[p].dat = tree[tree[p].lc].dat + tree[tree[p].rc].dat;
return p;
}
int main() {
scanf("%d %d", &n, &q);
lg[0] = -1;
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]), m = std::max(m, a[i]), f[i][0] = a[i], lg[i] = lg[i >> 1] + 1, pre[i] = n + 1;
for (int j = 1; j <= 19; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
f[i][j] = std::min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
int tmp = 0;
for (int i = 1; i <= n; i++) {
if (las[a[i]] && query(las[a[i]] + 1, i - 1) >= a[i])
sum[i] = tmp, pre[i] = las[a[i]];
else
sum[i] = ++tmp;
las[a[i]] = i;
}
root[0] = build(1, n);
for (int i = 1; i <= n; i++)
root[i] = pre[i] <= n ? insert(root[i - 1], 1, n, pre[i]) : root[i - 1];
int l, r;
for (int i = 1; i <= q; i++) {
scanf("%d %d", &l, &r);
if (l == 1) {
printf("%d\n", sum[r]);
continue;
}
printf("%d\n", sum[r] - sum[l - 1] + (ask(root[r], 1, n, 1, l - 1) - ask(root[l - 1], 1, n, 1, l - 1)));
}
}