题解：P9297 [POI 2020] Licznik długu / 债务计数器

dream10 · 2025-06-01 11:27:24 · 题解

Preface

目前的两篇题解要么渐进复杂度不如我，要么常数不如我。

@happybob @Alex_Eon

Hint

两个数相加，最多进几位？

修改的本质是什么？

查询的时候除了对应位置的数值，还需要知道什么？

怎么快速计算进位？

Solution

Step 1

发现两个数相加，最多进一位。修改也不过是改 a_i+b_i，查询只需要知道比当前这一位低的数中是否进位。

于是用线段树维护这段区间的 d_i(i\in\{ 0,1\})，表示是否被进位下是不是向前进位，合并直接复合。

难度不高，详见代码。

#include<bits/stdc++.h>
using namespace std;

int n,m;
const int MAXN=100010;
int a[MAXN];
int b[MAXN];
struct Node{
    int d[2];
}t[MAXN<<2];
Node operator + (Node A,Node B){
    Node C;
    C.d[0]=B.d[A.d[0]];
    C.d[1]=B.d[A.d[1]];
    return C;
}
#define mid ((L+R)>>1)
void build(int x,int L=1,int R=n){
    if(L==R){
        t[x].d[0]=a[L]+b[L]+0>=10;
        t[x].d[1]=a[L]+b[L]+1>=10;
    }else{
        build(x<<1,L,mid);
        build(x<<1|1,mid+1,R);
        t[x]=t[x<<1]+t[x<<1|1];
    }
}
void upd(int x,int pos,int L=1,int R=n){
    if(L==R){
        t[x].d[0]=a[L]+b[L]+0>=10;
        t[x].d[1]=a[L]+b[L]+1>=10;
    }else{
        if(pos<=mid)upd(x<<1,pos,L,mid);
        else upd(x<<1|1,pos,mid+1,R);
        t[x]=t[x<<1]+t[x<<1|1];
    }
}
Node res;
void qry(int x,int l,int r,int L=1,int R=n){
    if(l<=L&&R<=r){
        res=res+t[x];
    }else{
        if(l<=mid)qry(x<<1,l,r,L,mid);
        if(r>mid)qry(x<<1|1,l,r,mid+1,R);
    }
}
#undef mid
signed main(){
    cin>>n>>m;
    for(int i=2;i<=n;++i){
        char c;cin>>c;
        a[i]=c-'0';
    }
    for(int i=2;i<=n;++i){
        char c;cin>>c;
        b[i]=c-'0';
    }
    reverse(a+2,a+n+1);
    reverse(b+2,b+n+1);
    build(1);
    char op;int i,c;
    while(m--){
        cin>>op>>i;
        ++i;
        if(op=='W'){
            cin>>c;
            a[i]=c;
            upd(1,i);
        }else if(op=='Z'){
            cin>>c;
            b[i]=c;
            upd(1,i);
        }else{
            res.d[0]=0;
            res.d[1]=0;
            qry(1,1,i-1);
            printf("%d\n",(a[i]+b[i]+res.d[0])%10);
        }
    }
    return 0;
}