题解：P12194 [NOISG 2025 Prelim] Snacks

ni_ju_ge · 2025-10-03 11:22:15 · 题解

题目传送门

思路

权值线段树+离散化乱搞。

先离线下来离散化一下。

权值线段树每个节点存一下值域内数的个数和它们总和，操作一就是区间修，操作二就是单点加。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
struct problem {
    ll l,r,x;
} t[N];
ll n,q,a[N];
ll z[4*N],p[4*N],cnt,tot;
map<ll,ll> mp1,mp2;
struct node {
    int l,r;
    ll zs,sm;
    bool laz;
} tr[16*N];
void up(int pos) {
    tr[pos].sm=tr[pos*2].sm+tr[pos*2+1].sm;
    tr[pos].zs=tr[pos*2].zs+tr[pos*2+1].zs;
}
void pd(int pos) {
    if(!tr[pos].laz) return;
    tr[pos*2].laz=tr[pos*2+1].laz=1;
    tr[pos*2].sm=tr[pos*2].zs=0;
    tr[pos*2+1].sm=tr[pos*2+1].zs=0;
    tr[pos].laz=0;
}
void bd(int l,int r,int pos) {
    tr[pos].l=l,tr[pos].r=r;
    if(l==r) {
        tr[pos].zs=mp2[l];
        tr[pos].sm=tr[pos].zs*p[l];
        return;
    }
    int mid=(l+r)/2;
    bd(l,mid,pos*2);bd(mid+1,r,pos*2+1);
    up(pos);
}
ll qs(int l,int r,int pos) {
    if(tr[pos].l>r||tr[pos].r<l) return 0;
    if(tr[pos].l>=l&&tr[pos].r<=r) {
        tr[pos].laz=1;
        ll res=tr[pos].zs;
        tr[pos].sm=tr[pos].zs=0;
        return res;
    }
    pd(pos);
    ll res=qs(l,r,pos*2)+qs(l,r,pos*2+1);
    up(pos);
    return res;
}
void pl(int gl,int pos,int val) {
    if(tr[pos].l>gl||tr[pos].r<gl) return;
    if(tr[pos].l==tr[pos].r) {
        tr[pos].zs+=val;
        tr[pos].sm+=val*p[tr[pos].l];
        return;
    }
    pd(pos);
    pl(gl,pos*2,val);pl(gl,pos*2+1,val);
    up(pos);
}
void init() {
    sort(z+1,z+tot+1);
    z[0]=-1;
    for(int i=1;i<=tot;i++) {
        if(z[i]!=z[i-1]) {
            p[++cnt]=z[i];
            mp1[z[i]]=cnt;
        }
    }
    for(int i=1;i<=n;i++) mp2[mp1[a[i]]]++;
}
void aswr() {printf("%lld\n",tr[1].sm);}
int main() {
    cin>>n>>q;
    for(int i=1;i<=n;i++) {
        scanf("%lld",&a[i]);
        z[++tot]=a[i];
    }
    for(int i=1;i<=q;i++) {
        scanf("%lld %lld %lld",&t[i].l,&t[i].r,&t[i].x);
        z[++tot]=t[i].l,z[++tot]=t[i].r,z[++tot]=t[i].x;
    }
    init();
    bd(1,cnt,1);aswr();
    for(int i=1;i<=q;i++) {
        ll l=mp1[t[i].l],r=mp1[t[i].r],x=mp1[t[i].x];
        ll gd=qs(l,r,1);
        pl(x,1,gd);
        aswr();
    }
}