题解：P12194 [NOISG 2025 Prelim] Snacks
ltl0825
·
·
题解
原题链接\
更好的阅读体验
前置知识：珂朵莉树
ltl0825 （无 merge）\
Charllote_（有 merge）
题目大意
给定 n 个元素，以及 m 次操作，每次操作形如 l,r,x 要将 n 个元素中值在 l \sim r 的元素的值变为 x。
题目解法：
我们看一下题，发现这很像区间推平，于是果断珂朵莉树，但这是在值域上。\
所以，权值珂朵莉树就产生了。\
我们重新定义一下节点表示的意思：\
## 操作
考虑对于每个操作：
1. 将 $l \sim r$ 每个权值出现次数都变成 $0$，设 $l \sim r$ 每个权值出现次数总和为 $tmp$。
2. 将 $x$ 出现的次数加上 $tmp$。
所以我们需要区间推平和单点加，在推平时还可以暴力求 $tmp$。
## 查询
我们动态维护一个 $sum$，在操作时进行更改（详见代码）。
# 注意
十年 OI 一场空，不开 `long long` 见祖宗。
# 代码（含注释）
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
int l,r;
mutable int cnt;//mutable 可以在迭代器中修改此值
bool operator < (const node&W)const
{
return l<W.l;
}
};
set<node> s;
auto split(int x)//split和原来一样
{
auto it=s.lower_bound({x,0,0});
if(it!=s.end()&&it->l == x)
{
return it;
}
it--;
int l=it->l,r=it->r,cnt=it->cnt;
s.erase(it);
s.insert({l,x-1,cnt});
return s.insert({x,r,cnt}).first;
}
int sum=0;//和值
void add(int x,int v)//单点加，将 x 权值出现次数 +v
{
auto itr=split(x+1),itl=split(x);
for(auto it=itl;it!=itr;it++)
{
it->cnt+=v;
sum+=x*v;//维护sum
}
}
void assgin(int l,int r,int val)//将 l~r 中的权值都变为 val
{
auto itr=split(r+1),itl=split(l);
int tmp=0;
for(auto it=itl;it!=itr;it++)
{
sum-=(it->r+it->l)*(it->r-it->l+1)/2*it->cnt;//it->l~it->r 都出现了 it->cnt 次，用等差数列求和解决
tmp+=it->cnt;//维护 tmp
}
s.erase(itl,itr);//区间推平
s.insert({l,r,0});
add(val,tmp);//add
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin>>n>>m;
s.insert({0,int32_t(1e9),0});//由于有0权值，所以要从0开始
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
add(x,1);//add 进行初始化
}
cout<<sum<<'\n';
for(int i=1;i<=m;i++)
{
int l,r,x;
cin>>l>>r>>x;
assgin(l,r,x);//操作
cout<<sum<<'\n';
}
return 0;
}
```