C.能源 energy.cpp

题目描述

新任市长$Chihiro$给$Introl$传真了当地行政规划图，其用长度为$N$字符串$S$表示，其中$0$和$1$分别表示空地和城区。

定义$x_i$和$x_j$的$φ$距离为$\lvert x_i-x_j \rvert+1$。

$Introl$规划在空地和城区分别建设风车和光伏发电板，对于一处空地其每天能获取的风能为$E_{wind}^2$，对于一处城区其每天能获取的光能为$E_{solar}^3$。

最大的$E_{wind}$满足到该空地的$φ$距离不超过最大的$E_ {wind}$的地方在行政规划片区内且为空地。

最大的$E_ {solar}$满足到该城区的$φ$距离不超过最大的$E_ {solar}$的地方在行政规划片区内且为城区。

$Chihiro$将提出$M$次询问，对于片区$[L,R]$每天共能获取多少能源，答案对$1e9+7$取模。

输入格式

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

第二行仅一个字符串$S$。

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

输出格式

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

样例 #1

样例输入 #1

5 2
11100
1 3
4 5

样例输出 #1

10
2

提示

样例1解释

当地所有片区能获得的能源分别为：$1,8,1,1,1$​。

对于片区$[1,3]$能获得的能源为$1+8+1=10$​。

对于片区$[4,5]$能获得的能源为$1+1=2$。

数据范围

对于$30$%的数据，$1 \leq N,M \leq 10^3$。

对于另外$20$%的数据，$S$仅包含$0$。

对于$100$%的数据，$1 \leq L \leq R \leq N,M \leq10^6$

我的解法:

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000010];
char s[1000010];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++) a[i]=s[i-1]-'0';
	a[n+1]=-1;
	for(int i=1;i<=n;i++){
		int L=i,R=i;
		while(a[R]==a[i]) R++;
		R--;
		if(L==R){
			a[L]=1;
			continue;
		} else if(R-L==1) {
			a[L]=1;
			a[R]=1;
			continue;
		}
		for(int j=L;i<=(L+R)/2;j++){
			a[j]=j-L+1;
		}
		for(int j=(L+R)/2+1;j<=R;j++){
			a[j]=R-j+1;
		}
		i=R;
	} 
	for(int i=1;i<=n;i++) cout<<a[i]<<" ";
	for(int i=1;i<=n;i++){
		if(s[i]=='0') a[i]=(a[i]*a[i])%int(1e9+7);
		else a[i]=(a[i]*a[i]*a[i])%int(1e9+7);
	}
	long long psum[1000010];
	psum[1]=a[1];
	for(int i=2;i<=n;i++) psum[i]=psum[i-1]+a[i];
	for(int i=1;i<=m;i++){
		int l,r;
		cin>>l>>r;
		cout<<psum[r]-psum[l -1];
	}
	return 0;
}