专栏文章

P6357 [COCI 2007/2008 #3] REDOKS 题解

llzh0220
P6357题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mipsn6dy
此快照首次捕获于
2025/12/03 17:17
3 个月前
此快照最后确认于
2025/12/03 17:17
3 个月前
查看原文

思路

题解区里基本上都是线段树做法，那我来说一下分块。
首先我们需要维护每个块内 00 到 99 分别出现的次数。对于每个块，维护一个类似懒标记的东西，记录这个整块 +1+1 的次数。
查询时直接暴力修改散块，对于整块打上懒标记，求出答案即可。
时间复杂度 O(nn)O(n\sqrt n)，实测跑的飞快。

code

CPP
const int N=250010,M=510;
int bl[N],sum[M][10],t[M],a[N],to[10][10];
signed main(){
	for(int i=0;i<=9;i++)for(int j=0;j<=9;j++)to[i][j]=(i+j)%10;
	int n=read(),m=read(),len=sqrt(n);
	for(int i=1;i<=n;i++){
		bl[i]=(i-1)/len+1;
		a[i]=getch()-'0';
		sum[bl[i]][a[i]]++;
	}
	while(m--){
		int l=read(),r=read();
		if(t[bl[l]]){
			for(int i=0;i<=9;i++)sum[bl[l]][i]=0;
			for(int i=bl[l]*len-len+1;i<=bl[l]*len;i++){
				a[i]=to[a[i]][t[bl[l]]];
				sum[bl[l]][a[i]]++;
			}t[bl[l]]=0;
		}
		if(t[bl[r]]){
			for(int i=0;i<=9;i++)sum[bl[r]][i]=0;
			for(int i=bl[r]*len-len+1;i<=bl[r]*len;i++){
				a[i]=to[a[i]][t[bl[r]]];
				sum[bl[r]][a[i]]++;
			}t[bl[r]]=0;
		}int ans=0;
		if(bl[l]==bl[r]){
			for(int i=l;i<=r;i++)ans+=a[i];
			printf("%lld\n",ans);
			for(int i=l;i<=r;i++){
				sum[bl[i]][a[i]]--;
				a[i]=to[a[i]][1];
				sum[bl[i]][a[i]]++;
			}continue;
		}
		for(int i=l;i<=bl[l]*len;i++)ans+=a[i];
		for(int i=bl[r]*len-len+1;i<=r;i++)ans+=a[i];
		for(int i=l;i<=bl[l]*len;i++){
			sum[bl[i]][a[i]]--;
			a[i]=to[a[i]][1];
			sum[bl[i]][a[i]]++;
		}
		for(int i=bl[r]*len-len+1;i<=r;i++){
			sum[bl[i]][a[i]]--;
			a[i]=to[a[i]][1];
			sum[bl[i]][a[i]]++;
		}
		for(int i=bl[l]+1;i<=bl[r]-1;i++){
			for(int j=0;j<=9;j++)ans+=to[j][t[i]]*sum[i][j];
			t[i]=to[t[i]][1];
		}printf("%lld\n",ans);
	}
	ret 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...