自动搬运

查看原文

来自洛谷，原作者为

	Ptilopsis_w 你以为我是谁？这是我埋下的因，我要亲手解决这一切。

搬运于2025-08-24 22:21:51，当前版本为作者最后更新于2020-10-27 16:38:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题的题意很简单这里就不赘述了

首先看数据范围,$n<=10^6$, $m<=10^3$,肯定不能暴力求解了，但是对于这道题，$1,4,5$的所在位置对答案没有影响，所以我们可以分别记录$1,4,5$的数量，每次修改时维护这个数量就可以了,但是每次询问乘积时如果直接求的话会TLE,所以我们可以预处理出$4,5$的次幂来，每次询问直接调用就好了

注意模数是99824353，不要想当然 (Ctrl+C是个好东西)

下面是代码详解

#include<bits/stdc++.h>
#define MAXN 1000000
using namespace std;
typedef long long ll;
int m, tot[6], a[MAXN+5];
ll pow4[MAXN+5], pow5[MAXN+5];
const ll mod = 99824353;
int main()
{
	pow4[0] = pow5[0] = 1;//预处理4,5的次幂
	for(int i = 1; i <= MAXN; i++)
		pow4[i] = (pow4[i-1]*4) % mod, pow5[i] = (pow5[i-1]*5) % mod;
	char ch;
	int cnt = 0;
	while(ch = getchar(), ch != '\n')
	{//逗号表达式返回最后一个语句的值,这个while就是每次读入一个字符存到ch里,如果ch是换行就结束循环
		cnt++;
		a[cnt] = ch-'0';
		tot[a[cnt]]++;//数据只有1,4,5，可以直接用数组下标对应
	}
	scanf("%d", &m);
	while(m--)
	{
		int l, r;
		scanf("%d%d", &l, &r);getchar();//注意这里要先用一个getchar()读掉r后面的空格,不然会RE
		for(int i = l; i <= r; i++)
		{
			int x = getchar()-'0';
			tot[a[i]]--;//原a[i]对应的数的数量减一
			tot[x]++;//新a[i]对应的数的数量加一
			a[i] = x;//一定要把a[i]换掉,不然重复更新的时候会出错
		}
		ll sum = (tot[1] + 4*tot[4] + 5*tot[5]) % mod;
		ll p = (pow4[tot[4]] * pow5[tot[5]]) % mod;//已经预处理过4,5的次幂了,直接调用就可以 (没有1的原因都懂)
		printf("%d %lld %lld\n", tot[1], sum, p);//注意longlong要用%lld,不然会见祖宗的
	}
	return 0;
}