文章目錄
- 題目
- 思路
- 代碼
- 思考
題目
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 一定要思路清晰。