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

P12194 [NOISG 2025 Prelim] Snacks

题目描述

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

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

在处理任何查询之前，以及每次处理完查询之后，Shor 都希望你确定所有盘子中小吃的美味值总和。

形式化地说，给定一个长度为 $n$ 的数组 $a$，你必须处理 $q$ 个查询。在处理所有查询之前，打印 $a$ 中所有元素的总和。在第 $j$ 个查询中，将所有满足 $l[j]\le a[i]\le r[j]$ 的元素 $a[i]$ 更新为 $x[j]$，然后打印更新后的 $a$ 中所有元素的总和。

输入格式

你的程序必须从标准输入读取数据。

输入的第一行包含两个用空格分隔的整数 $n$ 和 $q$。

第二行包含 $n$ 个用空格分隔的整数 $a[1],a[2],\dots ,a[n]$。

接下来的 $q$ 行输入中，每一行包含三个用空格分隔的整数。第 $j$ 行包含 $l[j],r[j]$ 和 $x[j]$，描述了第 $j$ 个查询。

输出格式

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

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

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

接下来的 $q$ 行中，第 $i$ 行应包含一个整数，表示第 $i$ 个查询后 $a$ 中所有元素的总和。

输入输出样例 #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\le n\le 200000$
• $0\le q\le 200000$
• $0\le a[i]\le 10^9$ 对于所有 $1\le i\le n$
• $0\le x[j]\le 10^9$ 对于所有 $1\le j\le q$
• $0\le l[j]\le r[j]\le 10^9$ 对于所有 $1\le j\le q$

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

样例 1 解释

此样例适用于子任务 $2,3,4,6$。

样例 2 解释

此样例适用于子任务 $2,5,6$。

样例 3 解释

此样例适用于子任务 $2,6$。

在所有查询之前，数组 $a$ 为 $[7,72,727,123,321,9]$，总和为 $1259$。

第一次查询后，数组 $a$ 变为 $[10,72,727,123,321,10]$，总和为 $1263$。

第二次查询后，数组 $a$ 变为 $[727,727,727,123,321,727]$，总和为 $3352$。

第三次查询后，数组 $a$ 变为 $[727,727,727,30,321,727]$，总和为 $3259$。

第四次查询后，数组 $a$ 变为 $[99,99,99,30,99,99]$，总和为 $525$。

第五次查询后，数组 $a$ 变为 $[99,99,99,30,99,99]$，总和为 $525$。

C++实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
int l,r;
mutable ll v;
node(int a=0,int b=–1,ll c=0):l(a),r(b),v(c){}
friend bool operator<(node a,node b){return a.l<b.l;}
};
set<node>s;ll ans;
auto split(ll pos){
auto it=s.lower_bound(node(pos));
if(it!=s.end()&&it->l==pos)return it;
it—;ll l=it->l,r=it->r,v=it->v;
s.erase(it),s.insert(node(l,pos–1,v));
return s.insert(node(pos,r,v)).first;
}
void update(ll d,ll k){
auto it2=split(d+1),it1=split(d);
for(auto it=it1;it!=it2;it++)it->v+=k,ans+=d*k;//X的出现次数的更新
}
ll assign(ll l,ll r,ll k){
ll sum=0;
auto it2=split(r+1),it1=split(l);
for(auto it=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);return ans;
}
int main(){
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));
}
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容