[原创]Codeforces 794F - Leha and security system [线段树-区间更新]【数据结构】

2017-09-21 16:44:50 Tabris_ 阅读数：359

博客爬取于2020-06-14 22:39:27
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/78053974

题目链接：http://codeforces.com/problemset/problem/794/F
——————————————————————————————————————
F. Leha and security system
time limit per test2 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
Bankopolis, the city you already know, finally got a new bank opened! Unfortunately, its security system is not yet working fine… Meanwhile hacker Leha arrived in Bankopolis and decided to test the system!

Bank has n cells for clients’ money. A sequence from n numbers a1, a2, …, an describes the amount of money each client has. Leha wants to make requests to the database of the bank, finding out the total amount of money on some subsegments of the sequence and changing values of the sequence on some subsegments. Using a bug in the system, Leha can requests two types of queries to the database:

1 l r x y denoting that Leha changes each digit x to digit y in each element of sequence ai, for which l ≤ i ≤ r is holds. For example, if we change in number 11984381 digit 8 to 4, we get 11944341. It’s worth noting that Leha, in order to stay in the shadow, never changes digits in the database to 0, i.e. y ≠ 0.
2 l r denoting that Leha asks to calculate and print the sum of such elements of sequence ai, for which l ≤ i ≤ r holds.
As Leha is a white-hat hacker, he don’t want to test this vulnerability on a real database. You are to write a similar database for Leha to test.

Input
The first line of input contains two integers n and q (1 ≤ n ≤ 105, 1 ≤ q ≤ 105) denoting amount of cells in the bank and total amount of queries respectively.

The following line contains n integers a1, a2, …, an (1 ≤ ai < 109) denoting the amount of money in each cell initially. These integers do not contain leading zeros.

Each of the following q lines has one of the formats:

1 l r x y (1 ≤ l ≤ r ≤ n, 0 ≤ x ≤ 9, 1 ≤ y ≤ 9), denoting Leha asks to change each digit x on digit y for each element ai of the sequence for which l ≤ i ≤ r holds;
2 l r (1 ≤ l ≤ r ≤ n), denoting you have to calculate and print the sum of elements ai for which l ≤ i ≤ r holds.
Output
For each second type query print a single number denoting the required sum.

Examples
input
5 5
38 43 4 12 70
1 1 3 4 8
2 2 4
1 4 5 0 8
1 2 5 8 7
2 1 5
output
103
207
input
5 5
25 36 39 40 899
1 1 3 2 7
2 1 2
1 3 5 9 1
1 4 4 0 9
2 1 5
output
111
1002
Note
Let’s look at the example testcase.

Initially the sequence is [38, 43, 4, 12, 70].

After the first change each digit equal to 4 becomes 8 for each element with index in interval [1; 3]. Thus, the new sequence is [38, 83, 8, 12, 70].

The answer for the first sum’s query is the sum in the interval [2; 4], which equal 83 + 8 + 12 = 103, so the answer to this query is 103.

The sequence becomes [38, 83, 8, 12, 78] after the second change and [38, 73, 7, 12, 77] after the third.

The answer for the second sum’s query is 38 + 73 + 7 + 12 + 77 = 207.
——————————————————————————————————————
题目大意:

一个长度为n的序列 ，有两种操作，

  1. 将[l, r]上所有数中 数位为x的都改为y
  2. 求[l, r]上所有数的和

解题思路：

还是考虑直接的线段树维护，
每个节点维护10个信息，分别是数位为0~9的和，同时维护延迟标记

求和部分略，

对于数位修改，最大的问题就是考虑 如何维护lazy了，

这里维护的lazy同样有10个，lazy[i]表示的是接下来的数中数位为i的要变成数位lazy[i]

那么问题就是标记下传怎么搞了

和普通的标记下传相比 较为复杂,但也无非是把左右儿子的值先改过来 ,再把lazy合并过去,

还是看代码 比较好理解

1
2
3
4
5
6
7
8
这是对左儿子进行pushdown的
    for(int i=0;i<10;i++)vis[i]=lazy[rt<<1][i],sum2[i]=sum[rt<<1][i];  // 找两个临时变量代替左儿子的信息
    for(int i=0;i<10;i++)if(lazy[rt][i]!=i){                           //
        for(int j=0;j<10;j++)if(lazy[rt<<1][j]==i) vis[j]=lazy[rt][i]; //数位变化
        sum2[lazy[rt][i]]+=sum[rt<<1][i];                              // 变过去的就要加上值
        sum2[i]-=sum[rt<<1][i];                                        // 因为可能是变过来在变过去,所以不能直接赋0
    }
    for(int i=0;i<10;i++) sum[rt<<1][i]=sum2[i],lazy[rt<<1][i]=vis[i];

附本题代码
——————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N = 1e5+7;
/*****************************************/
LL sum[N<<2][11],sum2[11],a[N];
int lazy[N<<2][11],vis[11];

void pushdown(int rt){
    for(int i=0;i<10;i++)vis[i]=lazy[rt<<1][i],sum2[i]=sum[rt<<1][i];
    for(int i=0;i<10;i++)if(lazy[rt][i]!=i){
        for(int j=0;j<10;j++)if(lazy[rt<<1][j]==i) vis[j]=lazy[rt][i];
        sum2[lazy[rt][i]]+=sum[rt<<1][i];
        sum2[i]-=sum[rt<<1][i];
    }
    for(int i=0;i<10;i++) sum[rt<<1][i]=sum2[i],lazy[rt<<1][i]=vis[i];

    for(int i=0;i<10;i++) vis[i]=lazy[rt<<1|1][i],sum2[i]=sum[rt<<1|1][i];
    for(int i=0;i<10;i++)if(lazy[rt][i]!=i){
        for(int j=0;j<10;j++)if(lazy[rt<<1|1][j]==i) vis[j]=lazy[rt][i];
        sum2[lazy[rt][i]]+=sum[rt<<1|1][i];
        sum2[i]-=sum[rt<<1|1][i];
    }
    for(int i=0;i<10;i++) sum[rt<<1|1][i]=sum2[i],lazy[rt<<1|1][i]=vis[i];

    for(int i=0;i<10;i++) lazy[rt][i] = i;
}

void pushup(int rt){
    for(int i=0;i<10;i++) sum[rt][i]=sum[rt<<1][i]+sum[rt<<1|1][i];
}

void build(int rt,int l,int r){
    for(int i=0;i<10;i++) sum[rt][i]=0;
    for(int i=0;i<10;i++)lazy[rt][i]=i;
    if(l==r){
        for(LL t=1;a[l];a[l]/=10,t*=10)
            sum[rt][a[l]%10]+=t;
        return ;
    }
    int m = r+l >> 1;
    build(rt<<1  ,l  ,m);
    build(rt<<1|1,m+1,r);
    pushup(rt);
}

void update(int rt,int l,int r,int L,int R,int x,int y){
    if(L<=l&&r<=R){
        for(int i=0;i<10;i++)if(lazy[rt][i]==x){
            sum[rt][y]+=sum[rt][x];
            sum[rt][x]=0;
            lazy[rt][i]=y;
        }
        return ;
    }
    pushdown(rt);
    int m = r+l >> 1;
    if(L<=m) update(rt<<1  ,l  ,m,L,R,x,y);
    if(R> m) update(rt<<1|1,m+1,r,L,R,x,y);
    pushup(rt);
}

LL query(int rt,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        LL ans = 0;
        for(LL i=1;i<10;i++) ans+=sum[rt][i]*i;
        return ans;
    }
    pushdown(rt);
    int m = r+l >> 1;LL ans = 0;
    if(L<=m) ans += query(rt<<1  ,l  ,m,L,R);
    if(R> m) ans += query(rt<<1|1,m+1,r,L,R);
    pushup(rt);
    return ans;
}

int n,m;
int main(){
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        build(1,1,n);
        int op,l,r,x,y;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&op,&l,&r);
            if(1==op){
                scanf("%d%d",&x,&y);
                if(x==y) continue;
                update(1,1,n,l,r,x,y);
            }
            else printf("%lld\n",query(1,1,n,l,r));
        }
    }
    return 0;
}