题意

有一个长度为 $n$ 的序列 $a$，$m$ 次询问，求区间 $[L,R]$ 长度分别为 $[1,10]$ 的极长值域连续段个数。

定义值域连续段为满足以下条件的区间。

• 对区间 $[L,R]$ 去重并排序之后，选出的区间 $[l,r]$ 满足 $\forall i \in [l+1,r],b_{i}=b_{i-1}+1$

分析

$1 \le n \le 10^6$，考虑可以 $O(nk\log n)$ 做，其中 $k = 10$。这种情况看上去不好线段树做，因为答案与询问的区间关系十分紧密，那就考虑离线，然后用神秘数据结构维护。

考虑将询问按照 $r$ 排序，那么就考虑新添加的 $i$ 对之前每个区间的答案有什么影响。设 $lst_x$ 表示之前数字 $x$ 最后一次出现在哪。那么新添加的 $a_i$ 是不会对左端点在 $lst_{a_i}$ 之前的点产生影响的。因为这个序列 $b$ 最终是要去重的。所以我们只要考虑左端点在 $(lst_{a_i},i]$ 之间的区间即可。

我们添加一个数字 $a_i$，会影响到值当且仅当以下三种情况。

• 作为一段值域的开头。
• 作为一段值域的结尾。
• 连接了两段值域。

这三种情况都需要考虑与 $a_i$ 相邻的值。但是我们知道我们只要长度为 $10$ 的区间长度，所以值域范围也不会超过 $10$。所以我们只需要取 $[a_i-10,a_i+10]$ 的数字考虑即可。我们可以从后往前考虑，依次加入数字。因为我们只要在 $[a_i-10,a_i+10]$ 的数字，且只要最后一个，其他数字都不用考虑，所以可以直接依次枚举，然后暴力移动至于的左右端点。因为数字只有最多 $21$ 个，移动次数就不会超过 $21$ 次。这样子我们就找到了极长值域连续段。

不妨设我们现在的极长值域范围是 $[a_i-l,a_i+r]$，那么首先对于长度为 $l$ 和长度为 $r$ 的，他们不再是极长的，所以要减去。而对于新的区间，如果长度不超过 $10$，那么就可以加上贡献。

所以我们现在要支持区间加，单点查，直接套树状数组即可。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 1000005
#define L (max(a[i] - 11, 1))
#define R (min(a[i] + 11, 1000000))
il ll rd(){
    ll s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, m, a[N], l, r, ans[N][15], vis[N], lst[N];
struct P{
    int id, val;
};
bool operator < (const P& a, const P& b){return a.id > b.id;}
vector <P> query[N];
struct BIT{
    int tr[N];
    il void add(int x, int k){for (int i = x; i <= n; i += (i & (-i))) tr[i] += k;}
    il int ask(int x){int ans = 0;for (int i = x; i >= 1; i -= (i & (-i))) ans += tr[i];return ans;}
}T[35];
int main(){
    n = rd(), m = rd();
    for (int i = 1; i <= n; i++) a[i] = rd();
    for (int i = 1; i <= m; i++) l = rd(), r = rd(), query[r].push_back(P{i, l});
    for (int i = 1; i <= n; i++){
        vector <P> pt;
        vector <int> del;
        for (int j = L; j <= R; j++) if (lst[j] && lst[j] > lst[a[i]]) pt.push_back(P{lst[j], j});
        vis[a[i]] = 1, pt.push_back(P{lst[a[i]], -1}), pt.push_back(P{i, a[i]});
        sort (pt.begin(), pt.end());
        for (int j = 0, l = 0, r = 0; j < pt.size() - 1; j++){
            if (~pt[j].val) vis[pt[j].val] = 1, del.push_back(pt[j].val);
            for (; vis[a[i] - l - 1]; l++);for (; vis[a[i] + r + 1]; r++);
            int s = l + r + 1;
            if (1 <= l && l <= 10) T[l].add(pt[j + 1].id + 1, -1), T[l].add(pt[j].id + 1, 1);
            if (1 <= r && r <= 10) T[r].add(pt[j + 1].id + 1, -1), T[r].add(pt[j].id + 1, 1);
            if (1 <= s && s <= 10) T[s].add(pt[j + 1].id + 1, 1), T[s].add(pt[j].id + 1, -1);
        }
        vis[a[i]] = 0;
        for (int p : del) vis[p] = 0;
        lst[a[i]] = i;
        for (P p : query[i]) for (int j = 1; j <= 10; j++) ans[p.id][j] = T[j].ask(p.val);
    }

    for (int i = 1; i <= m; i++, putchar('\n')) for (int j = 1; j <= 10; j++) putchar(ans[i][j] % 10 + 48);
    return 0;
}