2023年中国高校计算机大赛-团队程序设计天梯赛(GPLT)上海理工大学校内选拔赛(同步赛)(H题)(线段树)
又到了万物复苏的季节,家乡的苹果树结果了。像往常一样小龙同学被叫回家摘苹果。
假设需要采摘的一棵树上当前有a颗苹果,那么小龙会采摘⌈a/3⌉颗苹果,其中⌈x⌉表示不小于x的最小整数。
但是,为了可持续发展,若a小于10,那么小龙不会采摘这棵树的任何一颗苹果。
此外,小龙时不时会有一些疑问,想知道一些树上当前总共有多少颗苹果。
又或者想知道一些树中有多少棵苹果树上的苹果小于100颗。
那么就请你来帮助小龙同学吧。输入描述:
第1行2个正整数 n和 m。表示小龙同学家有n棵苹果树,m次采摘(或疑问)。第2行 n 个整数,第 i 个整数 ai 表示第 i棵苹果树上原本结有 ai 颗苹果 。接下来 m 行,每行共3个正整数op,l,r。若op=1,表示小龙会采摘 [l,r] 区间内的苹果树。
若op=2,表示小龙想知道 [l,r]区间内的有多少棵苹果树上的苹果小于100颗。
若op=3,表示小龙想知道 [l,r] 区间内的共有多少颗苹果。输出描述:
对于每个 op=2或者op=3的操作,输出1行1个整数表示答案。示例1
输入
5 5 1 10 100 1000 10000 2 1 5 3 1 5 1 1 5 2 1 5 3 1 5输出
2 11111 3 7405备注:
1e5范围
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
typedef pair<int,int> pii;
int n,m;
int a[N];
struct node{int l,r;int max,num100;ll sum;
}tr[N*4];
void pushup(int u){tr[u].max= max(tr[u<<1].max,tr[u<<1|1].max);tr[u].num100=tr[u<<1].num100+tr[u<<1|1].num100;tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void build(int u,int l,int r){tr[u]={l,r,0,0,0};if(l==r){tr[u].max=a[r];tr[u].sum=a[r];if(a[r]<100) tr[u].num100=1;return;}int mid=(l+r)>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);
}
void modify(int u,int l,int r){if(tr[u].max<10) return;if(tr[u].l==tr[u].r){int p=tr[u].sum/3;if(tr[u].sum%3) p++;tr[u].sum-=p;tr[u].max=(int)tr[u].sum;if(tr[u].sum<100)tr[u].num100=1;return;}int mid=tr[u].r+tr[u].l>>1;if(l<=mid) modify(u<<1,l,r);if (r>mid) modify(u<<1|1,l,r);pushup(u);
}
ll querynum100(int u,int l,int r){if(l<=tr[u].l&&r>=tr[u].r) return tr[u].num100;ll res=0;int mid = tr[u].l + tr[u].r >> 1;if (l <= mid) res += querynum100(u << 1, l, r);if (r > mid) res += querynum100(u << 1 | 1, l, r);return res;
}
ll querysum(int u,int l,int r){if(l<=tr[u].l&&r>=tr[u].r) return tr[u].sum;ll res=0;int mid = tr[u].l + tr[u].r >> 1;if (l <= mid) res += querysum(u << 1, l, r);if (r > mid) res += querysum(u << 1 | 1, l, r);return res;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);build(1,1,n);while(m--){int op,l,r;scanf("%d%d%d",&op,&l,&r);if(op==1) modify(1,l,r);if(op==2) printf("%lld\n",querynum100(1,l,r));if(op==3) printf("%lld\n",querysum(1,l,r));}return 0;
}
相关文章:
2023年中国高校计算机大赛-团队程序设计天梯赛(GPLT)上海理工大学校内选拔赛(同步赛)(H题)(线段树)
又到了万物复苏的季节,家乡的苹果树结果了。像往常一样小龙同学被叫回家摘苹果。 假设需要采摘的一棵树上当前有a颗苹果,那么小龙会采摘⌈a/3⌉颗苹果,其中⌈x⌉表示不小于x的最小整数。 但是,为了可持续发展,若a小于1…...
Linux内核Thermal框架详解十三、Thermal Governor(3)
接前一篇文章Linux内核Thermal框架详解十二、Thermal Governor(2) 二、具体温控策略 上一篇文章介绍并详细分析了bang_bang governor的源码。本文介绍第2种温控策略:fair_share。 2. fair_share fair_share governor总的策略是频率档位⽐较…...
TikTok品牌出海创世纪(二)
目录 1.推荐算法打造王者品牌 2.品牌聚焦海外Z群体 3.持续扩展应用场景 加速品牌全球化传播 品牌聚焦海外Z群体 “这个地球上,三分之二的人都在用Facebook“,这是对Facebook曾经统治地位最直观的描述。 但如今,这家全球社交媒体巨头的光环正…...
iOS中SDK开发 -- cocoapods库创建
在iOS项目中,经常使用cocoadpods来进行依赖管理以及三方库引入等。引入的三方库一般会有几种形式:一、在Pods目录下可以直接看到源代码的开源库,如AFNetworking,Masonry等常见开源库。二、在Pods目录下拉取的项目文件只能看到对应…...
2023年了,还是没学会内卷....
先做个自我介绍:我,普本,通信工程专业,现在飞猪干软件测试,工作时长两年半。 回望疫情纪元,正好是实习 毕业这三年。要说倒霉也是真倒霉,互联网浪潮第三波尾巴也没抓住,狗屁造富神…...
chatGPT爆火,什么时候中国能有自己的“ChatGPT“
目录 引言 一、ChatGPT爆火 二、中国何时能有自己的"ChatGPT" 三、为什么openai可以做出chatGPT? 四、结论 引言 随着人工智能技术的不断发展,自然语言处理技术也逐渐成为了研究的热点之一。其中,ChatGPT作为一项领先的自然语言处理技术…...
【Matlab算法】粒子群算法求解一维非线性函数问题(附MATLAB代码)
MATLAB求解一维非线性函数问题前言正文函数实现(可视化处理)可视化结果前言 一维非线性函数是指函数的自变量和因变量都是一维实数,而且函数的形式是非线性的,也就是不符合线性函数的形式。在一维非线性函数中,自变量…...
2023 最新发布超全的 Java 面试八股文,整整 1000道面试题,太全了
作为一名优秀的程序员,技术面试都是不可避免的一个环节,一般技术面试官都会通过自己的方式去考察程序员的技术功底与基础理论知识。 2023 年的互联网行业竞争越来越严峻,面试也是越来越难,很多粉丝朋友私信希望我出一篇面试专题或…...
产品经理面经|当面试官问你还有什么问题?
相信很多产品经理在跳槽面试的时候,在面试尾声都会遇到这样的环节,面试官会问你有什么问题要问的,一般来说大家都能随时随地甩出几个问题来化解,但其实在这个环节对于应聘者来说也是一个很好的机会来展现自己的能力,甚…...
单链表的基本操作
目录 一.链表的基本概念和结构 二.链表的分类 三.单链表的基本操作 1.创建一个节点 2.打印 3.尾插 4.头插 5.尾删 6.头删 7.查找 8.指定位置插入 9.指定位置删除 10.销毁 一.链表的基本概念和结构 概念:链表是一种物理存储结构上非连续、非顺序的存储结…...
【微信小程序-原生开发】系列教程目录(已完结)
01-注册登录账号,获取 AppID、下载安装开发工具、创建项目、上传体验 https://sunshinehu.blog.csdn.net/article/details/128663679 02-添加全局页面配置、页面、底部导航 https://sunshinehu.blog.csdn.net/article/details/128705866 03-自定义底部导航&#x…...
JavaEE--Thread 类的基本用法(不看你会后悔的嘿嘿)
Thread类是JVM用来管理线程的一个类,换句话说,每个线程都唯一对应着一个Thread对象. 因此,认识和掌握Thread类弥足重要. 本文将从 线程创建线程中断线程等待线程休眠获取线程实例 等方面来进行具体说明. 1)线程创建 方法1:通过创建Thread类的子类并重写run () 方法 class M…...
MySQL数据库基本使用(二)-------数据库及表的增删改查及字符集修改
1.MySQL数据库的使用演示 1.1创建自己的数据库 命令格式如下(创建的数据库名称不能与已经存在的数据库重名): mysql> create database 数据库名;例如: mysql> create database atguigudb; #创建atguigudb数据库…...
互联网摸鱼日报(2023-03-17)
互联网摸鱼日报(2023-03-17) InfoQ 热门话题 开源新生代的成长之路:从校园到开源,需要迈过哪些挑战? 从 Clickhouse 到 Apache Doris,慧策电商 SaaS 高并发数据服务的改造实践 刚刚,百度文心…...
【前后端】低代码平台Jeecg-Boot 3.2宝塔云服务器部署流程
1 后端 部署流程 修改配置文件 更改数据库、redis的配置。 在system子模块中的target文件夹下生成 jar 包jeecg-boot-module-system-3.2.0.jar。 复制到云服务器 生成数据库 在这里插入图片描述 使用命令运行后端程序 java -jar ./jeecg-boot-module-system-3.2.0.jar宝…...
leetcode todolist
数组 数组的改变、移动 453. 最小移动次数使数组元素相等 665. 非递减数列 283. 移动零 数组的旋转 189. 旋转数组 396. 旋转函数 统计数组中的元素 645. 错误的集合 697. 数组的度 448. 找到所有数组中消失的数字 442. 数组中重复的数据 41. 缺失的第一个正数 数…...
改进YOLO系列 | CVPR2023最新 PConv | 提供 YOLOv5 / YOLOv7 / YOLOv7-tiny 模型 YAML 文件
DWConv是Conv的一种流行变体,已被广泛用作许多神经网络的关键构建块。对于输入 I ∈ R c h w I \in R^{c \times h \times w} I∈...
像ChatGPT玩转Excel数据
1.引言 最近ChatGPT的出现,把人工智能又带起了一波浪潮。机器人能否替代人类又成了最近热门的话题。 今天我们推荐的一个玩法和ChatGPT有点不一样。我们的课题是“让用户可以使用自然语言从Excel查询到自己想要的数据”。 要让自然语言可以从Excel中查数据&#…...
云原生之docker容器监控详解(cAdvisor、node exporter、prometheus)
docker容器监控一、前言二、cAdvisor2.1、安装cAdvisor2.2、使用Prometheus监控cAdvisor2.3、cAdvisor暴露的Prometheus指标三、Node Exporter3.1、安装Node Exporter3.2、指标四、Prometheus4.1、安装4.2、规则配置4.3、报警管理器五、grafana一、前言 cAdvisor源码 node exp…...
<Linux>进程概念
文章目录一、什么是进程1.进程概念2.进程描述 – PCB3.task_struct内容分类二、进程的基本操作1.查看进程2.结束进程3.通过系统调用获取进程标示符4.通过系统调用创建子进程(fork)三、进程状态1.普遍的操作系统状态2.Linux操作系统状态四、两种特殊的进程1.僵尸进程2.孤儿进程五…...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
