Tinkoff Challenge – Final Round (Codeforces Round #414, rated, Div. 1 + Div. 2), problem: (F) Leha and security system Solution In C/C++

#include <cstdio>
#include <iostream>
#include <algorithm>
#define N 100010

using namespace std;

typedef long long ll;

int n,m;
int a[N];
struct segt{
int l,r,cd;
int f[10],lazy[10];
ll sum[10];
ll val(){
ll ret=0;
for(int i=0;i<10;i++) ret+=sum[i]*i;
return ret;
}
}T[N<<2];

inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}

inline void rea(int &x){
char c=nc(); x=0;
for(;c>’9’||c<‘0′;c=nc());for(;c>=’0’&&c<=’9’;x=x*10+c-‘0’,c=nc());
}

inline void Up(int g){
int ls=g<<1,rs=g<<1|1;
for(int i=0;i<10;i++)
T[g].sum[i]=T[ls].sum[i]+T[rs].sum[i];
}

inline void Push(int g){
ll cur[10];
for(int x=(g<<1);x<=(g<<1|1);x++){
for(int i=0;i<10;i++) cur[i]=0;
for(int i=0;i<10;i++) cur[T[g].f[i]]+=T[x].sum[i];
for(int i=0;i<10;i++) T[x].f[i]=T[g].f[T[x].f[i]];
for(int i=0;i<10;i++) T[x].sum[i]=cur[i];
}
for(int i=0;i<10;i++) T[g].f[i]=i;
}

void Build(int g,int l,int r){
T[g].l=l; T[g].r=r;
for(int i=0;i<10;i++) T[g].f[i]=i;
if(l==r){
int x=a[l];
for(int i=1,j=1;x;i++,j*=10)
T[g].sum[x%10]+=j,x/=10;
return ;
}
int mid=l+r>>1;
Build(g<<1,l,mid); Build(g<<1|1,mid+1,r);
Up(g);
}

void Modify(int g,int l,int r,int x,int y){
if(T[g].l==l&&T[g].r==r){
for(int i=0;i<10;i++)
if(T[g].f[i]==x) T[g].f[i]=y;
T[g].sum[y]+=T[g].sum[x];
T[g].sum[x]=0;
return ;
}
Push(g);
int mid=T[g].l+T[g].r>>1;
if(r<=mid) Modify(g<<1,l,r,x,y);
else if(l>mid) Modify(g<<1|1,l,r,x,y);
else Modify(g<<1,l,mid,x,y),Modify(g<<1|1,mid+1,r,x,y);
Up(g);
}

ll Query(int g,int l,int r){
if(T[g].l==l&&T[g].r==r) return T[g].val();
Push(g);
int mid=T[g].l+T[g].r>>1;
if(r<=mid) return Query(g<<1,l,r);
if(l>mid) return Query(g<<1|1,l,r);
return Query(g<<1,l,mid)+Query(g<<1|1,mid+1,r);
}

int main(){
rea(n); rea(m);
for(int i=1;i<=n;i++) rea(a[i]);
Build(1,1,n);
while(m–){
int op,l,r,x,y;
rea(op); rea(l); rea(r);
if(op==1){
rea(x); rea(y);
if(x==y) continue;
Modify(1,l,r,x,y);
}
else printf(“%I64d\n”,Query(1,l,r));
}
return 0;
}