「POI 2020/2021 R1」Licznik długu 题解

算法思路

本题需要维护两个 $n-1$ 位的大整数（国内债务和国际债务），支持单点修改和查询某一位的和值。关键在于处理进位传播问题。

核心观察

进位传播规律

对于第 $i$ 位的和值 $s_i = a_i + b_i$，是否产生进位到第 $i+1$ 位取决于：

• 如果 $s_i > 9$，则产生进位
• 如果 $s_i = 9$，则可能传递来自低位的进位

关键性质

从第 $i$ 位开始向左（高位方向）的连续 $9$ 会传递进位，直到遇到第一个 $s_j > 9$ 的位。

数据结构设计

线段树维护

代码使用两个线段树：

1. segmaiorque9：标记 $s_i > 9$ 的位置

   if (num[0][i] + num[1][i] > 9)
       segmaiorque9.set(i, 1);
   

2. seg9：标记 $s_i \geq 9$ 的位置

   if (num[0][i] + num[1][i] >= 9)
       seg9.set(i, 1);
   

查询处理

二分查找连续 $9$

int l = 1, r = x, mid, ans, L = -1;
while (l <= r) {
    mid = (l + r) / 2;
    if (seg9.query(x - mid, x - 1) == mid)
        L = x - mid, l = mid + 1;
    else
        r = mid - 1;
}

这段代码找到从第 $x-1$ 位开始向左的最长连续 $\geq 9$ 的区间 $[L, x-1]$。

计算最终结果

ans = num[0][x] + num[1][x];
if (L >= 0 && segmaiorque9.query(L, x - 1))
    ans++;
cout << ans % 10 << endl;

• 如果存在连续 $\geq 9$ 的区间 $[L, x-1]$ 且该区间内至少有一个 $>9$ 的位，则第 $x$ 位需要 $+1$（进位）
• 最后输出 $\bmod 10$ 的结果

修改处理

更新数字值

num[(c == 'Z')][p] = x;

// 更新线段树标记
if (num[0][p] + num[1][p] > 9)
    segmaiorque9.set(p, 1);
else
    segmaiorque9.set(p, 0);

if (num[0][p] + num[1][p] >= 9)
    seg9.set(p, 1);
else
    seg9.set(p, 0);

复杂度分析

• 预处理：$O(n)$ 建立线段树
• 修改操作：$O(\log n)$ 更新线段树
• 查询操作：$O(\log^2 n)$（二分 + 线段树查询）

总复杂度：$O(z \log^2 n)$

算法正确性证明

进位传递规则

1. 如果 $s_i > 9$，直接产生进位
2. 如果 $s_i = 9$，可以传递来自低位的进位
3. 进位在连续 $9$ 的区间中传播，直到遇到 $s_j > 9$ 的位

二分查找的正确性

• 找到的是最长的连续 $\geq 9$ 区间
• 该区间内只要有一个 $>9$ 的位，就能保证进位传递到查询位

存储方式

// 数字从低位到高位存储（小端序）
for (int j = n - 1, p = 0; j >= 0; j--, p++) {
    num[i][p] = s[j] - '0';
}