P12194 [NOISG 2025 Prelim] Snacks

题目描述

Shor 小鸭已经准备了nnn个小吃盘子，准备一边看电影一边享用！第iii个盘子最初装有一个美味值为a[i]a[i]a[i]的小吃。

你需要处理qqq个查询。在第jjj个查询中，Shor 将按顺序执行以下两个操作：

1. 吃掉所有美味值在l[j]l[j]l[j]到r[j]r[j]r[j]（包含）之间的小吃。
2. 然后，将每一个被吃掉的小吃替换为一个美味值为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个查询。

输出格式

你的程序必须将结果打印到标准输出。

输出应包含q+1q + 1q+1行。

输出的第一行应包含一个整数，表示在所有查询之前aaa中所有元素的总和。

接下来的qqq行中，第iii行应包含一个整数，表示第iii个查询后aaa中所有元素的总和。

输入输出样例 #1

输入 #1

5 3 1 6 2 4 6 6 6 3 2 2 3 3 3 5

输出 #1

19 13 14 20

输入输出样例 #2

输入 #2

6 4 929 121 5 3 919 72 1 133 0 70 79 0 900 999 0 1 1000 0

输出 #2

2049 1848 1848 0 0

输入输出样例 #3

输入 #3

6 5 7 72 727 123 321 9 7 9 10 10 72 727 111 222 30 123 727 99 111 222 333

输出 #3

1259 1263 3352 3259 525 525

说明/提示

子任务

对于所有测试用例，输入将满足以下约束条件：

• 1≤n≤200 0001 \leq n \leq 200\,0001≤n≤200000
• 0≤q≤200 0000 \leq q \leq 200\,0000≤q≤200000
• 0≤a[i]≤1090 \leq a[i] \leq 10^90≤a[i]≤109对于所有1≤i≤n1 \leq i \leq n1≤i≤n
• 0≤x[j]≤1090 \leq x[j] \leq 10^90≤x[j]≤109对于所有1≤j≤q1 \leq j \leq q1≤j≤q
• 0≤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

你的程序将在满足以下特殊性质的输入数据上进行测试：

样例 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++实现

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;structnode{intl,r;mutablell v;node(inta=0,intb=-1,ll c=0):l(a),r(b),v(c){}friendbooloperator<(node a,node b){returna.l<b.l;}};set<node>s;ll ans;autosplit(ll pos){autoit=s.lower_bound(node(pos));if(it!=s.end()&&it->l==pos)returnit;it--;ll l=it->l,r=it->r,v=it->v;s.erase(it),s.insert(node(l,pos-1,v));returns.insert(node(pos,r,v)).first;}voidupdate(ll d,ll k){autoit2=split(d+1),it1=split(d);for(autoit=it1;it!=it2;it++)it->v+=k,ans+=d*k;//X的出现次数的更新}llassign(ll l,ll r,ll k){ll sum=0;autoit2=split(r+1),it1=split(l);for(autoit=it1;it!=it2;it++){ans-=(it->r+it->l)*(it->r-it->l+1)/2*it->v;//原来的出现次数消失了，更新权值和sum+=(it->r-it->l+1)*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 i=1;i<=n;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考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容