当前位置: 首页 > news >正文

P3373 【模板】线段树 2(乘法与加法)(内附封面)

【模板】线段树 2

题目描述

如题,已知一个数列,你需要进行下面三种操作:

  • 将某区间每一个数乘上 x x x
  • 将某区间每一个数加上 x x x
  • 求出某区间每一个数的和。

输入格式

第一行包含三个整数 n , q , m n,q,m n,q,m,分别表示该数列数字的个数、操作的总个数和模数。

第二行包含 n n n 个用空格分隔的整数,其中第 i i i 个数字表示数列第 i i i 项的初始值。

接下来 q q q 行每行包含若干个整数,表示一个操作,具体如下:

操作 1 1 1: 格式:1 x y k 含义:将区间 [ x , y ] [x,y] [x,y] 内每个数乘上 k k k

操作 2 2 2: 格式:2 x y k 含义:将区间 [ x , y ] [x,y] [x,y] 内每个数加上 k k k

操作 3 3 3: 格式:3 x y 含义:输出区间 [ x , y ] [x,y] [x,y] 内每个数的和对 m m m 取模所得的结果

输出格式

输出包含若干行整数,即为所有操作 3 3 3 的结果。

样例 #1

样例输入 #1

5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4

样例输出 #1

17
2

提示

【数据范围】

对于 30 % 30\% 30% 的数据: n ≤ 8 n \le 8 n8 q ≤ 10 q \le 10 q10
对于 70 % 70\% 70% 的数据:$n \le 10^3 , , q \le 10^4$。
对于 100 % 100\% 100% 的数据: 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1n105 1 ≤ q ≤ 1 0 5 1 \le q \le 10^5 1q105

除样例外, m = 571373 m = 571373 m=571373

(数据已经过加强 _

样例说明:

故输出应为 17 17 17 2 2 2 40 m o d 38 = 2 40 \bmod 38 = 2 40mod38=2)。

大致思路

线段树模板,不过多解释,

  • 建树

首先,线段树是二叉树,因此具有二叉树的性质,其左儿子节点与右儿子节点是固定的,具体实现如下,其中, l c ( x ) lc(x) lc(x)为左儿子, r c ( x ) rc(x) rc(x)为右儿子(对应2n与2+1)

#define lc(x) (x<<1)
#define rc(x) ((x<<1)|1)

其次,线段树的建立为递归建立,最底层的节点对应的就是 a [ 1... n ] a[1...n] a[1...n]

void build(int x,int l,int r){tag_add[x]=0;tag_mul[x]=1;if(l==r){sm[x]=a[l];return;}int mid=(l+r)>>1;build(lc(x),l,mid);build(rc(x),mid+1,r);pushup(x);return;
}

s m [ x ] = s m [ l c ( x ) ] + s m [ r c ( x ) ] sm[x]=sm[lc(x)]+sm[rc(x)] sm[x]=sm[lc(x)]+sm[rc(x)]通常会被单独写做一个函数pushup

  • pushup

void pushup(int x){sm[x]=(sm[lc(x)]+sm[rc(x)])%mod;
}

区间修改与查询

单点修改与查询只需如同建树一样查找到节点修改并pushup或return即可,不过多赘述。

对于区间修改,我们需要用到 lazy_tag 对于一次修改操作我们先不全部进行修改,当火烧眉毛不得不用到这个值时再进行修改,对于一种运算使用一个tag[]数组实现。
此模板题有两种运算,因此用 tag_add 与 tag_mul 分别记录

int sm[N<<2],a[N<<2],tag_add[N<<2],tag_mul[N<<2];
  • cover

  • 两种运算,我们先乘后加
  • 对于乘法,节点 x 对应的 sm[x] 就是一段区间的和,根据乘法分配律,我们直接 s m [ x ] ∗ m u l sm[x]*mul sm[x]mul 即可,同样, tag_add也要乘mul,已有的 tag_mul 根据乘法结合律,直接 t a g . m u l [ x ] ∗ m u l tag.mul [ x ] * mul tag.mul[x]mul,记得最后取模
void cover(int x,int l,int r,int ad,int mul){sm[x]=sm[x]*mul%mod;sm[x]+=(r-l+1)*ad%mod;sm[x]%=mod;tag_mul[x]*=mul;tag_mul[x]%=mod;tag_add[x]*=mul;tag_add[x]+=ad;tag_add[x]%=mod;
}
  • pushdown

  • 实现 tag 下传,配合cover使用,分别下传到左儿子和右儿子,之后清空父节点的 lazy_tag 。
void pushdown(int x,int l,int r){int mid=(l+r)>>1;cover(lc(x),l,mid,tag_add[x],tag_mul[x]);cover(rc(x),mid+1,r,tag_add[x],tag_mul[x]);tag_add[x]=0;tag_mul[x]=1;
}
  • update

  • 关键部分
  • 实现区间加法与区间乘法,同样配合 cover,pushdown 使用。
  • 以下给出两种写法,将注释掉的内容解开并将 if (L<=mid)…两行注释即为第二种写法
void update(int x,int l,int r,int L,int R,int ad,int mul){
//	if(r<L||l>R)return;if(l>=L&&R>=r){cover(x,l,r,ad,mul);//若已被完全包含,进行一次计算return;}pushdown(x,l,r);//注意下传tagint mid=(l+r)>>1;if(L<=mid)update(lc(x),l,mid,L,R,ad,mul);//下传左儿子if(R>mid) update(rc(x),mid+1,r,L,R,ad,mul);//下传右儿子
//	update(lc(x),l,mid,L,R,ad,mul);
//	update(rc(x),mid+1,r,L,R,ad,mul);pushup(x);
}
int query(int x,int l,int r,int L,int R){
//	if(r<L||l>R)return 0;int res=0;if(l>=L&&R>=r){return sm[x];}pushdown(x,l,r);int mid=(l+r)>>1;if(L<=mid)res+=(query(lc(x),l,mid,L,R)%mod);if(R>mid) res+=(query(rc(x),mid+1,r,L,R)%mod);
//	res+=(query(lc(x),l,mid,L,R)%mod);
//	res+=(query(rc(x),mid+1,r,L,R)%mod);return res%mod;
}
int query(int x,int l,int r,int L,int R){if(r<L||l>R)return 0;if(l>=L&&R>=r){return sm[x];}pushdown(x,l,r);int mid=(l+r)>>1;return (query(lc(x),l,mid,L,R)+query(rc(x),mid+1,r,L,R))%mod;
}
真的快被线段树ex吐了

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long int
const int N=1e6+2233;
#define lc(x) (x<<1)
#define rc(x) ((x<<1)|1)
int n,m,mod;
int sm[N<<2],a[N<<2],tag_add[N<<2],tag_mul[N<<2];
void pushup(int x){sm[x]=(sm[lc(x)]+sm[rc(x)])%mod;
}
void build(int x,int l,int r){tag_add[x]=0;tag_mul[x]=1;if(l==r){sm[x]=a[l];return;}int mid=(l+r)>>1;build(lc(x),l,mid);build(rc(x),mid+1,r);pushup(x);return;
}
void cover(int x,int l,int r,int ad,int mul){sm[x]=sm[x]*mul%mod;sm[x]+=(r-l+1)*ad%mod;sm[x]%=mod;tag_mul[x]*=mul;tag_mul[x]%=mod;tag_add[x]*=mul;tag_add[x]+=ad;tag_add[x]%=mod;
}
void pushdown(int x,int l,int r){int mid=(l+r)>>1;cover(lc(x),l,mid,tag_add[x],tag_mul[x]);cover(rc(x),mid+1,r,tag_add[x],tag_mul[x]);tag_add[x]=0;tag_mul[x]=1;
}
void update(int x,int l,int r,int L,int R,int ad,int mul){
//	if(r<L||l>R)return;if(l>=L&&R>=r){cover(x,l,r,ad,mul);return;}pushdown(x,l,r);int mid=(l+r)>>1;if(L<=mid)update(lc(x),l,mid,L,R,ad,mul);if(R>mid) update(rc(x),mid+1,r,L,R,ad,mul);
//	update(lc(x),l,mid,L,R,ad,mul);
//	update(rc(x),mid+1,r,L,R,ad,mul);pushup(x);
}
int query(int x,int l,int r,int L,int R){
//	if(r<L||l>R)return 0;int res=0;if(l>=L&&R>=r){return sm[x];}pushdown(x,l,r);int mid=(l+r)>>1;if(L<=mid)res+=(query(lc(x),l,mid,L,R)%mod);if(R>mid) res+=(query(rc(x),mid+1,r,L,R)%mod);
//	res+=(query(lc(x),l,mid,L,R)%mod);
//	res+=(query(rc(x),mid+1,r,L,R)%mod);return res%mod;
}
signed main(){scanf("%lld %lld %lld",&n,&m,&mod);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}build(1,1,n);while(m--){int op,xx,yy,kk;scanf("%lld",&op);if(op==1){scanf("%lld %lld %lld",&xx,&yy,&kk);update(1,1,n,xx,yy,0,kk);}if(op==2){scanf("%lld %lld %lld",&xx,&yy,&kk);update(1,1,n,xx,yy,kk,1);}if(op==3){scanf("%lld %lld",&xx,&yy);printf("%lld\n",query(1,1,n,xx,yy));}}return 0;
}

附封面(佐仓大法好!)

请添加图片描述

相关文章:

P3373 【模板】线段树 2(乘法与加法)(内附封面)

【模板】线段树 2 题目描述 如题&#xff0c;已知一个数列&#xff0c;你需要进行下面三种操作&#xff1a; 将某区间每一个数乘上 x x x&#xff1b;将某区间每一个数加上 x x x&#xff1b;求出某区间每一个数的和。 输入格式 第一行包含三个整数 n , q , m n,q,m n,…...

实现langchain-ChatGLM API调用客户端(及未解决的问题)

langchain-ChatGLM是一个基于本地知识库的LLM对话库。其基于text2vec-large-Chinese为Embedding模型&#xff0c;ChatGLM-6B为对话大模型。原项目地址&#xff1a;https://github.com/chatchat-space/langchain-ChatGLM 对于如何本地部署ChatGLM模型&#xff0c;可以参考我之前…...

【AltWalker】模型驱动:轻松实现自动化测试用例的生成和组织执行

目录 模型驱动的自动化测试 优势 操作步骤 什么是AltWalker&#xff1f; 安装AltWalker 检查是否安装了正确的版本 牛刀小试 创建一个测试项目 运行测试 运行效果 在线模型编辑器 VScode扩展 本地部署 包含登录、选择产品、支付、退出登录的模型编写 模型效果 1…...

大数据课程E3——Flume的Sink

文章作者邮箱:yugongshiye@sina.cn 地址:广东惠州 ▲ 本章节目的 ⚪ 掌握Sink的HDFS Sink; ⚪ 掌握Sink的Logger Sink; ⚪ 掌握Sink的File Roll Sink; ⚪ 掌握Sink的Null Sink; ⚪ 掌握Sink的AVRO Sink; ⚪ 掌握Sink的Custom Sink; 一、HDFS Sink …...

如何快速做单元测试?

首先写unit test之前&#xff0c;要确认自己的测试遵循两个原则&#xff1a; 1、尽量不要干涉原来的代码。从阅读代码的体验来说&#xff0c;不要让你的测试&#xff08;哪怕是一小段if..else...的代码&#xff09;出现在你准备测试的代码中。 2、代码要只是测试某个class里面…...

不同对象的集合转换

https://blog.csdn.net/qq_42483473/article/details/128984514 import com.alibaba.fastjson.JSON;import java.util.ArrayList; import java.util.List;/*** author */ public class ObjectConversion {/*** 从List<A> copy到List<B>* param list List<B>…...

【机器学习】Gradient Descent

Gradient Descent for Linear Regression 1、梯度下降2、梯度下降算法的实现(1) 计算梯度(2) 梯度下降(3) 梯度下降的cost与迭代次数(4) 预测 3、绘图4、学习率 首先导入所需的库&#xff1a; import math, copy import numpy as np import matplotlib.pyplot as plt plt.styl…...

直播读弹幕机器人:直播弹幕采集+文字转语音(附完整代码)

目录 前言代码实现请求数据解析数据文字转语音完整代码 高级点的tk界面版 前言 直播读弹幕机器人是指能够实时读取直播平台上观众发送的弹幕&#xff0c;并将其转化为语音进行播放的机器人。这种机器人通常会使用文字转语音技术&#xff0c;将接收到的弹幕文本转为语音&#x…...

K3s vs K8s:轻量级对决 - 探索替代方案

在当今云原生应用的领域中&#xff0c;Kubernetes&#xff08;简称K8s&#xff09;已经成为了无可争议的领导者。然而&#xff0c;随着应用规模的不断增长&#xff0c;一些开发者和运维人员开始感受到了K8s的重量级特性所带来的挑战。为了解决这一问题&#xff0c;一个名为K3s的…...

dev控件gridControl,gridview中添加合计

需求&#xff1a;在合并结账查询中&#xff0c;双击每一条结账出现这次结账对应的结算明细&#xff1a; 弹出的页面包括&#xff1a;结算日期&#xff0c;ID&#xff0c;姓名&#xff0c;费别&#xff0c;预交金收入&#xff0c;结算金额&#xff0c;收据号&#xff0c;合计&a…...

SpringBoot基础认识

创建SpringBoot模块 首先需要引设置maven并引用maven环境 1.打开项目结构&#xff0c;new module&#xff0c;选择Spring Initializr&#xff0c;URL选默认&#xff1a; group填写分组如com.kdy &#xff0c; Artifact起个模块名如springboot_quickstart&#xff0c;Type选择M…...

二十三种设计模式第十九篇--命令模式

命令模式是一种行为设计模式&#xff0c;它将请求封装成一个独立的对象&#xff0c;从而允许您以参数化的方式将客户端代码与具体实现解耦。在命令模式中&#xff0c;命令对象充当调用者和接收者之间的中介。这使您能够根据需要将请求排队、记录请求日志、撤销操作等。 命令模…...

STM32基础入门学习笔记:基础知识和理论 开发环境建立

文件目录&#xff1a; 一&#xff1a;基础知识和理论 1.ARM简介 2.STM32简介 3.STM32命名规范 4.STM32内部功能* 5.STM32接口定义 二&#xff1a;开发环境建立 1.开发板简介 2.ISP程序下载 3.最小系统电路 4.KEIL的安装 5.工程简介与调试流程 6.固件库的安装 7.编…...

Qt应用开发(基础篇)——数值微调输入框QAbstractSpinBox、QSpinBox、QDoubleSpinBox

目录 一、前言 二、QAbstractSpinBox类 1、accelerated 2、acceptableInput 3、alignment 4、buttonSymbols 5、correctionMode 6、frame 7、keyboardTracking 8、readOnly 9、showGroupSeparator 10、specialValueText 11、text 12、wrapping 13、信号 二、Q…...

html | 无js二级菜单

1. 效果图 2. 代码 <meta charset"utf-8"><style> .hiddentitle{display:none;}nav ul{list-style-type: none;background-color: #001f3f;overflow:hidden; /* 父标签加这个&#xff0c;防止有浮动子元素时&#xff0c;该标签失去高度*/margin: 0;padd…...

appium的基本使用

appium的基本使用 一、appium的基本使用appium环境安装1、安装Android SDK 2、安装Appium3、安装手机模拟器4、Pycharm安装 appium-python-alicent5、连接appium和模拟器6、Python代码调用appium软件&#xff0c;appium软件在通过adb命令调用android操作系统&#xff08;模拟器…...

Dockerfile构建nginx镜像(编译安装)

Dockerfile构建nginx镜像 1、建立工作目录 [rootdocker ~]# mkdir nginx [rootdocker ~]# cd nginx/ 2、编写Dockerfile文件 [rootdocker nginx]# vim run.sh [rootdocker nginx]# vim Dockerfile #基于的基础镜像 FROM centos:7#镜像作者信息 MAINTAINER Crushlinux <…...

手机屏幕视窗机器视觉定位软硬件-康耐德

【检测目的】 手机屏幕视窗视觉定位 【效果图片】 【安装示意图】 【硬件配置】...

Databend 开源周报第 104 期

Databend 是一款现代云数仓。专为弹性和高效设计&#xff0c;为您的大规模分析需求保驾护航。自由且开源。即刻体验云服务&#xff1a;https://app.databend.cn 。 Whats On In Databend 探索 Databend 本周新进展&#xff0c;遇到更贴近你心意的 Databend 。 从 Kafka 载入数…...

用于医学图像分类的双引导的扩散网络

文章目录 DiffMIC: Dual-Guidance Diffusion Network for Medical Image Classification摘要本文方法实验结果 DiffMIC: Dual-Guidance Diffusion Network for Medical Image Classification 摘要 近年来&#xff0c;扩散概率模型在生成图像建模中表现出了显著的性能&#xf…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...