分块样例全过20分球跳玄关

#include <bits/stdc++.h>
using namespace std;
struct fk {
	int l,r,add;
	int a[10];
	int m[505];
} k[505];
inline int read() {
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9') {
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9') {
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*f;
}
void write(int x) {
	if(x<0)putchar('-'),x=-x;
	if(x<10)putchar(x+'0');
	else write(x/10),putchar(x%10+'0');
}
int x,y;
int B=500;
string a;
int m[250005];
int main() {
	x=read();
	y=read();
	cin>>a;
	for(int i=0; i<a.size(); i++) m[i+1]=a[i]-'0';
	for(int i=1; i<=B; i++) {
		k[i].l=((i-1)*B)+1;
		k[i].r=i*B;
		k[i].add=0;
		for(int j=1; j<=B; j++) {
			if(k[i].l+j-1<=x) {
				k[i].m[j]=m[k[i].l+j-1];
				k[i].a[k[i].m[j]]++;
			}
		}
	}
	for(int i=1;i<=y;i++){
		int l=read(),r=read();
		int ans=0;
		for(int j=1;j<=B;j++){
			if(k[j].r<l||k[j].l>r) continue;
			else if(l<=k[j].l&&r>=k[j].r){
				for(int h=0;h<=9;h++){
					ans+=k[j].a[h]*((h+k[j].add)%10);
				}
				k[j].add++;
			}
			else{
				for(int h=1;h<=B;h++){
					if(k[j].l+h-1<=x){
						k[j].m[h]+=k[j].add;
						k[j].m[h]%=10;
					}	
					if(k[j].l+h-1<=r&&k[j].l+h-1>=l) ans+=k[j].m[h];
				}
				for(int h=1;h<=B;h++){
					if(k[j].l+h-1<=r&&k[j].l+h-1>=l){
						k[j].m[h]++;
						k[j].m[h]%=10;
					}
				}
				for(int h=0;h<=9;h++) k[j].a[h]=0;			
				for(int h=1;h<=B;h++){
					if(k[j].l+h-1<=x){
						k[j].a[k[j].m[h]]++;
					}	
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}