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;
}

Advertisement

spot_img

How Viral Kitchen Gadgets...

📢 As an Amazon Associate, I earn from qualifying...

APTEXPO 2026 Spotlights AI-Driven...

The Future of Fashion: APTEXPO 2026 Set to Convene...

7 Reasons This Viral...

📢 As an Amazon Associate, I earn from qualifying...

Jaishankar meets senior Japanese...

In a significant step forward for Indo-Pacific diplomacy, External...

Why Viral Kitchen Gadgets...

📢 As an Amazon Associate, I earn from qualifying...

How does a raccoon...

Raccoons are ubiquitous across both rural woodlands and bustling...

How Viral Kitchen Gadgets Is Quietly Changing the Game

📢 As an Amazon Associate, I earn from qualifying purchases.After putting the Viral Kitchen Gadgets through a proper 30-day real-world test, I can tell...

APTEXPO 2026 Spotlights AI-Driven Supply Chains, Sustainable Materials, and Asian Fashion Brands

The Future of Fashion: APTEXPO 2026 Set to Convene in SingaporeThe global textile and apparel industry is standing at the precipice of a monumental...

7 Reasons This Viral Kitchen Gadgets Is Worth Every Single Penny

📢 As an Amazon Associate, I earn from qualifying purchases.If you had told me six months ago that a single purchase would change how...

Jaishankar meets senior Japanese leaders; discusses deeper strategic, economic ties

In a significant step forward for Indo-Pacific diplomacy, External Affairs Minister S. Jaishankar met with senior Japanese leaders in Tokyo to deliberate on enhancing...

Why Viral Kitchen Gadgets Is Currently Breaking the Internet

📢 As an Amazon Associate, I earn from qualifying purchases.I stumbled across this while desperately trying to fix a recurring problem in my routine....

How does a raccoon act with rabies?

Raccoons are ubiquitous across both rural woodlands and bustling suburban neighborhoods. While these masked foragers are generally cautious and nocturnal, their close proximity to...

We Tested Viral Kitchen Gadgets Here Is What You Must Know

📢 As an Amazon Associate, I earn from qualifying purchases.There comes a point when you realise that tolerating a frustrating situation is costing you...

Brad Pitt and Ines De Ramon walk ‘The Further Mis-Adventures of Cliff Booth’ premiere red carpet hand in hand

Hollywood royalty made a stylish statement in Los Angeles as Oscar-winning actor Brad Pitt arrived hand in hand with his partner, jewelry designer Inés...

Why Viral Kitchen Gadgets Is Currently Breaking the Internet

📢 As an Amazon Associate, I earn from qualifying purchases.Most products in this category disappoint within weeks. Cheap materials, vague instructions, and results that...