Leha and security system（Codeforces 794F）（线段树懒标记）

文章目录

• 题目
• 思路
• 代码
• 思考

题目

CF

a i ≤ 1 0 9 a_i\le10^9 ai​≤109

思路

不难想到用线段树维护， s u m [ i ] [ j ] sum[i][j] sum[i][j] 表示区间 [ l , r ] [l,r] [l,r] 中数码为 j j j 的和除以 j j j

但是如何维护呢，我们记 l a z y [ i ] [ j ] lazy[i][j] lazy[i][j] 表示 [ l , r ] [l,r] [l,r] 中数码为 j j j 的和转移到数码为 l a z y [ i ] [ j ] lazy[i][j] lazy[i][j] 的和，即时生效（即对儿子的起作用）

void PushDown(int i){
	for(int t=0;t<=9;t++)
		tmp[t]=sum[lch][t];
	for(int t=0;t<=9;t++)
		lazy[lch][t]=lazy[i][lazy[lch][t]];
	for(int t=0;t<=9;t++)
		if(lazy[i][t]!=t){
			tmp[lazy[i][t]]+=sum[lch][t];
			tmp[t]-=sum[lch][t];
		}
	for(int t=0;t<=9;t++)
		sum[lch][t]=tmp[t];
	for(int t=0;t<=9;t++)
		tmp[t]=sum[rch][t];
	for(int t=0;t<=9;t++)
		lazy[rch][t]=lazy[i][lazy[rch][t]];
	for(int t=0;t<=9;t++)
		if(lazy[i][t]!=t){
			tmp[lazy[i][t]]+=sum[rch][t];
			tmp[t]-=sum[rch][t];
		}
	for(int t=0;t<=9;t++)
		sum[rch][t]=tmp[t];
	for(int t=0;t<=9;t++)
		lazy[i][t]=t;
	return ;
}
           

P u s h D o w n PushDown PushDown 写得非常玄幻,我们可以一步步看

for(int t=0;t<=9;t++)
	lazy[lch][t]=lazy[i][lazy[lch][t]];
           

想一想， l a z y lazy lazy 是对儿子生效的，也就是说本层的 l a z y lazy lazy 是不会影响自己的，我们可以先将儿子的 l a z y lazy lazy 修改，本来是孙子要从 t − > l a t -> la t−>la 但是又来了一个 l a − > p la->p la−>p 于是就变为了 t − > p t->p t−>p

for(int t=0;t<=9;t++)
	tmp[t]=sum[lch][t];
for(int t=0;t<=9;t++)
	if(lazy[i][t]!=t){
		tmp[lazy[i][t]]+=sum[lch][t];
		tmp[t]-=sum[lch][t];
	}
for(int t=0;t<=9;t++)
	sum[lch][t]=tmp[t];
           

现在和儿子的 l a z y lazy lazy 没有任何关系了，我们就只更改儿子的 s u m sum sum

但是我们不能直接修改儿子的 s u m sum sum 因为我们需要这个历史版本去更新这个儿子其他的 s u m sum sum 于是就用了一个临时数组

注意你修改后不能直接将 t m p tmp tmp 赋值为0(第6行)，因为可能已经保存了一些修改后 s u m sum sum 的信息

然后就常规了

代码

//#pragma GCC optimize(2)
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<climits>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int read(){
	bool f=0;int x=0;char c=getchar();
	while(c<'0'||'9'<c){if(c=='-')f=1;c=getchar();}
	while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return !f?x:-x;
}
#define lch (i<<1)
#define rch (i<<1|1)
#define MAXN 200000
#define INF 0x3f3f3f3f
int lazy[5*MAXN+5][10];
LL sum[5*MAXN+5][10];
void PushUp(int i){
	for(int t=0;t<=9;t++)
		sum[i][t]=sum[lch][t]+sum[rch][t];
	return ;
}
LL tmp[10];
void PushDown(int i){
	for(int t=0;t<=9;t++)
		tmp[t]=sum[lch][t];
	for(int t=0;t<=9;t++)
		lazy[lch][t]=lazy[i][lazy[lch][t]];
	for(int t=0;t<=9;t++)
		if(lazy[i][t]!=t){
			tmp[lazy[i][t]]+=sum[lch][t];
			tmp[t]-=sum[lch][t];
		}
	for(int t=0;t<=9;t++)
		sum[lch][t]=tmp[t];
	for(int t=0;t<=9;t++)
		tmp[t]=sum[rch][t];
	for(int t=0;t<=9;t++)
		lazy[rch][t]=lazy[i][lazy[rch][t]];
	for(int t=0;t<=9;t++)
		if(lazy[i][t]!=t){
			tmp[lazy[i][t]]+=sum[rch][t];
			tmp[t]-=sum[rch][t];
		}
	for(int t=0;t<=9;t++)
		sum[rch][t]=tmp[t];
	for(int t=0;t<=9;t++)
		lazy[i][t]=t;
	return ;
}
void Build(int i,int L,int R){
	for(int t=0;t<=9;t++)
		lazy[i][t]=t,sum[i][t]=0;
	if(L==R){
		int x=read(),tmp=1;
		while(x)
			sum[i][x%10]+=tmp,tmp*=10,x/=10;
		return ;
	}
	int Mid=(L+R)>>1;
	Build(lch,L,Mid),Build(rch,Mid+1,R);
	PushUp(i);
	return ;
}
void Modify(int i,int L,int R,int qL,int qR,int x,int y){
	if(qL<=L&&R<=qR){
		for(int t=0;t<=9;t++)
			if(lazy[i][t]==x){
				lazy[i][t]=y;
				sum[i][y]+=sum[i][x];
				sum[i][x]=0;
			}
		return ;
	}
	PushDown(i);
	int Mid=(L+R)>>1;
	if(qL<=Mid)
		Modify(lch,L,Mid,qL,qR,x,y);
	if(Mid+1<=qR)
		Modify(rch,Mid+1,R,qL,qR,x,y);
	PushUp(i);
	return ;
}
LL Query(int i,int L,int R,int qL,int qR){
	if(qL<=L&&R<=qR){
		LL ret=0;
		for(int t=0;t<=9;t++)
			ret+=sum[i][t]*t;
		return ret;
	}
	PushDown(i);
	LL ret=0;
	int Mid=(L+R)>>1;
	if(qL<=Mid)
		ret+=Query(lch,L,Mid,qL,qR);
	if(Mid+1<=qR)
		ret+=Query(rch,Mid+1,R,qL,qR);
	return ret;
}
int main(){
	int n=read(),q=read();
	Build(1,1,n);
	for(int i=1;i<=q;i++){
		int opt=read();
		if(opt==1){
			int l=read(),r=read(),x=read(),y=read();
			if(x==y) continue;
			Modify(1,1,n,l,r,x,y);
		}
		else{
			int l=read(),r=read();
			printf("%lld\n",Query(1,1,n,l,r));
		}
	}
	return 0;
}

           

思考

分清即时生效和非即时生效的 l a z y lazy lazy ，即时生效的 P u s h D o w n PushDown PushDown 比较难写时可以将修改儿子 l a z y lazy lazy 和其它信息分开处理，记住即时生效写法儿子的 l a z y lazy lazy 一定不会影响儿子本身，写 P u s h D o w n PushDown PushDown 一定要思路清晰。