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