C++11(clang++ 3.9) 解法, 执行用时: 569ms, 内存消耗: 23924K, 提交时间: 2018-04-02 08:50:16

#include<bits/stdc++.h>
#define MAXN 1000050
using namespace std;
int N,M;
char ans[MAXN][15];
int A[MAXN],pos[MAXN];
struct Query{
	int l,r,id;
	bool operator < (const Query &rtm) const{
		return r<rtm.r;
	}
}Q[MAXN];
struct BIT{
	int a[11][MAXN],n;
	#define Lowbit(x) (x&(-x))
	void Modify(int k,int p,int v){
		for(;p<=n;p+=Lowbit(p)) a[k][p]+=v;
	}
	int Query(int k,int p,int ret=0){
		for(;p;p-=Lowbit(p)) ret+=a[k][p];
		return ret;
	}
}DT;
int main(){
	scanf("%d%d",&N,&M); DT.n=1000000;
	for(int i=1;i<=N;i++) scanf("%d",&A[i]);
	for(int i=1;i<=M;i++) Q[i].id=i,scanf("%d%d",&Q[i].l,&Q[i].r);
	sort(Q+1,Q+M+1);
	for(int i=1,j=1;i<=N&&j<=M;i++){
		int last=pos[A[i]],cur=i,ll=0,rr=0,pre;
		while(cur>last&&(ll<=10||rr<=10)){
			pre=cur; cur=last;
			if(ll<=10) cur=max(cur,pos[max(A[i]-ll-1,0)]);
			if(rr<=10) cur=max(cur,pos[min(A[i]+rr+1,1000000)]);
			if(ll&&ll<=10) DT.Modify(ll,cur+1,-1),DT.Modify(ll,pre+1,1);
			if(rr&&rr<=10) DT.Modify(rr,cur+1,-1),DT.Modify(rr,pre+1,1);
			if(ll+rr+1<=10) DT.Modify(ll+rr+1,cur+1,1),DT.Modify(ll+rr+1,pre+1,-1);
			while(ll<=10&&A[i]-ll-1>=1&&pos[A[i]-ll-1]>=cur) ++ll;
			while(rr<=10&&A[i]+rr+1<=1000000&&pos[A[i]+rr+1]>=cur) ++rr;
		}
		for(pos[A[i]]=i;j<=M&&Q[j].r==i;j++)
			for(int k=1;k<=10;k++)
				ans[Q[j].id][k]='0'+DT.Query(k,Q[j].l)%10;
	}
	for(int i=1;i<=M;i++) puts(ans[i]+1);
	return 0;
}