打卡信奥刷题（3664）用C++实现信奥题 P12194 [NOISG 2025 Prelim] Snacks-云帆数科

P12194 [NOISG 2025 Prelim] Snacks题目描述Shor 小鸭已经准备了nnn个小吃盘子准备一边看电影一边享用第iii个盘子最初装有一个美味值为a[i]a[i]a[i]的小吃。你需要处理qqq个查询。在第jjj个查询中Shor 将按顺序执行以下两个操作吃掉所有美味值在l[j]l[j]l[j]到r[j]r[j]r[j]包含之间的小吃。然后将每一个被吃掉的小吃替换为一个美味值为x[j]x[j]x[j]的新小吃。在处理任何查询之前以及每次处理完查询之后Shor 都希望你确定所有盘子中小吃的美味值总和。形式化地说给定一个长度为nnn的数组aaa你必须处理qqq个查询。在处理所有查询之前打印aaa中所有元素的总和。在第jjj个查询中将所有满足l[j]≤a[i]≤r[j]l[j] \leq a[i] \leq r[j]l[j]≤a[i]≤r[j]的元素a[i]a[i]a[i]更新为x[j]x[j]x[j]然后打印更新后的aaa中所有元素的总和。输入格式你的程序必须从标准输入读取数据。输入的第一行包含两个用空格分隔的整数nnn和qqq。第二行包含nnn个用空格分隔的整数a[1],a[2],…,a[n]a[1], a[2], \ldots, a[n]a[1],a[2],…,a[n]。接下来的qqq行输入中每一行包含三个用空格分隔的整数。第jjj行包含l[j],r[j]l[j], r[j]l[j],r[j]和x[j]x[j]x[j]描述了第jjj个查询。输出格式你的程序必须将结果打印到标准输出。输出应包含q1q 1q1行。输出的第一行应包含一个整数表示在所有查询之前aaa中所有元素的总和。接下来的qqq行中第iii行应包含一个整数表示第iii个查询后aaa中所有元素的总和。输入输出样例 #1输入 #15 3 1 6 2 4 6 6 6 3 2 2 3 3 3 5输出 #119 13 14 20输入输出样例 #2输入 #26 4 929 121 5 3 919 72 1 133 0 70 79 0 900 999 0 1 1000 0输出 #22049 1848 1848 0 0输入输出样例 #3输入 #36 5 7 72 727 123 321 9 7 9 10 10 72 727 111 222 30 123 727 99 111 222 333输出 #31259 1263 3352 3259 525 525说明/提示子任务对于所有测试用例输入将满足以下约束条件1≤n≤200 0001 \leq n \leq 200\,0001≤n≤2000000≤q≤200 0000 \leq q \leq 200\,0000≤q≤2000000≤a[i]≤1090 \leq a[i] \leq 10^90≤a[i]≤109对于所有1≤i≤n1 \leq i \leq n1≤i≤n0≤x[j]≤1090 \leq x[j] \leq 10^90≤x[j]≤109对于所有1≤j≤q1 \leq j \leq q1≤j≤q0≤l[j]≤r[j]≤1090 \leq l[j] \leq r[j] \leq 10^90≤l[j]≤r[j]≤109对于所有1≤j≤q1 \leq j \leq q1≤j≤q你的程序将在满足以下特殊性质的输入数据上进行测试子任务分值特殊性质000000样例111555q0q 0q0222121212n,q≤2000n, q \leq 2000n,q≤2000333212121l[j]r[j]≤200 000l[j] r[j] \leq 200\,000l[j]r[j]≤200000且a[i],x[j]≤200 000a[i], x[j] \leq 200\,000a[i],x[j]≤200000444131313l[j]r[j]l[j] r[j]l[j]r[j]555161616x[j]0x[j] 0x[j]0666333333无样例 1 解释此样例适用于子任务2,3,4,62, 3, 4, 62,3,4,6。样例 2 解释此样例适用于子任务2,5,62, 5, 62,5,6。样例 3 解释此样例适用于子任务2,62, 62,6。在所有查询之前数组aaa为[7,72,727,123,321,9][7, 72, 727, 123, 321, 9][7,72,727,123,321,9]总和为125912591259。第一次查询后数组aaa变为[10,72,727,123,321,10][10, 72, 727, 123, 321, 10][10,72,727,123,321,10]总和为126312631263。第二次查询后数组aaa变为[727,727,727,123,321,727][727, 727, 727, 123, 321, 727][727,727,727,123,321,727]总和为335233523352。第三次查询后数组aaa变为[727,727,727,30,321,727][727, 727, 727, 30, 321, 727][727,727,727,30,321,727]总和为325932593259。第四次查询后数组aaa变为[99,99,99,30,99,99][99, 99, 99, 30, 99, 99][99,99,99,30,99,99]总和为525525525。第五次查询后数组aaa变为[99,99,99,30,99,99][99, 99, 99, 30, 99, 99][99,99,99,30,99,99]总和为525525525。C实现#includebits/stdc.husingnamespacestd;typedeflonglongll;structnode{intl,r;mutablell v;node(inta0,intb-1,ll c0):l(a),r(b),v(c){}friendbooloperator(node a,node b){returna.lb.l;}};setnodes;ll ans;autosplit(ll pos){autoits.lower_bound(node(pos));if(it!s.end()it-lpos)returnit;it--;ll lit-l,rit-r,vit-v;s.erase(it),s.insert(node(l,pos-1,v));returns.insert(node(pos,r,v)).first;}voidupdate(ll d,ll k){autoit2split(d1),it1split(d);for(autoitit1;it!it2;it)it-vk,ansd*k;//X的出现次数的更新}llassign(ll l,ll r,ll k){ll sum0;autoit2split(r1),it1split(l);for(autoitit1;it!it2;it){ans-(it-rit-l)*(it-r-it-l1)/2*it-v;//原来的出现次数消失了更新权值和sum(it-r-it-l1)*it-v;//每个数的出现次数都要给到X}s.erase(it1,it2),s.insert(node(l,r,0));update(k,sum);returnans;}intmain(){ll n,q,x;scanf(%lld%lld,n,q);s.insert(node(0,1e9,0));//一开始的区间for(ll i1;in;i)scanf(%lld,x),update(x,1);//出现次数加一printf(%lld\n,ans);while(q--){ll l,r,x;scanf(%lld%lld%lld,l,r,x);printf(%lld\n,assign(l,r,x));}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容

企业数字化 ERP 产品动态

相关推荐

[Playwright][12] 踩坑记录：为什么 locator.count() 不会自动等待

在 HPC Dashboard 的 Job 自动化测试中，我需要验证日期筛选前后的 Job 数量。在测试中我发现，locator.count() 只会获取当前页面上的元素数量。如果页面数据还没加载出来，可能返回 0。而 toHaveCount() 会在一定时间内反复检查元素数量&#… · 2026/11/2 19:01:10

【C++】set map 使用

目录 1. set 和 map 的与其他类型的介绍对比 2. set 的系列介绍 2.1 set 和 multiset 的相关文献 2.2 set 的初始化函数 2.3 set 的增删改函数 2.4 set 的其他函数 2.5 set 和 multiset 的对比 3. map 的系列介绍 3.1 map 和 multimap 的相关文献 3.2 map 的初始化函… · 2026/11/2 19:00:07

Spring AI 多模态实战（下）：文生图 + TTS 语音合成（含 2.0 流式音频分片）

Spring AI 多模态实战（下）：文生图 TTS 语音合成（含 2.0 流式音频分片）系列：Spring AI 深入浅出（第 17 篇） 版本：Spring AI 2.0.1 / Spring Boot 4.1.x / JDK 21 标签&am… · 2026/11/2 18:59:03

AI声线转换技术实践：从VITS模型到萝莉音合成

1. 项目背景与核心思路最近在语音合成领域出现了一个有趣的技术应用方向——通过AI技术实现让知名艺人使用特定声线（如萝莉音）录制个性化语音内容。这个项目的核心在于突破传统语音合成的限制，实现高度拟真且富有表现力的声线转换。我花了… · 2026/11/3 16:02:08

明星语音转换技术：从声纹特征到情感增强

1. 项目背景与核心思路去年在某个深夜调试语音模型时，我突然冒出一个想法：如果能用喜欢的明星声音定制专属晚安问候，会是种什么体验？这个看似娱乐化的需求背后，其实涉及语音合成领域多个前沿技术的交叉应用。经过两个… · 2026/11/3 16:02:08

高校食堂移动预约点餐系统开发实践

1. 项目背景与需求分析作为一名在高校信息化领域摸爬滚打多年的开发者，我深刻理解食堂就餐高峰期的痛点。每到中午11:30，各个档口前蜿蜒的长队已经成为校园"特色景观"。学生们端着餐盘在队伍中缓慢移动，而食堂工作人员则在重复着&q… · 2026/11/3 16:02:08

SpringBoot水产养殖管理系统开发实践

1. 项目概述水产养殖行业正经历从传统人工管理向数字化、智能化转型的关键阶段。作为一名长期从事农业信息化系统开发的工程师，我在实际项目中发现，大多数中小型养殖场仍在使用纸质记录本和Excel表格来管理养殖过程，这种方式不仅效率低下&am… · 2026/11/3 16:02:08

5G NR覆盖优化指导：SS-RSRP门限、RF调整与波束权值实战

简介：《5G NR无线网络覆盖优化指导书》面向5G网络规划优化工程师、工程交付与运维人员，以及需要系统梳理覆盖评估与验收标准的通信从业者，重点解决弱覆盖、覆盖空洞、越区覆盖和导频污染等现场问题。覆盖优化贯穿实验网、预商用、工程优化与日… · 2026/11/3 16:02:08

双向链表节点删除操作详解与优化技巧

1. 双向链表删除节点的核心逻辑双向链表作为一种基础数据结构，相比单向链表最大的特点在于每个节点同时保存了前驱和后继指针。这种设计使得删除操作不再需要像单向链表那样遍历查找前驱节点，但也带来了指针维护的复杂性。在实际工程中，正确处… · 2026/11/3 16:01:06

双极步进电机控制实战：DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/2 13:10:28

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

STM32F411RE与MAX14431实现SPI隔离：工业现场抗共模干扰实战

ESP32+大模型AI硬件开发：从Demo到产品的8个工程问题

基于MAX14431BAEE+与PIC18F85J10的SPI隔离方案设计与实践

双极步进电机控制实战：DRV8818PWPR与PIC18F86K22驱动调试

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

打卡信奥刷题（3664）用C++实现信奥题 P12194 [NOISG 2025 Prelim] Snacks

相关推荐

了解更多？预约专属演示