目录

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 
    
     using namespace std;typedef long long ll;bool Finish_read;template
     
      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
      
       inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}template
       
        inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}template
        
         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%10;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
         
          =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