记录编号	446877	评测结果	AAAAAAAAAA
题目名称	[HAOI 2017]供给侧改革	最终得分	100
用户昵称	Imone NOI2018Au	是否通过	通过
代码语言	C++	运行时间	0.410 s
提交时间	2017-09-09 08:13:09	内存使用	48.07 MiB

#include <cstring>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;

template<typename T>
inline void read(T &x) {
	char ch; while((ch = getchar()), (ch < '0' || ch > '9'));
	x = ch - '0'; while((ch = getchar()), (ch >= '0' && ch <= '9')) x = x * 10 + (ch  - '0');
}
inline void read01(char *str) {
	char ch; while((ch = getchar()), (ch < '0' || ch > '1'));
	*(str++) = ch - '0'; while((ch = getchar()), (ch >= '0' && ch <= '1')) *(str++) = ch - '0';
}

const int MAXN = 100010;
const int MAXLEN = 40;
const int MAXNODE = MAXN * MAXLEN + 10;
char str[MAXN];
int N, NQ, maxpos[MAXLEN + 5];

namespace trie {
	int ch[MAXNODE][2], pos[MAXNODE], pool = 1;
	inline void ins(int x) {
		int i, u = 0; char c;
		for(i = x; i <= min(N, x + MAXLEN - 1); i++) {
			c = str[i];
			if(!ch[u][c]) ch[u][c] = pool++;
			u = ch[u][c];
			
			if(pos[u]) maxpos[i - x + 1] = max(maxpos[i - x + 1], pos[u]);
			pos[u] = max(pos[u], x);
		}
	}
}
struct query {
	int id, L, R;
	inline bool operator<(query rhs) const {
		return R < rhs.R;
	}
} Q[MAXN];
ll Ans[MAXN];

int main() {
	freopen("supply.in", "rt", stdin);
	freopen("supply.out", "wt", stdout);
	
	int i, p = 1, k;
	read(N); read(NQ); read01(str + 1);
	for(i = 1; i <= NQ; i++) read(Q[i].L), read(Q[i].R), Q[i].id = i;
	sort(Q+1, Q+NQ+1);

	for(i = 1; i <= N; i++) {
		trie::ins(i);
		while(p <= NQ && Q[p].R == i) {
			for(k = 1; k <= MAXLEN; k++) {
				if(maxpos[k] < Q[p].L) break;
				Ans[Q[p].id] += (ll)k * (maxpos[k] - max(maxpos[k + 1], Q[p].L - 1));
			}
			p++;
		}
	}
	for(i = 1; i <= NQ; i++) printf("%lld\n", Ans[i]);
}