打卡信奥刷题（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考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容

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

相关推荐

常见标定方式

【开源工程审计L3】rapidsai/cudf 静态源码一页纸评测报告（固定快照：8d0d077）

内存省95%、延迟降80%？拆解金仓前天的发布会，我关心的几个指标落地了

更多资讯

智能体硬件三块短板：GPU、KV缓存与CPU调度优化实战

AMD 7900 XTX跑27B模型：hipEngine与llama.cpp实测，我为何没换引擎

AI辅助漏洞挖掘门槛塌方：PS5大神退圈背后的技术信号

基于AT89S52与模糊PID的恒温水箱温控系统设计

Grok4.7高分却退订？真实用户的AI订阅体验与选型反思

从实时全模态交互到自主智能体：端侧大模型如何迈向真正的端侧智能？

今日更新

PLFM_RADAR：从被动告警到主动感知的微服务健康监控系统

SPI隔离设计实战：MAX14431BAEE+与STM32F407工业级应用

数字隔离器如何根治SPI通信地环路干扰：MAX14431与TM4C129实战

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？