P15233 浣熊的蒲公英

· · 题解

主要思想

由于 * 优先级高，表达式可以看作若干个乘法块，块之间用 + 或 - 连接。每次修改只会影响一个块，把 * 改为 + 或 - 会拆分块。这样修改时只需要更新被影响的块，不需要重新计算整个表达式。

实现

为了方便处理，先处理出每个数字和中间的符号。

类比链表和并查集的思想，记录每个块的开头位置和下一个数字，处理出每个块的乘积和符号。

对于修改，就是把一个块拆成两个。计算出两个块的数值，像链表一样修改前后两个块的指针指向的位置。

代码（注释版）

#include <bits/stdc++.h>
using namespace std;
#define int long long  // 不开 long long 见祖宗

const int MAXN = 100005, MOD = 1e9 + 7;

string expr;  // 表达式
int n;        // 数字个数
int tot;      // 当前表达式的总值
int a[MAXN];  // 数字数组
int bst[MAXN];    // 数字 i 所在乘法块的起点
int bval[MAXN];   // 以 i 为起点的块的乘积
int nex[MAXN];    // 同一个乘法块中，i 的下一个数字
char ope[MAXN];   // a[i] 和 a[i+1] 之间的运算符
char bsg[MAXN];   // 以 i 为起点的块的符号

// 解析表达式，将字符串转换为数字数组和运算符数组
void parse(){
    n = 0;
    for(int i = 0; i < expr.size();){
        if(isdigit(expr[i])){
            int num = 0;
            // 读数字
            while(i < expr.size() && isdigit(expr[i]))
                num = (num * 10 + expr[i] - '0') % MOD, ++ i;
            a[++ n] = num;
        }
        else{
            // 存储运算符
            if(n > 0) ope[n] = expr[i];
            ++ i;
        }
    }
}

// 初始化，构建乘法块，计算块乘积，计算初始总值
void init(){
    // 每个数字单独成一个块
    for(int i = 1; i <= n; ++ i)
        bst[i] = i;

    // 连接乘法块
    for(int i = 1; i < n; ++ i)
        if(ope[i] == '*')
            if(bst[i] != bst[i + 1]){
                // 合并块
                for(int j = bst[i + 1]; j <= n && bst[j] == bst[i + 1]; ++ j)
                    bst[j] = bst[i];
                nex[i] = i + 1;  // 记录 i 和 i+1 在同一个乘法块中
            }

    // 计算每个块的乘积
    for(int i = 1; i <= n; ++ i)
        if(bst[i] == i){  // i 是块的起点
            int j = i;
            bval[i] = 1;
            // 遍历块中的所有数字，计算乘积
            while(j <= n && bst[j] == i){
                bval[i] = (bval[i] * a[j]) % MOD;
                if(nex[j] != 0) j = nex[j];  // 跳到块中的下一个数字
                else break;
            }
        }

    // 设置每个块的符号
    bsg[1] = '+';  // 第一个块是正号
    for(int i = 2; i <= n; ++ i)
        if(bst[i] == i)  // i 是新块的起点
            bsg[i] = ope[i - 1];  // 块的符号是它前面的运算符

    // 计算初始总值
    tot = 0;
    for(int i = 1; i <= n; ++ i)
        if(bst[i] == i){
            if(bsg[i] == '+')
                tot = (tot + bval[i]) % MOD;
            else
                tot = (tot - bval[i] + MOD) % MOD;
        }
}

// 修改操作
void update(int k, char c){
    if(ope[k] != '*' || c == '*') return;

    int s1 = bst[k];  // 原块的起点
    int ed = k;       // 原块的终点
    // 找到原块的终点（沿着链表走到最后）
    while(nex[ed] != 0) ed = nex[ed];

    // 从总值中移除原块的贡献
    if(bsg[s1] == '+')
        tot = (tot - bval[s1] + MOD) % MOD;
    else
        tot = (tot + bval[s1]) % MOD;

    // 计算拆分后的左块乘积（从 s1 到 k）
    int lval = a[s1] % MOD, now = s1;
    // 沿着链表走到 k
    while(now != k && nex[now] != 0){
        now = nex[now];
        lval = (lval * a[now]) % MOD;
    }

    // 计算拆分后的右块乘积（从 k+1 到 ed）
    int rval = a[k + 1] % MOD; 
    now = k + 1;
    // 沿着链表走到 ed
    while(now != ed && nex[now] != 0){
        now = nex[now];
        rval = (rval * a[now]) % MOD;
    }

    // 断开乘法连接（k 和 k+1 不再属于同一个块）
    nex[k] = 0;

    // 创建新块（k+1 成为新块的起点）
    int start2 = k + 1;
    bst[start2] = start2;
    now = start2;
    // 更新所有属于新块的数字的起点
    while(now <= ed){
        bst[now] = start2;
        if(nex[now] != 0) now = nex[now];
        else break;
    }

    // 更新两个新块的乘积
    bval[s1] = lval;
    bval[start2] = rval;

    // 更新运算符和块符号
    ope[k] = c;
    bsg[start2] = c;

    // 将两个新块的贡献加入总值
    if(bsg[s1] == '+')
        tot = (tot + lval) % MOD;
    else
        tot = (tot - lval + MOD) % MOD;

    if(c == '+')
        tot = (tot + rval) % MOD;
    else
        tot = (tot - rval + MOD) % MOD;

    cout << tot << "\n";
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> expr;
    parse();
    init();
    cout << tot << "\n";

    int q;
    cin >> q;
    while(q --){
        int k; char c;
        cin >> k >> c;
        update(k, c);
    }

    return 0;
}