线段树-模板-区间查询-区间修改
【模板】线段树 2
传送门:https://www.luogu.com.cn/problem/P3373
题单:https://www.luogu.com.cn/training/16376#problems
题目描述
如题,已知一个数列,你需要进行下面三种操作:
- 将某区间每一个数乘上 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 n≤8, q ≤ 10 q \le 10 q≤10。
对于 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 1≤n≤105, 1 ≤ q ≤ 1 0 5 1 \le q \le 10^5 1≤q≤105。
除样例外, m = 571373 m = 571373 m=571373。
(数据已经过加强 _)
样例说明:

故输出应为 17 17 17、 2 2 2( 40 m o d 38 = 2 40 \bmod 38 = 2 40mod38=2)。
代码
#include <bits/stdc++.h>#define MAXN 100010
#define ll long longusing namespace std;int n, m, mod;
int a[MAXN];struct Segment_Tree {ll sum, add, mul;int l, r;
}s[MAXN * 4];void update(int pos) {s[pos].sum = (s[pos << 1].sum + s[pos << 1 | 1].sum) % mod;return;
}void pushdown(int pos) { //pushdown的维护s[pos << 1].sum = (s[pos << 1].sum * s[pos].mul + s[pos].add * (s[pos << 1].r - s[pos << 1].l + 1)) % mod;s[pos << 1 | 1].sum = (s[pos << 1 | 1].sum * s[pos].mul + s[pos].add * (s[pos << 1 | 1].r - s[pos << 1 | 1].l + 1)) % mod;s[pos << 1].mul = (s[pos << 1].mul * s[pos].mul) % mod;s[pos << 1 | 1].mul = (s[pos << 1 | 1].mul * s[pos].mul) % mod;s[pos << 1].add = (s[pos << 1].add * s[pos].mul + s[pos].add) % mod;s[pos << 1 | 1].add = (s[pos << 1 | 1].add * s[pos].mul + s[pos].add) % mod;s[pos].add = 0;s[pos].mul = 1;return;
}void build_tree(int pos, int l, int r) { //建树s[pos].l = l;s[pos].r = r;s[pos].mul = 1;if (l == r) {s[pos].sum = a[l] % mod;return;}int mid = (l + r) >> 1;build_tree(pos << 1, l, mid);build_tree(pos << 1 | 1, mid + 1, r);update(pos);return;
}void ChangeMul(int pos, int x, int y, int k) { //区间乘法if (x <= s[pos].l && s[pos].r <= y) {s[pos].add = (s[pos].add * k) % mod;s[pos].mul = (s[pos].mul * k) % mod;s[pos].sum = (s[pos].sum * k) % mod;return;}pushdown(pos);int mid = (s[pos].l + s[pos].r) >> 1;if (x <= mid) ChangeMul(pos << 1, x, y, k);if (y > mid) ChangeMul(pos << 1 | 1, x, y, k);update(pos);return;
}void ChangeAdd(int pos, int x, int y, int k) { //区间加法if (x <= s[pos].l && s[pos].r <= y) {s[pos].add = (s[pos].add + k) % mod;s[pos].sum = (s[pos].sum + k * (s[pos].r - s[pos].l + 1)) % mod;return;}pushdown(pos);int mid = (s[pos].l + s[pos].r) >> 1;if (x <= mid) ChangeAdd(pos << 1, x, y, k);if (y > mid) ChangeAdd(pos << 1 | 1, x, y, k);update(pos);return;
}ll AskRange(int pos, int x, int y) { //区间询问if (x <= s[pos].l && s[pos].r <= y) {return s[pos].sum;}pushdown(pos);ll val = 0;int mid = (s[pos].l + s[pos].r) >> 1;if (x <= mid) val = (val + AskRange(pos << 1, x, y)) % mod;if (y > mid) val = (val + AskRange(pos << 1 | 1, x, y)) % mod;return val;
}int main() {scanf("%d%d%d", &n, &m, &mod);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);}build_tree(1, 1, n);for (int i = 1; i <= m; i++) {int opt, x, y;scanf("%d%d%d", &opt, &x, &y);if (opt == 1) {int k;scanf("%d", &k);ChangeMul(1, x, y, k);}if (opt == 2) {int k;scanf("%d", &k);ChangeAdd(1, x, y, k);}if (opt == 3) {printf("%lld\n", AskRange(1, x, y));}}return 0;
}
相关文章:
线段树-模板-区间查询-区间修改
【模板】线段树 2 传送门:https://www.luogu.com.cn/problem/P3373 题单:https://www.luogu.com.cn/training/16376#problems 题目描述 如题,已知一个数列,你需要进行下面三种操作: 将某区间每一个数乘上 x x x&a…...
微服务架构和分布式架构的区别
微服务架构和分布式架构的区别 有:1、含义不同;2、概念层面不同;3、解决问题不同;4、部署方式不同;5、耦合度不同。其中,含义不同指微服务架构是一种将一个单一应用程序开发为一组小型服务的方法ÿ…...
Ajax-概念、Http协议、Ajax请求及其常见问题
Ajax Ajax概念Ajax优缺点HTTP协议请求报文响应报文 Ajax案例准备工作express基本使用创建一个服务器 发送AJAX请求GET请求POST请求JSON响应 Ajax请求出现的问题IE缓存问题Ajax请求超时与网络异常处理Ajax手动取消请求Ajax重复发送请求问题 Ajax概念 AJAX 全称为Asynchronous J…...
react 09之状态管理工具1 redux+ react-thunk的使用实现跨组件状态管理与异步操作
目录 react 09之状态管理工具1 redux react-thunk的使用实现跨组件状态管理与异步操作store / index.js store的入口文件index.js 在项目入口文件 引入store / actionType.js 定义action的唯一标识store / reducers / index.jsstore / actions / form.jsstore / reducers / for…...
opencv实战项目 手势识别-实现尺寸缩放效果
手势识别系列文章目录 手势识别是一种人机交互技术,通过识别人的手势动作,从而实现对计算机、智能手机、智能电视等设备的操作和控制。 1. opencv实现手部追踪(定位手部关键点) 2.opencv实战项目 实现手势跟踪并返回位置信息&…...
Netty对HPACK头部压缩的支持
前言 HTTP2终于支持对头部进行压缩传输了,Netty很早就支持HTTP2了,看下Netty对HPACK的实现源码,可以对HPACK理解的更深一下。 HpackDecoder Netty内置的编解码器Http2FrameCodec专门用来对HTTP2的各种Frame进行编解码,其中就包…...
C++:替换string中的字符
1.按照位置进行替换 string的成员函数replace可以满足这种需求,其变体有很多种,请参考官方文档,以下列举常用的两种: #include <iostream> #include <string> using namespace std;int main() {string s = "hello world";s.replace(s.begin(), s.b…...
【ChatGPT】自我救赎
ChatGPT辅助学习C之【在C中如果大数据类型转小数据类型会发生什么呢?】,今天问ChatGPT一个问题,让它解析下面这个C程序: #include <iostream> #include <cstdio> using namespace std; int main() {int a;long long b532165478…...
微信小程序(由浅到深)
文章目录 一. 项目基本配置1. 项目组成2. 常见的配置文件解析3. app.json全局的五大配置4.单个页面中的page配置5. App函数6.tabBar配置 二. 基本语法,事件,单位1. 语法2. 事件3. 单位 三. 数据响应式修改四 . 内置组件1. button2. image3. input4. 组件…...
冒泡排序 简单选择排序 插入排序 快速排序
bubblesort 两个for循环,从最右端开始一个一个逐渐有序 #include <stdio.h> #include <string.h> #include <stdlib.h>void bubble(int *arr, int len); int main(int argc, char *argv[]) {int arr[] {1, 2, 3, 4, 5, 6, 7};int len sizeof(…...
linux文件I/O之 open() 函数用法
#include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> typedef unsigned int mode_t ; int open(const char *pathname, int flags); int open(const char *pathname, int flags, mode_t mode); 函数功能 打开或创建一个文件 返回值 成功…...
用Java操作MySQL数据库
新建Maven项目 创建Maven项目 添加依赖 在pom.xml的标签里加上下面的内容 如果是MySQL 5.8那么的版本号是5.x.x, 例如5.1.49 如果是MySQL 8.0那么的版本号是8.x.x, 例如 8.0.28 <dependencies><!-- https://mvnrepository.com/artifact/mysql/mysql-connector-java …...
SpringBoot启动报错:java: 无法访问org.springframework.boot.SpringApplication
报错原因:jdk 1.8版本与SpringBoot 3.1.2版本不匹配 解决方案:将SpringBoot版本降到2系列版本(例如2.5.4)。如下图: 修改版本后切记刷新Meavn依赖 然后重新启动即可成功。如下图:...
Vue3 setup语法糖 解决富文本编辑器上传图片64位码过长问题 quill-image-extend-module
引言: 富文本编辑器传图片会解码成64位,非常长导致数据库会报错第一种方法:将数据库类型改成 mediumtext第二种办法:本文中的方法 说明,本周文所用语法糖为Vue3 setup语法,即<script setup> 思路 拦…...
百度坐标(BD09)、国测局坐标(火星坐标,GCJ02)、和WGS84坐标系之间的转换
<!DOCTYPE html> <html><head><meta charset="UTF-8"><title></title></head><body><script>/*** * 百度坐标(BD09)、国测局坐标(火星坐标,GCJ02)、和WGS84坐标系之间的转换*///定义一些常量var x_PI = …...
论文浅尝 | CI4MRC:基于因果推断去除机器阅读理解中的名字偏差
笔记整理:朱珈徵,天津大学硕士,研究方向:问答 链接:https://aclanthology.org/2023.findings-acl.812/ 动机 机器阅读理解(Machine Reading Comprehension,MRC)是根据给定的文章回答…...
【校招VIP】测试计划之黑盒测试白盒测试
考点介绍: 黑盒测试&白盒测试是大厂和三四线公司校招的必考点。黑盒是以结果说话,白盒往往需要理解实现逻辑。现在商业项目的接口测试往往以白盒为主,也就是需要测试同学自己观察和修改数据库的值进行用例的测试。 但是无论采用哪种测试方…...
学习笔记整理-JS-01-语法与变量
文章目录 一、语法与变量1. 初识JavaScript2. JavaScript的历史3. JavaScript与ECMAScript的关系4. JavaScript的体系5. JavaScript的语言风格和特性 二、语法1. JavaScript的书写位置2. 认识输出语句3. REPL环境,交互式解析器4. 变量是什么5. 重点内容 一、语法与变…...
PHP之PHPExcel
include PHPExcel.php; include PHPExcel/Writer/Excel2007.php; //或者include PHPExcel/Writer/Excel5.php; 用于输出.xls的 //创建一个excel $objPHPExcel new PHPExcel(); // 输出Excel表格到浏览器下载 header(Content-Type: application/vnd.ms-excel); header(Content-…...
Redis系列(一):深入了解Redis数据类型和底层数据结构
Redis有以下几种常用的数据类型: redis数据是如何组织的 为了实现从键到值的快速访问,Redis 使用了一个哈希表来保存所有键值对。 Redis全局哈希表(Global Hash Table)是指在Redis数据库内部用于存储所有键值对的主要数据结构。…...
Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
