BZOJ 1798 [Ahoi2009]Seq 维护序列seq 线段树

BZOJ 1798 [Ahoi2009]Seq 维护序列seq 线段树

大家好,又见面了,我是全栈君。

题意:链接

方法:线段树

解析:

俩标记sb题

更新乘的时候更新加

完了

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define N 100010
using namespace std;
typedef long long ll;
ll mul[N<<2],sum[N<<2],add[N<<2];
ll n,mod;
int q;
void pushup(int rt)
{
    sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%mod;
}
void pushdown(int rt,ll m)
{
    if(mul[rt]!=1||add[rt]!=0)
    {
        mul[rt<<1]=(mul[rt<<1]*mul[rt])%mod;
        mul[rt<<1|1]=(mul[rt<<1|1]*mul[rt])%mod;
        add[rt<<1]=(mul[rt]*add[rt<<1]+add[rt])%mod;
        add[rt<<1|1]=(mul[rt]*add[rt<<1|1]+add[rt])%mod;
        sum[rt<<1]=(sum[rt<<1]*mul[rt]+(m-(m>>1))*add[rt])%mod;
        sum[rt<<1|1]=(sum[rt<<1|1]*mul[rt]+(m>>1)*add[rt])%mod;
        mul[rt]=1,add[rt]=0;
    }
}
void build(int l,int r,int rt)
{
    mul[rt]=1,sum[rt]=0;
    if(l==r)
    {
        scanf("%I64d",&sum[rt]);
        return;
    }
    int mid=(l+r)>>1;
    build(lson),build(rson);
    pushup(rt);
}
void update_mul(int L,int R,int l,int r,int rt,ll c)
{
    if(L<=l&&r<=R)
    {
        mul[rt]=(mul[rt]*c)%mod;
        add[rt]=(add[rt]*c)%mod;
        sum[rt]=(sum[rt]*c)%mod;
        return;
    }
    pushdown(rt,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid)update_mul(L,R,lson,c);
    if(R>mid) update_mul(L,R,rson,c);
    pushup(rt);
}
void update_add(int L,int R,int l,int r,int rt,ll c)
{
    if(L<=l&&r<=R)
    {
        add[rt]=(add[rt]+c)%mod;
        sum[rt]=(sum[rt]+(r-l+1)*c)%mod;
        return;
    }
    pushdown(rt,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid)update_add(L,R,lson,c);
    if(R>mid)update_add(L,R,rson,c);
    pushup(rt);
}
ll query(int L,int R,int l,int r,int rt)
{
    ll ret=0;
    if(L<=l&&r<=R)
    {
        return sum[rt];
    }
    pushdown(rt,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid)ret=(ret+query(L,R,lson))%mod;
    if(R>mid)ret=(ret+query(L,R,rson))%mod;
    pushup(rt);
    return ret;
}
int main()
{
    scanf("%lld%lld",&n,&mod);
    build(1,n,1);
    scanf("%d",&q);
    while(q--)
    {
        int opt;scanf("%d",&opt);
        int x,y;scanf("%d%d",&x,&y);
        ll z;
        switch(opt)
        {
            case 1:scanf("%lld",&z);update_mul(x,y,1,n,1,z);break;
            case 2:scanf("%lld",&z);update_add(x,y,1,n,1,z);break;
            case 3:printf("%lld\n",query(x,y,1,n,1));break;
        }
    }
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115363.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • VBoxManage

    VBoxManageVBoxManage[-v|-version]        显示virtualbox的版本号VBoxManage-nologo              隐藏logoVBoxManage-convertSettings     允许自动转换设置文件VBoxManage-convertSettingsBackup 允许自动转换设置文件,并在转换前作备份VBoxMan

  • SQL Server中QUOTENAME函数的使用

    SQL Server中QUOTENAME函数的使用–函数QUOTENAME–功能:返回带有分隔符的Unicode 字符串,分隔符的加入可使输入的字符串成为有效的Microsoft SQL Server 2005 分隔标识符。–语法QUOTENAME ( character_string [ , quote_character ] ) –举例说明:–比如你有一个表,名字叫index–你有一个动

  • 使用libpng读写PNG图片

    使用libpng读写PNG图片libpng是一款C语言编写的比较底层的读写PNG文件的跨平台的库。借助它,你可以轻松读写PNG文件的每一行像素。因为PNG文件是经过压缩而且格式复杂的图形文件(有的PNG文件甚至像GIF文件一样带动画效果)而且PNG可以是带透明通道的真彩色图像、不带透明通道的真彩色图像、索引颜色、灰度颜色等各种格式,如果大家都自己写程序分析PNG文件就会显得很麻烦、很累。因此,通过使用libpng你就能直接…

    2022年10月22日
  • hi3516DV300_hi3531

    hi3516DV300_hi3531一.方案架构二.应用场景三.特点四.SDK包内容

  • Security身份认证之UserDetailsService[通俗易懂]

    Security身份认证之UserDetailsService[通俗易懂]之前我们采用了配置文件的方式从数据库中读取用户进行登录。虽然该方式的灵活性相较于静态账号密码的方式灵活了许多,但是将数据库的结构暴露在明显的位置上,绝对不是一个明智的做法。本文通过Java代码实现UserDetailsService接口来实现身份认证。1.1UserDetailsService在身份认证中的作用SpringSecurity中进行身份验证的是AuthenticationMan…

  • Spring Cloud的架构[通俗易懂]

    Spring Cloud的架构[通俗易懂]SpringCloud架构图Eureka用于服务注册和发现,利用了客户端的服务发现,所以它内部需要Ribbon作为客户端负载均衡。Hystrix,客户端容错保护,服务熔断、请求缓存、请求合并、依赖隔离。Feign,声明式服务调用。Bus,消息总线,配合Config仓库修改的一种Stream实现,Dashboard,Hystrix仪表盘,监控集群模式和单点模式,其中集群模式…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号