目录
codeforces 794F Leha and security system题意题解Ｃｏｄｅ
codeforces 794F Leha and security system
题目传送门
题意
给出一个长度为\(n\)的序列，有两种操作： １．将区间\([l,r]\)中每一个元素的数字\(x\)改为\(y\)。 ２．询问区间\([l,r]\)的元素之和。 一共\(q\)次操作。\((1 \leq n,q \leq 10^5)\)
题解
看起来就很可做的题目，实际上只是线段树的应用而已。我们记\(sum[i]\)表示数字\(i\)的数位和，例如\(18456645\)的\(sum[5]=10001,sum[6]=1100\)，再记\(to[i]\)表示数字\(i\)被更改成了什么数字。如果没有更改，那么\(to[i]=i\)。这样剩下的就是简单的线段树的操作了。最后需要注意的是，计算答案的时候，数字\(i\)的贡献是\(sum[i]*to[i]\)，而不是\(sum[i]*i\)，所以\(sum[0]\)也是可能做出贡献的。刚开始写的时候以为\(0\)就不会做出贡献了，然后无限的\(WA\)。。
Ｃｏｄｅ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
const int N=1e5+500;
int n,m;
int a[N];
/*==================Define Area================*/
namespace SegmentTree {
struct node {
int l,r;
ll sum[10];
int to[10];
void Reset() {memset(sum,0,sizeof sum);}
void Init() {for(int i=0;i<=9;i++) to[i]=i,sum[i]=0;}
void Print() {printf("[%d,%d] --> ",l,r);for(int i=0;i<=9;i++) printf("%lld ",sum[i]);puts("");}
}t[N<<2];
ll tmp[10];
#define ls(o) o<<1
#define rs(o) o<<1|1
void Update(int o) {
t[o].Reset();
for(int i=0;i<=9;i++) t[o].sum[t[ls(o)].to[i]]+=t[ls(o)].sum[i];
for(int i=0;i<=9;i++) t[o].sum[t[rs(o)].to[i]]+=t[rs(o)].sum[i];
}
void Pushdown(int o) {
for(int i=0;i<=9;i++) t[ls(o)].to[i]=t[o].to[t[ls(o)].to[i]];
for(int i=0;i<=9;i++) t[rs(o)].to[i]=t[o].to[t[rs(o)].to[i]];
memset(tmp,0,sizeof tmp);
for(int i=0;i<=9;i++) tmp[t[o].to[i]]+=t[o].sum[i];
for(int i=0;i<=9;i++) t[o].sum[i]=tmp[i];
for(int i=0;i<=9;i++) t[o].to[i]=i;
}
void Build(int o,int l,int r) {
t[o].l=l;t[o].r=r;t[o].Init();
if(l==r) {
int p=a[l],tmp=1;
while(p) {
int num=p;p/=10;
t[o].sum[num]+=tmp;tmp*=10;
}
return ;
}
int mid=(l+r)>>1;
Build(ls(o),l,mid);
Build(rs(o),mid+1,r);
for(int i=0;i<=9;i++) t[o].sum[i]=t[ls(o)].sum[i]+t[rs(o)].sum[i];
Update(o);
}
void Modify(int o,int l,int r,int x,int y) {
if(t[o].l>=l&&t[o].r<=r) {
for(int i=0;i<=9;i++) if(t[o].to[i]==x) t[o].to[i]=y;
return ;
}
Pushdown(o);
int mid=(t[o].l+t[o].r)>>1;
if(mid>=l) Modify(ls(o),l,r,x,y);
if(mid<r) Modify(rs(o),l,r,x,y);
Update(o);
}
ll Query(int o,int l,int r) {
if(t[o].l>=l&&t[o].r<=r) {
ll res=0;
for(int i=0;i<=9;i++) res+=(ll)t[o].sum[i]*t[o].to[i];
return res;
}
Pushdown(o);
int mid=(t[o].l+t[o].r)>>1;
ll res=0;
if(mid>=l) res+=Query(ls(o),l,r);
if(mid<r) res+=Query(rs(o),l,r);
return res;
}
void Debug(int o) {
if(!o) return ;
if(!t[o].l) return ;
Pushdown(o);Debug(ls(o));t[o].Print();Debug(rs(o));
return ;
}
}
using namespace SegmentTree;
int main() {
read(n);read(m);
for(int i=1;i<=n;i++) read(a[i]);
Build(1,1,n);
while(m--) {
int opt;
read(opt);
if(opt==1) {
int l,r,x,y;
read(l);read(r);read(x);read(y);
Modify(1,l,r,x,y);
}
else {
int l,r;
read(l);read(r);
printf("%lld\n",Query(1,l,r));
}
}
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/9561880.html
