题面
$ a,b $ 是两个非负整数，定义奇怪的加法操作$ a \oplus b $为：
- 将两个数字写成两行，并对齐最低位；
- 逐位相加，将结果直接连成一串而不是进位。
可以假设 $ a,b $ 都用前导0补齐。
更具体地，例如 $ 3248 \oplus 908 $：
现在给你一个 $n$ 位数 $c$，以及 $m$ 次更新，更新描述为：
- $x d$ —— 将 $c$ 中第 $x$ 位替换为 $d$。
注意 $c$ 在任何时候都可能会有前导0。
每次更新后，你需要输出满足 $ a \oplus b = c $ 的有序数对 $(a,b)$ 的数目。
数目会很大，所以输出其模 $998244353$ 的值即可。
输入格式
第一行两个整数 $n,m$ ($1 \leq n,m \leq 5 \times 10^5$) —— $c$ 的长度和更新次数
第二行一个字符串 $c$，包含 $n$ 位 $0$ ~ $9$。
接下来的 $m$ 行，每行两个整数 $x,d$ ($1 \leq x \leq n,0 \leq d \leq 9$) —— 更新的描述
输出格式
$m$ 个整数 —— 第 $i$ 个数表明第 $i$ 次操作后满足 $a \oplus b = c$ 的有序数对 $(a,b)$ 个数模 $998244353$ 的值
题解
思路
根据奇怪的加法操作，可以发现，我们只需要将 $c$ 划分成类似于样例图片中的样子，即可很容易地对于每一种划分方案，求出每位上可能的方案。接下来再利用乘法原理就可以算出答案。
而划分的方法非常简单，只有当连续遇到的两位数能组成 $10$~$18$ ，才会出现不同的划分方式。例如 $311416$，我们可以划分成以下几种：
3|1|1|4|1|6$4 \times 2 \times 2 \times 5 \times 2 \times 7$3|11|4|1|6$4 \times 8 \times 5 \times 2 \times 7$3|1|14|1|6$4 \times 2 \times 5 \times 2 \times 7$3|1|1|4|16$4 \times 2 \times 2 \times 5 \times 3$3|11|4|16$4 \times 8 \times 5 \times 3$3|1|14|16$4 \times 2 \times 5 \times 3$
显然，每一块数 $x$ 的方案数，如果长度为 $1$ 则为 $x+1$，为 $2$ 则为 $19-x$。
所以我们可以写一个简单的一维 dp 来解决。
for(int i=1;i<=n;++i){
dp[i] = dp[i-1]*(c[i]+1)%mod;
if(c[i-1]==1) dp[i] = (dp[i]+dp[i-2]*(9-c[i])%mod)%mod;
}
复杂度 $\Theta(nm)$ ，显然会超时。
那么如何优化呢？从本质出发，其实我们修改一位数只会影响它附近的划分方式，而这样线性递推的方式会使得我们需要花费 $\Theta(n)$ 的时间来更新，再结合 $n,m$ 范围，很显然想让我们花费 $\Theta(log n)$ 来解决。
所以上线段树。
在最简单的情况下，每个节点只需要维护当前区间内所有数划分的方案数即可，pullup时（pushup？）直接将左右节点乘起来即可。
但很显然情况并没有这么简单，除非没有 $1$。那么怎么办呢？官方题解给了我一个很厉害的思路：
对于区间 $[l,r]$ 维护四个方案数：$(l,r),[l,r),(l,r],[l,r]$ 。
而pullup的过程也很显然，直接画图便可推出。但是对于长度小于4的区间要特判一下。
struct Node {
...
ll val[4];
// y/n,y/n 分别表示左右端点取或不取
// 0 - n,n 1 - n,y
// 2 - y,n 3 - y,y
...
inline void pullup(){
if(r-l==1){
val[0]=1;
val[1]=rt->val[3];
val[2]=lt->val[3];
val[3]=lt->val[3]*rt->val[3]%mod;
}else if(r-l==2){
val[0]=lt->rt->val[3];
val[1]=lt->rt->val[3]*rt->val[3]%mod;
val[2]=lt->val[3];
val[3]=lt->val[3]*rt->val[3]%mod;
}else{
val[0] = lt->val[1]*rt->val[2];val[0]%=mod;
val[1] = lt->val[1]*rt->val[3];val[1]%=mod;
val[2] = lt->val[3]*rt->val[2];val[2]%=mod;
val[3] = lt->val[3]*rt->val[3];val[3]%=mod;
}
int l=a[lt->r],r=a[rt->l];
if(l==1){
if(this->r-this->l==1){
val[3]+=lt->val[2]*rt->val[1]*(9-r);val[3]%=mod;
}else if(this->r-this->l==2){
val[1]+=lt->val[0]*rt->val[1]*(9-r);val[1]%=mod;
val[3]+=lt->val[2]*rt->val[1]*(9-r);val[3]%=mod;
}else{
val[0]+=lt->val[0]*rt->val[0]*(9-r);val[0]%=mod;
val[1]+=lt->val[0]*rt->val[1]*(9-r);val[1]%=mod;
val[2]+=lt->val[2]*rt->val[0]*(9-r);val[2]%=mod;
val[3]+=lt->val[2]*rt->val[1]*(9-r);val[3]%=mod;
}
}
}
}
虽然很容易写，但是很长0.0
修改时直接一路向上pullup即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
char a[500050];
const int mod=998244353;
struct SegmentTree {
int l,r,mid;
ll val[4];
// 0 - n,n
// 1 - n,y
// 2 - y,n
// 3 - y,y
SegmentTree *lt,*rt;
SegmentTree(int l,int r){
this->l = l;this->r = r;
mid = (l+r)>>1;
if(l==r){
val[0]=val[1]=val[2]=1;
val[3]=a[l]+1;
return;
}
lt = new SegmentTree(l,mid);
rt = new SegmentTree(mid+1,r);
pullup();
// cerr<<"("<<l<<","<<r<<"):"<<val[0]<<";"<<val[1]<<";"<<val[2]<<";"<<val[3]<<endl;
}
inline void pullup(){
if(r-l==1){
val[0]=1;
val[1]=rt->val[3];
val[2]=lt->val[3];
val[3]=lt->val[3]*rt->val[3]%mod;
}else if(r-l==2){
val[0]=lt->rt->val[3];
val[1]=lt->rt->val[3]*rt->val[3]%mod;
val[2]=lt->val[3];
val[3]=lt->val[3]*rt->val[3]%mod;
}else{
val[0] = lt->val[1]*rt->val[2];val[0]%=mod;
val[1] = lt->val[1]*rt->val[3];val[1]%=mod;
val[2] = lt->val[3]*rt->val[2];val[2]%=mod;
val[3] = lt->val[3]*rt->val[3];val[3]%=mod;
}
int l=a[lt->r],r=a[rt->l];
if(l==1){
if(this->r-this->l==1){
val[3]+=lt->val[2]*rt->val[1]*(9-r);val[3]%=mod;
}else if(this->r-this->l==2){
val[1]+=lt->val[0]*rt->val[1]*(9-r);val[1]%=mod;
val[3]+=lt->val[2]*rt->val[1]*(9-r);val[3]%=mod;
}else{
val[0]+=lt->val[0]*rt->val[0]*(9-r);val[0]%=mod;
val[1]+=lt->val[0]*rt->val[1]*(9-r);val[1]%=mod;
val[2]+=lt->val[2]*rt->val[0]*(9-r);val[2]%=mod;
val[3]+=lt->val[2]*rt->val[1]*(9-r);val[3]%=mod;
}
}
}
inline void modify(int p,int x){
if(l==r){
val[3]=x+1;
return;
}
if(p<=mid) lt->modify(p,x);
else rt->modify(p,x);
pullup();
}
}*rt;
int main(){
scanf("%d%d\n",&n,&m);
for(int i=1;i<=n;++i){
scanf("%c",&a[i]);
a[i]-='0';
}
rt = new SegmentTree(1,n);
for(int i=1,x,y;i<=m;++i){
scanf("%d%d",&x,&y);
a[x]=y;
rt->modify(x,y);
printf("%lld\n",rt->val[3]);
}
}
（才发现pullup竟然占了近一半代码
大佬的pullup
node merge(const node &a, const node &b, int l, int r){
node c;
int na = a.len == 1 ? 0 : 1;
int nb = b.len == 1 ? 0 : 2;
c.len = a.len + b.len;
c.val[0] = mul(a.val[na], b.val[nb]);
c.val[1] = mul(a.val[na], b.val[3]);
c.val[2] = mul(a.val[3], b.val[nb]);
c.val[3] = mul(a.val[3], b.val[3]);
if (l == 1){
na = a.len == 1 ? 2 : 0;
nb = b.len == 1 ? 1 : 0;
c.val[na + nb] = add(c.val[na + nb], mul(mul(a.val[0], b.val[0]), 19 - (l * 10 + r)));
c.val[1 + na] = add(c.val[1 + na], mul(mul(a.val[0], b.val[1]), 19 - (l * 10 + r)));
c.val[2 + nb] = add(c.val[2 + nb], mul(mul(a.val[2], b.val[0]), 19 - (l * 10 + r)));
c.val[3] = add(c.val[3], mul(mul(a.val[2], b.val[1]), 19 - (l * 10 + r)));
}
return c;
}
可以发现，之前我的pullup中，第一阶段对于左子树的操作只访问了 val[1-3]，这其中 val[3] 是不用根据区间长度来进行讨论的，重点在 val[1-2]。而这里直接使用了两个变量 na,nb 用来代替1,2，特判长度为1时，左右子树真实应取的val值。
总结
对于这类在区间上多次修改、多次询问的题，可以先从不修改的情况出发，去想出一个简单的解决方法，然后再来考虑修改后造成的影响。而这种区间上的题，我们又可以在线段树上维护这一段中不同情况的多个值，以达到方便合并的目的。