首页 > 其他分享 >AT_abl_e Replace Digits 题解

AT_abl_e Replace Digits 题解

时间:2024-08-05 19:28:43浏览次数:14  
标签:Digits rt lazy 题解 ll abl tree len rson

题目传送门

前置知识

线段树

解法

需要维护区间信息,考虑使用线段树维护。

预处理出 \(\overline{xx \dots x}\),其中 \(x \in \{1,2,3,4,5,6,7,8,9 \}\),便于区间赋值。

然后就是普通的线段树板子了。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
const ll p=998244353;
ll mi[200010],num[12][200010];
struct SMT
{
    struct SegmentTree
    {
        ll l,r,len,sum,lazy;
    }tree[800010];
    ll lson(ll x)
    {
        return x*2;
    }
    ll rson(ll x)
    {
        return x*2+1;
    }
    void pushup(ll rt)
    {
        tree[rt].len=tree[lson(rt)].len+tree[rson(rt)].len;
        tree[rt].sum=(tree[lson(rt)].sum*mi[tree[rson(rt)].len]+tree[rson(rt)].sum)%p;
    }
    void build(ll rt,ll l,ll r)
    {
        tree[rt].l=l;
        tree[rt].r=r;
        tree[rt].lazy=0;
        if(l==r)
        {
            tree[rt].len=tree[rt].sum=1;
            return;
        }
        ll mid=(tree[rt].l+tree[rt].r)/2;
        build(lson(rt),l,mid);
        build(rson(rt),mid+1,r);
        pushup(rt);
    }
    void pushdown(ll rt)
    {
        if(tree[rt].lazy!=0)
        {
            tree[lson(rt)].lazy=tree[rt].lazy;
            tree[lson(rt)].sum=num[tree[rt].lazy][tree[lson(rt)].len];
            tree[rson(rt)].lazy=tree[rt].lazy;
            tree[rson(rt)].sum=num[tree[rt].lazy][tree[rson(rt)].len];
            tree[rt].lazy=0;
        }
    }
    void update(ll rt,ll x,ll y,ll val)
    {
        if(x<=tree[rt].l&&tree[rt].r<=y)
        {
            tree[rt].lazy=val;
            tree[rt].sum=num[val][tree[rt].len];
            return;
        }
        pushdown(rt);
        ll mid=(tree[rt].l+tree[rt].r)/2;
        if(x<=mid)
        {
            update(lson(rt),x,y,val);
        }
        if(y>mid)
        {
            update(rson(rt),x,y,val);
        }
        pushup(rt);
    }
    pair<ll,ll> query(ll rt,ll x,ll y)
    {
        if(x<=tree[rt].l&&tree[rt].r<=y)
        {
            return make_pair(tree[rt].sum,tree[rt].len);
        }
        pushdown(rt);//以下部分在本题中显多此一举
        ll mid=(tree[rt].l+tree[rt].r)/2;
        pair<ll,ll>lp=make_pair(0,0),rq=make_pair(0,0);
        if(x<=mid)
        {
            lp=query(lson(rt),x,y);
        }
        if(y>mid)
        {
            rq=query(rson(rt),x,y);
        }
        return make_pair((lp.first*mi[rq.second]%p+rq.first)%p,lp.second+rq.second);
    }
}T;
int main()
{       
    ll n,q,l,r,x,i,j;
    cin>>n>>q;
    mi[0]=1;
    for(i=1;i<=n;i++)
    {
        mi[i]=mi[i-1]*10%p;
        for(j=1;j<=9;j++)
        {
            num[j][i]=(num[j][i-1]*10+j)%p;
        }
    }
    T.build(1,1,n);
    for(i=1;i<=q;i++)
    {
        cin>>l>>r>>x;
        T.update(1,l,r,x);
        cout<<T.query(1,1,n).first<<endl;
    }
    return 0;
}

标签:Digits,rt,lazy,题解,ll,abl,tree,len,rson
From: https://www.cnblogs.com/The-Shadow-Dragon/p/18343910

相关文章

  • AGC027C 题解
    注意到如果可以构造出所有由\(\texttt{A}\)和\(\texttt{B}\)组成的字符串,那么在图上游走的路径必须成环,并且的环上的每一个点都必须同时有一个\(\texttt{A}\)邻居和\(\texttt{B}\)邻居。于是可以考虑把点拆分为入点和出点,相邻两个点为\(\texttt{AA},\texttt{BB}\)的,从......
  • npm下载包时报错 Unexpected token ‘.‘问题解决
    项目场景:项目需要使用node18.12.0以上版本的,但是npm下载显示异常问题描述当通过nvm切换nodejs版本为16以上时,npminstall[package]报错:Unexpectedtoken'.'原因分析:提示:该问题不是npm的问题,也不是nodejs的问题,是nvm-windows的问题我是通过nvm-windows已经更新版本......
  • WPF WriteableBitmap通过GDI+绘制帮助类
    代码:publicclassWriteableBitmapGraphic:IDisposable{publicWriteableBitmapSource{get;privateset;}publicSystem.Drawing.Bitmapbitmap{get;privateset;}publicintDataLength{get;privateset;}publ......
  • AI绘画最强SD(Stable Diffusion)玩法实操教学案例及商业变现项目分享
    AI绘画现在越来越火爆了,很多人无论大人小孩都在玩,还有的很多电商老板也在使用辅助生成产品主图和详情页,可以说是非常的实用。而其中最让人追捧和好评的就是SD(StableDiffusion)这款AI绘图软件了,StableDiffusion是一款基于深度学习的图像生成工具,它可以根据文本描述生成高质......
  • 《数据结构习题解析与实验指导_李冬梅,张琪编著》总结出的大纲
        下面大纲为《数据结构习题解析与实验指导_李冬梅,张琪编著》总结出的大纲,可装13学习下:          ......
  • Codeforces Round 963 (Div. 2) D题解
    CodeforcesRound963D题目描述给定两个正整数n和k以及另一个由n个整数组成的数组a。在一次操作中,可以选择a中大小为k的任意一个子数组,然后将其从数组中删除,而不改变其他元素的顺序。更正式地说,假设(l,r)是对子数组a[l],a[l+1],...,a[r]的操作,使得r-l+1......
  • leetcode200. 岛屿数量C++题解,精美图例和流程图,一题带你弄懂图的dfs遍历算法
    leetcode200.岛屿数量给你一个由‘1’(陆地)和‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外,你可以假设该网格的四条边均被水包围。示例1:输入:grid=[[“1”,“1”,“1”,......
  • [POI2015] POD 题解
    前言题目链接:洛谷。题意简述长度为\(n\)的一串项链,每颗珠子是\(k\)种颜色之一。第\(i\)颗与第\(i-1,i+1\)颗珠子相邻,第\(n\)颗与第\(1\)颗也相邻。切两刀,把项链断成两条链。要求每种颜色的珠子只能出现在其中一条链中。求方案数量(保证至少存在一种),以及切成的两段......
  • CF1993C Light Switches 题解
    CF1993CLightSwitches题解题目大意有\(n\)盏灯,第\(i\)盏灯亮着的时间为\([a_i+bk,a_i+(b+1)k-1]\),其中\(k\)为给定常数,\(b\)为任意非负偶数。求一个最小的\(t\),使得在时间\(t\)所有灯都是亮着的。Solve令\(m=2k\),显然所有灯的开关状态以\(m\)为周期,所以我们......
  • P5086 的题解
    (一)将输入的四个数差分得到三个值,这三个值相同的两个坐标符合条件。用map存储记录这三个值的结构体,然后用vector存储下标。(二)AC代码。#include<bits/stdc++.h>#definedbdouble#definepbpush_back#definefifirst#definesesecond#definemkpmake_pair#defin......