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

A Simple Problem with Integers(线段树)

目录

描述

输入

输出

样例输入 

样例输出 

思路

建树 

第一次错误解法(正确解法在下面,可跳过这一步)

正确解法

code 


描述

You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

输入

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of AaAa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of AaAa+1, ... , Ab.

输出

You need to answer all Q commands in order. One answer in a line.

样例输入 

10 5
C 3 6 3
Q 2 4

样例输出 

9
15

思路

不要看这题全英文,但这题就是属于线段树模版题,基本做法是一样的

建树 

第一次错误解法(正确解法在下面,可跳过这一步)

树没有更新成功,id=10,id=11理论上是要继续更新他们的sum值,但我的错误代码没有更新

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
const int N = 100010;
#define ll long long
ll nums[N];
struct Tree {int l, r;ll sum;ll tag;
}tree[N << 2];
void pushup(int u) {tree[u].sum = tree[u << 1].sum + tree[u << 1 | 1].sum;
}
void build(int l, int r, int u) {if (l == r) tree[u] = { l,r,nums[l] };//要与结构体Tree一一对应 else {tree[u] = { l,r };int mid = (l + r) >> 1;build(l, mid, u << 1);build(mid + 1, r, u << 1 | 1);pushup(u);}
}
ll query(int L, int R, int u) {int l = tree[u].l, r = tree[u].r;if (l >= L && r <= R)return tree[u].sum;int mid = (l + r) >> 1;ll sum = 0;if (L <= mid) sum += query(L, R, u << 1);if (R > mid) sum += query(L, R, u << 1 | 1);return sum;
}
void pushdown(int u, int ln, int rn) {if (tree[u].tag) {tree[u << 1].tag += tree[u].tag;tree[u << 1 | 1].tag += tree[u].tag;tree[u << 1].sum += tree[u].tag * ln;tree[u << 1 | 1].sum += tree[u].tag * rn;tree[u].tag = 0;}
}
void updatespan(int L, int R, int value, int u) {int l = tree[u].l, r = tree[u].r;int mid = (l + r) >> 1;if (l >= L && r <= R) {tree[u].tag += value;tree[u].sum += value * (r - l + 1);return;}pushdown(u, mid - l + 1, r - mid);if (L <= mid) updatespan(L, R, value, u << 1);if (R > mid) updatespan(L, R, value, u << 1 | 1);pushup(u);
}
int main()
{int n, q;while (scanf("%d%d", &n, &q) != EOF) {for (int i = 1; i <= n; i++) scanf("%lld", &nums[i]);build(1, n, 1);while (q--) {string cz;int op1, op2;cin >> cz;if (cz == "C") {int val;scanf("%d%d%d", &op1, &op2, &val);updatespan(op1, op2, val, 1);}else {scanf("%d%d", &op1, &op2);printf("%lld\n", query(op1, op2, 1));}}}return 0;
}

正确解法

关键在于updatespan函数中,if语句中我没有继续pushdown导致错误

  

code 

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
const int N = 100010;
#define ll long long
ll nums[N];
struct Tree {int l, r;ll sum;ll tag;
}tree[N << 2];
void pushup(int u) {tree[u].sum = tree[u << 1].sum + tree[u << 1 | 1].sum;
}
void build(int l, int r, int u) {if (l == r) {tree[u] = { l,r,nums[l] };//要与结构体Tree一一对应 else {tree[u] = { l,r };int mid = (l + r) >> 1;build(l, mid, u << 1);build(mid + 1, r, u << 1 | 1);pushup(u);}
}
ll query(int L, int R, int u) {int l = tree[u].l, r = tree[u].r;if (l >= L && r <= R)return tree[u].sum;int mid = (l + r) >> 1;ll sum = 0;if (L <= mid) sum += query(L, R, u << 1);if (R > mid) sum += query(L, R, u << 1 | 1);return sum;
}
void pushdown(int u, int ln, int rn) {if (tree[u].tag) {tree[u << 1].tag += tree[u].tag;tree[u << 1 | 1].tag += tree[u].tag;tree[u << 1].sum += tree[u].tag * ln;tree[u << 1 | 1].sum += tree[u].tag * rn;tree[u].tag = 0;}
}
void updatespan(int L, int R, int value, int u) {int l = tree[u].l, r = tree[u].r;int mid = (l + r) >> 1;if (l >= L && r <= R) {tree[u].tag += value;tree[u].sum += value * (r - l + 1);pushdown(u, mid - l + 1, r - mid);//关键return;}pushdown(u, mid - l + 1, r - mid);if (L <= mid) updatespan(L, R, value, u << 1);if (R > mid) updatespan(L, R, value, u << 1 | 1);pushup(u);
}
int main()
{int n, q;while (scanf("%d%d", &n, &q) != EOF) {for (int i = 1; i <= n; i++) scanf("%lld", &nums[i]);build(1, n, 1);while (q--) {string cz;int op1, op2;cin >> cz;if (cz == "C") {int val;scanf("%d%d%d", &op1, &op2, &val);updatespan(op1, op2, val, 1);}else {scanf("%d%d", &op1, &op2);printf("%lld\n", query(op1, op2, 1));}}}return 0;
}

相关文章:

A Simple Problem with Integers(线段树)

目录 描述 输入 输出 样例输入 样例输出 思路 建树 第一次错误解法&#xff08;正确解法在下面&#xff0c;可跳过这一步&#xff09; 正确解法 code 描述 You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of …...

单元测试(UT)用例简介

单元测试&#xff08;Unit Testing, UT&#xff09;用例是一系列预先设计好的、针对软件最小可测试单元的测试场景。每一个单元测试用例都是为了验证一个独立代码单元&#xff08;如函数、方法、类&#xff09;的行为是否符合预期。这些用例通常包含以下几个关键组成部分&#…...

Java通过反射机制获取类对象下的属性值

目录 以类USER为例&#xff1a; 使用Java的反射机制获取Column的name为“user_name”的类属性值 以类USER为例&#xff1a; import lombok.Data; import javax.persistence.*; import java.io.Serializable;Data Table(name "user_info") public class User imple…...

IDEA插件开发-File -> New->Project中添加一个myOptions

写一个IDEA插件&#xff0c;在IDEA的File -> New -> Project 中添加一个选项myOptions &#xff0c;点击myOptions 后弹出一个提示对话框:被点击了 为了在IntelliJ IDEA中创建一个插件&#xff0c;您需要遵循一系列的步骤来开发和集成您的功能。下面是一个简化的指南&am…...

海量数据处理项目-账号微服务和流量包数据库表+索引规范(下)

海量数据处理项目-账号微服务和流量包数据库表索引规范&#xff08;下&#xff09; 第2集 账号微服务和流量包数据库表索引规范讲解《下》 简介&#xff1a;账号微服务和流量包数据库表索引规范讲解 账号和流量包的关系&#xff1a;一对多traffic流量包表思考点 海量数据下每…...

Nodejs 16与 gitbook搭建属于你自己的书本网站-第一篇

最近想重新搭建一个网站来存放自己的相关知识点&#xff0c;并向网络公开&#xff0c;有个hexo博客其实也不错的&#xff0c;但是总感觉hexo很多花里胡哨的玩意&#xff0c;导致挂载的博客异常卡&#xff0c;这样反而不利于我自己回顾博客了&#xff0c;于是我就开始钻研这个鬼…...

服务器被CC攻击之后怎么办?

1.取消域名绑定取消域名绑定后Web服务器的CPU能够马上恢复正常状态&#xff0c;通过IP进行访问连接一切正常。但是不足之处也很明显&#xff0c;取消或者更改域名对于别人的访问带来了不变&#xff0c;另外&#xff0c;对于针对IP的CC攻击它是无效的&#xff0c;就算更换域名攻…...

pygame通过重心坐标 用纹理填充三角形

texture_x int(alpha * texture_image.get_width()) texture_y int(beta * texture_image.get_height())为什么没有gama 2024/3/30 15:45:52 在使用重心坐标进行纹理映射时&#xff0c;通常是通过计算 alpha 和 beta 来确定纹理图片上的对应位置&#xff0c;而 gamma 通常是…...

Leetcode 611. 有效三角形的个数

给定一个包含非负整数的数组 nums &#xff0c;返回其中可以组成三角形三条边的三元组个数。 示例 1: 输入: nums [2,2,3,4] 输出: 3 解释:有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3 示例 2: 输入: nums [4,2,3,4] 输出: 4 提示: 1 < nums.len…...

Openfeign

Openfeign 相关扩展 在 2020 以前的 SpringCloud 采用 Ribbon 作为负载均衡&#xff0c;但是 2020 年之后&#xff0c;SpringCloud 吧 Ribbon 移除了&#xff0c;而是使用自己编写的 LoadBalancer 替代. 因此&#xff0c;如果在没有加入 LoadBalancer 依赖的情况下&#xff0c…...

五、基于KubeAdm搭建多节点K8S集群

如需查阅上一步骤,请点击下面链接:四、戴尔R630本地服务器Linux Centos7.9系统安装docker-ce-20.10.10-3.el7版本-CSDN博客文章浏览阅读727次,点赞12次,收藏13次。1、准备工作3、Linux Centos7.9系统的iDRAC远程管理、网络设置、SecureCRT远程登录终端、企业级静态ip地址配…...

PC电脑技巧[笔记本通过网线访问设备CMW500]

笔记本局域网访问设备 现在我有一台CMW500,我要用笔记本去访问它,但是我发现没有路由器就是不能够访问,通过网线连接设备就是ping不通: 这里设置TCP/IPv4的IP地址如下,这时候就可以pin通了:...

【接口自动化测试框架】YAML管理接口框架配置的最佳实践

管理接口框架配置是构建强大的接口测试框架的关键一环。良好的配置管理可以提高测试效率、可维护性和可扩展性。在本文中&#xff0c;我们将重点介绍使用YAML&#xff08;YAML Ain’t Markup Language&#xff09;来管理接口框架配置的最佳实践&#xff0c;并通过实例演示其用法…...

【进程OI】基本文件操作的系统调用

文章目录 前言open参数flags参数mode writereadclose 前言 当用户想要向磁盘中的文件读写数据&#xff0c;就必须要得到操作系统的允许。同样&#xff0c;操作系统为了能让用户去对文件进行打开、读写、关闭等操作&#xff0c;向上提供了相应的系统调用的接口。C、JAVA、C等语…...

Ubuntu20.04 server系统部署安装(VMware上)和初始化配置

Ubuntu20.04 server部署安装&#xff08;VMware上&#xff09;和初始化配置 一、Ubuntu20.04 server系统部署安装上下键控制上下&#xff0c;可以选择配置的目标&#xff0c;回车表示确定&#xff0c;并进行下一步1.1镜像下载2.1 VMware上创建虚拟机2.2 选择语言&#xff0c;键…...

图论最短路径以及floyd算法的MATLAB实现

图论是数学的一个分支&#xff0c;起源于18世纪。1736年&#xff0c;数学家欧拉通过解决“哥尼斯堡七桥问题”&#xff0c;将问题抽象成点和线的关系&#xff0c;并通过理论分析得出结论&#xff0c;这个过程标志着图论的产生&#xff0c;欧拉也因此被称为“图论之父”。图论研…...

微信小程序 - 登录功能实现

一、认证流程 1. 小程序调用wx.login获取登录认证需要的code&#xff0c;并请求开发者服务器。 2. 开发者服务器根据code&#xff0c;appid, appsecret请求微信接口t获取 openid与session_key &#xff0c;并生成自己的认证token&#xff0c;并返回给小程序。 3.小程序请求开…...

Python连接MySQL

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一、整体思路二、连接流程三、表结构及代码实现 一、整体思路 二、连接流程 三、表结构及代码实现 代码块如下&#xff1a; import pymysqlcon pymysql.connect(h…...

水泊梁山108小酒坛之呼保义宋江

宋江【绰号呼保义、及时雨】字公明&#xff0c;是古典名著《水浒传》中的角色。原为山东郓城县押司&#xff0c;他和晁盖互通往来的事被阎婆惜发现&#xff0c;因此怒杀阎婆惜&#xff0c;逃回家隐藏。后前往清风寨投靠花荣&#xff0c;却被清风寨观灯时遭知寨刘高之妻陷害入狱…...

java.lang.ClassNotFoundException: javafx.application.Application

java8&#xff08;jdk1.8&#xff09;到java10&#xff08;jdk10&#xff09;中内含有JavaFx 在java11&#xff08;jdk11&#xff09;以及以后的版本中剥离出来需要开发者独立下载&#xff0c;另行导入download https://gluonhq.com/products/javafx/java --module-path $FX-P…...

2026年AI一键生成歌曲软件精选:音潮 V3.0 零基础闭眼入

2026 年 AI 音乐创作全面大众化&#xff0c;AI 一键生成歌曲软件已经成为日常创作刚需。市面上音潮、Melo、Suno、海绵音乐等AI 音乐生成工具层出不穷&#xff0c;上手难度、成品质感、中文适配度差距明显。经过多轮实测&#xff0c;音潮 V3.0 综合体验一骑绝尘&#xff0c;成为…...

为什么设计师集体弃用Sora 2改投Veo?——从渲染延迟、长时序连贯性到版权水印支持的6维生产力对比

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;Veo vs Sora 2视频质量对比测试全景概览 为客观评估当前主流生成式视频模型的视觉保真度与时空一致性&#xff0c;我们构建了统一测试基准&#xff0c;涵盖运动连贯性、纹理细节还原、文本-视频对齐精度…...

基于计算机视觉的无接触生理测量:从远程PPG原理到工程实践

1. 项目概述&#xff1a;当普通摄像头成为健康监测的“听诊器” 几年前&#xff0c;我在一个远程医疗项目的早期原型测试中&#xff0c;遇到了一个棘手的问题。我们需要为居家康复的老人提供持续的心率监测&#xff0c;但传统的指夹式血氧仪或胸带式心率带&#xff0c;要么让用…...

xhs签名验证机制详解:如何绕过小红书反爬虫系统的终极指南

xhs签名验证机制详解&#xff1a;如何绕过小红书反爬虫系统的终极指南 【免费下载链接】xhs 基于小红书 Web 端进行的请求封装。https://reajason.github.io/xhs/ 项目地址: https://gitcode.com/gh_mirrors/xh/xhs 在小红书数据爬取领域&#xff0c;xhs签名验证机制是开…...

从零到一:深入拆解 I/O 多路复用的前世今生与实战选型

1. 从单线程阻塞到多路复用&#xff1a;I/O模型的进化史 第一次写网络程序时&#xff0c;你可能遇到过这样的场景&#xff1a;服务器在accept()一个客户端连接后&#xff0c;整个程序就像被冻住一样&#xff0c;直到这个客户端发送数据才能继续运行。这就是最原始的阻塞I/O模型…...

AzurLaneAutoScript:碧蓝航线终极自动化解决方案

AzurLaneAutoScript&#xff1a;碧蓝航线终极自动化解决方案 【免费下载链接】AzurLaneAutoScript Azur Lane bot (CN/EN/JP/TW) 碧蓝航线脚本 | 无缝委托科研&#xff0c;全自动大世界 项目地址: https://gitcode.com/gh_mirrors/az/AzurLaneAutoScript 还在为碧蓝航线…...

从“能用”到“可靠”:基于SonarQube与Jenkins的代码质量防线构建实战

当测试覆盖率不再只是一串数字&#xff0c;而是合并代码前的“一票否决权” 1. 为什么你的“质量门禁”只是个摆设&#xff1f; 在很多团队的CI/CD流水线中&#xff0c;SonarQube的集成往往停留在“能跑就行”的阶段。流水线里确实有代码扫描这一步&#xff0c;日志里也打印出…...

Midjourney油彩模式正在悄悄升级!内部测试通道流出的--oil-mode beta参数文档(含笔触方向控制与亚麻布基底模拟指令)

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;Midjourney油彩模式的演进脉络与beta通道解密 Midjourney 的油彩模式&#xff08;Oil Painting Mode&#xff09;并非官方命名的功能&#xff0c;而是社区对一组特定风格化参数组合的统称&#xff0c;…...

电容转换技术突破:电源小型化与高效能设计

1. 电源小型化革命&#xff1a;电容转换技术的突破想象一下&#xff0c;当你拆开最新款的智能手表&#xff0c;发现内部电源模块只占用了指甲盖大小的空间&#xff1b;或者当数据中心机架里的服务器&#xff0c;突然腾出了30%的空间用于增加计算单元。这正是德州仪器&#xff0…...

Armv8-A架构缓存维护指令详解与应用实践

1. A64系统指令中的缓存维护操作概述在Armv8-A架构中&#xff0c;缓存维护操作是确保系统内存一致性的关键机制。作为体系结构设计中最精妙的部分之一&#xff0c;缓存维护指令直接操控处理器缓存层次结构的状态&#xff0c;对系统性能、功能正确性和安全性都有着决定性影响。现…...