题解：P12194 [NOISG 2025 Prelim] Snacks

· · 题解

思路

这是一道非常有趣的题目，可以用很多种方法解决。

我在这里提供一种 FHQ-treap 的做法。

我们发现这道题只有一种操作，就是将一个序列 A 中所有的 l\leq A_i \leq r 全部改为 k。

那么我们将这个操作分为三部分。

第一步在我们的 FHQ-treap 上分裂出 x<l，l\leq x\leq r，r<x 这三部分。这一步非常简单，是基本操作，同时，我们令分裂出来三部分的根节点分别为 sx，sy，sz。

第二步合并 sx 和 sz，这一步相当与删除了 sy。

第三步，往我们的 FHQ-treap 中塞入 siz_{sy} 个 k。我们知道，原本 FHQ-treap 中，同一个数是不会在同一个节点的。但是在这里，我们考虑给每个节点多一个 cnt 值。表示这个节点拥有 cnt 个值为 val的数字。

既然如此，在 push_up 中 siz 的更新就会变成 siz_x=siz_ {ls}+siz_{rs}+cnt_x。

既然是统计和，所以维护 sum 是显然的。

接下来我们探讨一个问题，我们根据 l 和 r 进行分裂，最后却插入的是 k。会不会打破左小右大的规则呢。

答案是不会，这里关键就在于我们是先把 sx 和 sz 合并了，然后在合并完的 FHQ-treap 上重新做了一次普通的插入操作。这样我们就不用担心会出现上文所述的问题了。

代码不是很好，请见谅。

code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,q;
const int N=7e5+5;
struct fhqarr{int ls,rs,val,cnt,rnd,siz,sum;};
struct fhqtreap
{
    fhqarr b[N];
    int tot;
    int rt;
    int sx,sy,sz;
    inline int newnode(int x,int res)
    {
        b[++tot].val=x;
        b[tot].cnt=res;
        b[tot].sum=x*res;
        b[tot].rnd=rand();
        b[tot].siz=res;
        return tot;
    }
    inline void up(int x)
    {
        b[x].siz=b[b[x].ls].siz+b[b[x].rs].siz+b[x].cnt;
        b[x].sum=b[b[x].ls].sum+b[b[x].rs].sum+b[x].cnt*b[x].val;
        return;
    }
    void split(int x,int k,int &u,int &v)
    {
        if(!x){u=v=0;return;}
        if(b[x].val<=k)u=x,split(b[x].rs,k,b[x].rs,v);
        else v=x,split(b[x].ls,k,u,b[x].ls);
        up(x);
    }
    int merge(int x,int y)
    {
        if(!x||!y)return x+y;
        if(b[x].rnd<b[y].rnd)
        {
            b[x].rs=merge(b[x].rs,y);
            up(x);
            return x;
        }
        else 
        {
            b[y].ls=merge(x,b[y].ls);
            up(y);
            return y;
        }
    }
    inline void insert(int v,int p)
    {
        split(rt,v,sx,sy);
        rt=merge(merge(sx,newnode(v,p)),sy);
        return;
    }
    inline void update(int l,int r,int k)
    {
        split(rt,r,sx,sz);
        split(sx,l-1,sx,sy);
        int slv=b[sy].siz;
        rt=merge(sx,sz);
        insert(k,slv);
        return;
    }
}momoka;
signed main()
{
    srand(time(0));
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>q;
    for(int i=1,x;i<=n;++i)cin>>x,momoka.insert(x,1);
    cout<<momoka.b[momoka.rt].sum<<'\n';
    while(q--)
    {
        int l,r,k;
        cin>>l>>r>>k;
        momoka.update(l,r,k);
        cout<<momoka.b[momoka.rt].sum<<'\n';
    }
    return 0;
}