【题录】数据结构杂题

zhouxianzhuo · 2025-11-16 12:01:12 · 个人记录

Lucky Numbers

题面

P12087 [RMI 2019] 好数 / Lucky Numbers

QOJ #88. Lucky Numbers

思路

考虑直接用线段树维护，每个节点维护 3 个大标记，每个大标记维护 4 个小标记，具体如下：

• 小标记：ans，begin3，end1，begin3end1。

  其中 ans 表示总合法数量，begin3 表示开头为 3 的合法数量，end1 表示结尾为 1 的合法数量，begin3end1 表示开头为 3 且结尾为 1 的合法数量。

• 大标记：less，equal，greater。

  其中 less 表示小于原序列的合法数量，equal 表示等于原序列的合法数量，greater 表示大于原序列的合法数量。

合并：

• 小标记：

  • ans\leftarrow l.ans\times r.ans-l.end1\times r.begin3
  • begin3\leftarrow l.begin3\times r.ans-l.begin3end1\times r.begin3
  • end1\leftarrow l.ans\times r.end1-l.end1\times r.begin3end1
  • begin3end1\leftarrow l.begin3\times r.end1-l.begin3end1\times r.begin3end1

• 大标记：

  • less\leftarrow l.equal\times r.less+l.less\times(r.less+r.equal+r.greater)
  • equal\leftarrow l.equal\times r.equal
  • greater\leftarrow l.equal\times r.greater+l.greater\times(r.less+r.equal+r.greater)

  其中，\times 是以小标记的合并方式将两个大标记的小标记合并，而 + 是直接将两个大标记的小标记相加。

叶子节点分类讨论后，按如上方式维护线段树即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
struct tag{
    long long ans,b3,e1,b3e1;
};
tag operator + (tag x,tag y){
    tag z;
    z.ans=(x.ans+y.ans)%mod;
    z.b3=(x.b3+y.b3)%mod;
    z.e1=(x.e1+y.e1)%mod;
    z.b3e1=(x.b3e1+y.b3e1)%mod;
    return z;
}
//两个大标记相加为将其小标记相加 
tag operator * (tag x,tag y){
    tag z;
    z.ans=(x.ans*y.ans-x.e1*y.b3%mod+mod)%mod;
    z.b3=(x.b3*y.ans-x.b3e1*y.b3%mod+mod)%mod;
    z.e1=(x.ans*y.e1-x.e1*y.b3e1%mod+mod)%mod;
    z.b3e1=(x.b3*y.e1-x.b3e1*y.b3e1%mod+mod)%mod;
    return z;
}
//两个大标记相乘为将其小标记合并 
struct node{
    tag l,e,g;
};
inline node merge(node x,node y){
    node z;
    z.l=x.e*y.l+x.l*(y.l+y.e+y.g);
    z.e=x.e*y.e;
    z.g=x.e*y.g+x.g*(y.l+y.e+y.g);
    return z;
}
//大标记的合并 
int n,q,a[100010];
node tree[400010];
inline void init(int x,int v){
    tree[x].l.ans=v;
    tree[x].e.ans=1;
    tree[x].g.ans=9-v;
    if(v<1)
    {
        tree[x].l.e1=0;
        tree[x].e.e1=0;
        tree[x].g.e1=1;
    }
    if(v==1)
    {
        tree[x].l.e1=0;
        tree[x].e.e1=1;
        tree[x].g.e1=0;
    }
    if(v>1)
    {
        tree[x].l.e1=1;
        tree[x].e.e1=0;
        tree[x].g.e1=0;
    }
    if(v<3)
    {
        tree[x].l.b3=0;
        tree[x].e.b3=0;
        tree[x].g.b3=1;
    }
    if(v==3)
    {
        tree[x].l.b3=0;
        tree[x].e.b3=1;
        tree[x].g.b3=0;
    }
    if(v>3)
    {
        tree[x].l.b3=1;
        tree[x].e.b3=0;
        tree[x].g.b3=0;
    }
    tree[x].l.b3e1=0;
    tree[x].e.b3e1=0;
    tree[x].g.b3e1=0;
}
//线段树叶子节点的分类讨论 
inline void pushup(int x){
    tree[x]=merge(tree[x*2],tree[x*2+1]);
}
void build(int l,int r,int x){
    if(l==r)
    {
        init(x,a[l]);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,x*2);
    build(mid+1,r,x*2+1);
    pushup(x);
}
void change(int l,int r,int x,int k,int v){
    if(l==r)
    {
        init(x,v);
        return;
    }
    int mid=(l+r)>>1;
    if(k<=mid)change(l,mid,x*2,k,v);
    else change(mid+1,r,x*2+1,k,v);
    pushup(x);
}
node ask(int l,int r,int x,int ll,int rr){
    if(l>=ll&&r<=rr)return tree[x];
    int mid=(l+r)>>1;
    if(rr<=mid)return ask(l,mid,x*2,ll,rr);
    if(ll>mid)return ask(mid+1,r,x*2+1,ll,rr);
    return merge(ask(l,mid,x*2,ll,rr),ask(mid+1,r,x*2+1,ll,rr));
}
//线段树维护标记 
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        char c;
        cin>>c;
        a[i]=c-'0';
    }
    build(1,n,1);
    printf("%lld\n",(tree[1].l.ans+tree[1].e.ans)%mod);
    while(q--)
    {
        int op;
        scanf("%d",&op);
        if(op==1)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            node s=ask(1,n,1,l,r);
            printf("%lld\n",(s.l.ans+s.e.ans)%mod);
        }
        else
        {
            int k,v;
            scanf("%d%d",&k,&v);
            change(1,n,1,k,v);
        }
    }
    return 0;
}