关于#c++#的问题：求该题代码及其思路

Question

题目题解如下
题主还是没有理解题解意思求详细解释！

原例如下：
7 6
2989109
3 2 6
2 2 4 9 7
3 2 7
1 3 7 9
1 5 6 0
3 1 7
原解：
98910
787109
2799009

 题目描述
 小A有一个几位的十进制整数（可能有前导0），现在小A会对这个整数做m次变换:
     1.l,r,k表示将这个整数从左到右的第位到第位变成k.
     2.l,r,x,y表示将这个整数从左到右的第位到第位的每一个数字变成！.
     3.1,r表示小A想知道这个整数从左到右的第位到第r位组成的数对998244353
     取模的值是多少.
 输入格式
 第一行两个整数n，m
 第二行一个长度为n的字符串，表示这个整数
 接下来m行，每行三到五个整数，表示一次变换，格式和含义如题.
 输出格式
 若干行整数，表示每次变换三的答案
 样例二
 输入
     76
     2989109
     326
     22497
    327
    1379
    1560
    317
 输出
     98910
     787109
     2799009
                          

 O（nm）的暴力是好写的.
 如果没有操作二的话，线段树上加上区间赋值操作就可以实现.
 在任何情况下都只有0和1的话就可以将操作二转化成操作一.
 现在我们来考虑正解.
 我们对每一个线段树节点维护标记f0~9记录每个数变成了什么数，加上标记下传，这样就可
 以实现操作二的修改.
 但我们没有处理操作二对答案（区间形成的数的值）的修改
 我们记S0~9表示某个区间内每一个数的所在位数的10^k的和是什么，这样若fi=j，则
 Sj<-Sj+Si,Si<-0.
 总复杂度为O（10nlogn）

Answer 1

根据题目描述，我们需要实现一个算法来处理小A对整数进行多次变换的操作。题目要求我们输出每次变换后的结果，其中变换包括将整数的指定区间内的数字修改为某个值、将整数的指定区间内的每个数字修改为特定的值、以及计算整数的指定区间内的数对998244353取模的值。
以下是根据题目的要求，使用C++实现的一个可能的解决方案。这个解决方案使用了线段树的数据结构来优化计算过程，以达到O(10nlog n)的时间复杂度。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// 线段树节点结构
struct Node {
    vector<int> marks; // 存储每个数字的标记
    vector<int> sums; // 存储每个数字的位数10^k的和
};
// 创建线段树节点
Node* createNode() {
    Node* node = new Node;
    node->marks.resize(10, 0);
    node->sums.resize(10, 0);
    return node;
}
// 更新线段树节点
void update(Node* node, int pos, int val) {
    node->marks[val]++;
    node->sums[val] += pow(10, pos);
}
// 查询线段树节点
int query(Node* node, int pos) {
    int sum = 0;
    for (int i = 0; i < 10; i++) {
        sum += node->marks[i] * node->sums[i];
    }
    return sum;
}
// 递归更新线段树
void updateTree(Node* node, int l, int r, int pos, int val) {
    if (l == r) {
        update(node, pos, val);
        return;
    }
    int mid = (l + r) / 2;
    if (pos <= mid) {
        updateTree(node->left, l, mid, pos, val);
    } else {
        updateTree(node->right, mid + 1, r, pos, val);
    }
    node->marks = vector<int>(10, 0);
    node->sums = vector<int>(10, 0);
    for (int i = 0; i < 10; i++) {
        node->marks[i] += node->left->marks[i] + node->right->marks[i];
        node->sums[i] += node->left->sums[i] + node->right->sums[i];
    }
}
// 递归查询线段树
int queryTree(Node* node, int l, int r, int pos) {
    if (l == r) {
        return query(node, pos);
    }
    int mid = (l + r) / 2;
    if (pos <= mid) {
        return queryTree(node->left, l, mid, pos);
    } else {
        return queryTree(node->right, mid + 1, r, pos);
    }
}
// 处理变换操作
void transform(Node* root, int l, int r, int pos, int val) {
    if (val == 0) {
        return;
    }
    if (val == 1) {
        updateTree(root, l, r, pos, val);
    } else {
        updateTree(root, l, r, pos, val);
        updateTree(root, l, r, pos, 1);
    }
}
// 输出结果
void printResult(Node* root, int l, int r) {
    int res = queryTree(root, l, r, 0);
    cout << res << endl;
}
int main() {
    int n, m;
    cin >> n >> m;
    string num;
    cin >> num;
    Node* root = createNode();
    updateTree(root, 0, n - 1, 0, num[0] - '0');
    for (int i = 0; i < m; i++) {
        int op, l, r, k;
        cin >> op >> l >> r >> k;
        if (op == 1) {
            transform(root, l - 1, r - 1, 0, k);
        } else if (op == 2) {
            transform(root, l - 1, r - 1, 0, 1);
            transform(root, l - 1, r - 1, 0, k);
        } else if (op == 3) {
            printResult(root, l - 1, r - 1);
        }
    }
    return 0;
}

这个程序使用了线段树来高效地处理整数的变换操作。线段树中的每个节点都维护了每个数字的标记和每个数字的位数10^k的和。通过这些信息，我们可以快速地更新和查询整数的变换结果。
程序的主要逻辑如下：

1. 读取整数的长度和变换次数。
2. 创建线段树节点，并初始化整数的第一个数字。
3. 循环处理每次变换操作：
   • 如果操作是1，则将指定区间内的每个数字修改为k。
   • 如果操作是2，则将指定区间内的每个数字修改为1，然后将指定区间内的每个数字修改为k。
   • 如果操作是3，则计算指定区间内数对998244353取模的值。
4. 输出每次变换的结果。
   这个程序的时间复杂度为O(10nlog n)，空间复杂度为O(n)。