题解：P12194 [NOISG 2025 Prelim] Snacks

· · 题解

FHQ-Treap

看到机房大佬全在写权值线段树，但是很难调，有人干脆调不出来放弃了，于是笔者突发奇想用刚学的 FHQ-Treap，可能是笔者思维不够，有点小题大做了，跑的也很慢。

看题目，发现有个权值区间操作，即把 \forall l \leq a_i \leq r 都改为 x，这个刚好可以用 FHQ 的权值分裂来解决，至于求和，我们再在树上维护一个和数组，pushup 的时候更新即可。

Code

#include<bits/stdc++.h>
#define int long long
#define inf 1e18
#define gc getchar
#define pc putchar
#define rg register
#define LB lower_bound
#define UB upper_bound
#define PII pair<int, int> 
#define PDI pair<double, int>
#define fi first
#define se second
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using db=long double;
using ll=long long;
using ull=unsigned long long;
using namespace std;
namespace IO{
    inline int read(){
        int x=0,f=1;
        char ch=gc();
        while(!isdigit(ch)){
            if(ch=='-') f=-f;
            ch=gc();
        }
        while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=gc();
        return x*f;
    }
    inline void write(int x){
        if(x<0) pc('-'),x=-x;
        if(x>9) write(x/10);
        pc(x%10+'0');
    }
}
using namespace IO;
const int N=1e6+10;
struct FHQ{
    #define ls(i) tree[i][0]
    #define rs(i) tree[i][1]
    int root,tot,tree[N][2],size[N];
    int val[N],pri[N],cnt[N],sum[N];
    inline int newnode(int x, int num){
        int u=++tot;
        pri[u]=rand();
        val[u]=x,size[u]=num,ls(u)=rs(u)=0;
        cnt[u]=num,sum[u]=val[u]*cnt[u];
        return u;
    }
    inline void pushup(int u){
        size[u]=size[ls(u)]+size[rs(u)]+cnt[u];
        sum[u]=sum[ls(u)]+sum[rs(u)]+val[u]*cnt[u];
    }
    inline void split(int u, int x, int &L, int &R){
        if(!u){L=R=0;return;}
        if(val[u]<=x){L=u;split(rs(u),x,rs(u),R);}
        else{R=u;split(ls(u),x,L,ls(u));}
        pushup(u);
    }
    inline int _merge(int L, int R){
        if(!L||!R) return L+R;
        if(pri[L]<pri[R]){
            rs(L)=_merge(rs(L),R);
            pushup(L);return L;
        }else{
            ls(R)=_merge(L,ls(R));
            pushup(R);return R;
        }
    }
    inline void insert(int w, int num){
        int L,R;
        split(root,w,L,R);
        int u=newnode(w,num);
        int tmp=_merge(L,u);
        root=_merge(tmp,R);
    }
    inline void solve(int l, int r, int x){
        int L,R,p;
        split(root,r,L,R);
        split(L,l-1,L,p);//权值分裂 
        int tmp=size[p];
        root=_merge(L,R);
        insert(x,tmp);//重新插入 x 
        write(sum[root]);puts("");
    }
}T;
int n,q,a[N],tot;
signed main(){
    srand(20100102);
    n=read(),q=read();
    for(rg int i=1;i<=n;i++) a[i]=read(),T.insert(a[i],1);
    write(T.sum[T.root]);puts("");
    while(q--){
        int l=read(),r=read(),x=read();
        T.solve(l,r,x);
    }
    return 0;
}

开 2e5 不知道为啥 RE 了，然后就随手开了个 1e6。

PS：为啥要评黄啊？

End