原题链接
更好的阅读体验

前置知识：珂朵莉树

ltl0825 （无 merge）
Charllote_（有 merge）

题目大意

给定

n

个元素，以及

m

次操作，每次操作形如

l,r,x

要将

n

个元素中值在

l \sim r

的元素的值变为

x

。

题目解法：

我们看一下题，发现这很像区间推平，于是果断珂朵莉树，但这是在值域上。
所以，权值珂朵莉树就产生了。
我们重新定义一下节点表示的意思：

l,r,val

表示

l \sim r

中的每个权值都出现了

val

次，split 和原来一样。

操作

考虑对于每个操作：

将 $l \sim r$ 每个权值出现次数都变成 $0$ ，设 $l \sim r$ 每个权值出现次数总和为 $tmp$ 。
将 $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;
}

题解：P12194 [NOISG 2025 Prelim] Snacks

文章操作