1573. 【基础赛】区间（interval）

(Input: interval.in, Output: interval.out)

时间限制: 2 s 空间限制: 256 MB 

题目描述

Introl有一个长度为N且仅包含阿拉伯数字的字符串S=S1​S2​...Sn​。

他会向你询问M次，在区间[L,R]中有多少个二元组 (i,j)(i<j)满足mex(Si​,Sj​)=K。

mex()函数表示未出现在序列中的最小非负整数。

输入

从文件 interval.in 中读入数据。

第一行两个整数N和M，分别表示字符串S的长度和询问次数。

第二行仅一个字符串S。

接下来M行，每行给出L,R,K表示一组询问。

输出

输出到文件 interval.out 中。

输出共有M行，每行一个整数，表示对应的询问的答案。

样例数据

输入 #1 

5 2
10312
1 3 2
3 5 0

输出 #1 

1
3

数据范围限制

对于30% 的数据，1≤M≤10^3。

对于另外20% 的数据，K=0。

对于100% 的数据，1≤L≤R≤N,K≤3×10^3，1≤M≤10^6。

提示

区间[1,3]中：

二元组 (1,2)满足mex(1,0)=2。

区间[3,5]中：

二元组 (3,4)满足mex(3,1)=0。

二元组 (3,5)满足mex(3,2)=0。

二元组 (4,5)满足mex(1,2)=0。

#include<bits/stdc++.h>
using namespace std;
int n,m,k,l,r,f[3005][3005][3];
char s[3005];
int main()
{
	freopen("interval.in","r",stdin);
	freopen("interval.out","w",stdout);
	scanf("%d%d",&n,&m);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
	{
		int j=i,s0=0,s1=0,s2=0;
		while(j<=n)
		{
			if(s[j]=='0')
			{
				f[i][j][1]+=s2+s0;
				f[i][j][2]+=s1;
				s0++;
				
			}
			if(s[j]=='1')
			{
				f[i][j][0]+=s1+s2;
				f[i][j][2]+=s0;
				s1++;
			}
			if(s[j]>='2')
			{
				f[i][j][0]+=s1+s2;
				f[i][j][1]+=s0;
				s2++;
			}
			f[i][j][0]+=f[i][j-1][0];
			f[i][j][1]+=f[i][j-1][1];
			f[i][j][2]+=f[i][j-1][2];
			j++;
		}
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&l,&r,&k);
		if(l==r||k>2)printf("0\n");
		else printf("%d\n",f[l][r][k]);
	}
}