Luogu

分析

把询问离线，从左往右加入每个数并维护以这个数为右端点时每个左端点的答案。

假设当前加入了 $x$，那么它显然不会更新 $a_x$ 上一次出现位置之前的左端点的答案（因为这些区间排序去重后根本没有变化），而且只会和 $[x-11,x+11]$ 的数产生贡献（因为只需要统计 $\leq 10$ 的长度）。而插入 $x$ 后极长值域连续段可能会有以下变化

• 从 $[a,x-1]$ 变成了 $[a,x]$；
• 从 $[x+1,b]$ 变成了 $[x,b]$；
• 从 $[a,x-1]\cup[x+1,b]$ 变成了 $[a,b]$。

我们把所有 $[x-11,x+11]$ 内的数在已经加入的数中的最后位置从大到小排序并依次插入，显然当前插入的数会影响左端点在它到下一个数的位置 $-1$ 的答案。具体的，这些位置原来存在的长度为 $L,R$ 的极长值域连续段变成了一个长度为 $L+R+1$ 的极长值域连续段。开 $10$ 个树状数组维护每个左端点对应的每种长度的个数即可。

可以参考代码理解。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;

int n,m,a[N],lst[N],vis[N],ans[N][15];
struct query { int l,id; };
vector<query> q[N];
struct num { int p,w; };
bool operator <(num x,num y) { return x.p>y.p; }
vector<num> v;
vector<int> del;

struct BIT {
    int c[N];
    void add(int x,int y) { for (;x<=n;x+=x&-x) c[x]+=y; }
    int sum(int x) { int s=0; for (;x;x-=x&-x) s+=c[x]; return s; }
} t[11];

int main() {
    n=read(),m=read();
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<=m;++i) {
        int l=read(),r=read();
        q[r].emplace_back((query){l,i});
    }
    for (int i=1;i<=n;++i) {
        v.clear(),del.clear();
        for (int j=max(1,a[i]-11);j<=a[i]+11;++j)
            if (lst[j]>lst[a[i]]) v.emplace_back((num){lst[j],j});
        v.emplace_back((num){lst[a[i]],0}),v.emplace_back((num){i,a[i]});
        sort(v.begin(),v.end());
        for (int j=0,L=0,R=0;j<v.size()-1;++j) {
            vis[v[j].w]=1; del.emplace_back(v[j].w);
            while (vis[a[i]-L-1]) ++L;
            while (vis[a[i]+R+1]) ++R;
            int U=L+R+1;
            if (1<=L&&L<=10) t[L].add(v[j+1].p+1,-1),t[L].add(v[j].p+1,1);
            if (1<=R&&R<=10) t[R].add(v[j+1].p+1,-1),t[R].add(v[j].p+1,1);
            if (1<=U&&U<=10) t[U].add(v[j+1].p+1,1),t[U].add(v[j].p+1,-1);
        }
        for (int j:del) vis[j]=0;
        for (auto j:q[i])
            for (int k=1;k<=10;++k)
                ans[j.id][k]=t[k].sum(j.l);
        lst[a[i]]=i;
    }
    for (int i=1;i<=m;++i) {
        for (int j=1;j<=10;++j)
            putchar(ans[i][j]%10+'0');
        putchar('\n');
    }
    return 0;
}