题解：P12194 [NOISG 2025 Prelim] Snacks

lzt415 · 2025-06-27 21:28:19 · 题解

笔因

居然调这么一个水绿调了这么久，记录一下这个齿孺。

前言

其实这题挺无脑的，一看就是权值线段树，看完题面我都没想到其他东西能做，可能是我太菜了。

思路

我们发现这道题只有两个操作，即把值在 l 和 r 间的数全部删掉，然后将值为 x 的数的个数增加等量的数量。这其实挺明显用权值线段树维护的，而且要离散化。~~但是细节有点恶心心~~。

如下：（只是指我犯的，不代表大家，勿喷）

输出所有元素的总和，但我二话没说写了个元素个数之和。这个应该都没错，只能说我太蒟了。
这个我觉得可能有一点易错，就是这个 x_j 也要放进离散化数组里，因为这个数可能是原来没有的，所以要先全部把数据读入在统一处理做题。
注意有时候行与行的位置不能放反，有时候有后效性，改变了原先的值，比如计算满足条件的 a_i 的个数时。
code

其实本人的马蜂挺好的，只不过这次的码不小心写的有点随性。

凑合地看吧。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+10;
int a[N],t[N],tag[N],n,q,b[N],cnt,tot,l[N],r[N],x[N],sum[N];
void change(int k,int l,int r,int p,int val,int w)
{
    if(l==r) {t[k]+=val;sum[k]+=w;return;}
    if(tag[k]) 
    {
        t[k*2]=sum[k*2]=t[k*2+1]=sum[k*2+1]=0;
        tag[k*2]=tag[k*2+1]=1;
        tag[k]=0;
    }   
    int mid=(l+r)/2;
    if(p<=mid) change(k*2,l,mid,p,val,w);
    else change(k*2+1,mid+1,r,p,val,w);
    t[k]=t[k*2]+t[k*2+1];
    sum[k]=sum[k*2]+sum[k*2+1];
}
void update(int k,int l,int r,int x,int y)
{
    if(x<=l&&r<=y) {t[k]=sum[k]=0,tag[k]=1;return;}
    if(tag[k]) 
    {
        t[k*2]=sum[k*2]=t[k*2+1]=sum[k*2+1]=0;
        tag[k*2]=tag[k*2+1]=1;
        tag[k]=0;
    }   
    int mid=(l+r)/2;
    if(x<=mid) update(k*2,l,mid,x,y);
    if(y>=mid+1) update(k*2+1,mid+1,r,x,y); 
    t[k]=t[k*2]+t[k*2+1];
    sum[k]=sum[k*2]+sum[k*2+1];
}
int query(int k,int l,int r,int x,int y)
{
    if(x<=l&&r<=y) return t[k];
    if(tag[k]) 
    {
        t[k*2]=sum[k*2]=t[k*2+1]=sum[k*2+1]=0;
        tag[k*2]=tag[k*2+1]=1;
        tag[k]=0;
    }
    int mid=(l+r)/2,res=0;
    if(x<=mid) res+=query(k*2,l,mid,x,y);
    if(y>=mid+1) res+=query(k*2+1,mid+1,r,x,y);
    t[k]=t[k*2]+t[k*2+1];
    sum[k]=sum[k*2]+sum[k*2+1];
    return res;
}
int _(int k,int l,int r,int x,int y)
{
    if(x<=l&&r<=y) return sum[k];
    if(tag[k]) 
    {
        t[k*2]=sum[k*2]=t[k*2+1]=sum[k*2+1]=0;
        tag[k*2]=tag[k*2+1]=1;
        tag[k]=0;
    }
    int mid=(l+r)/2,res=0;
    if(x<=mid) res+=_(k*2,l,mid,x,y);
    if(y>=mid+1) res+=_(k*2+1,mid+1,r,x,y);
    t[k]=t[k*2]+t[k*2+1];
    sum[k]=sum[k*2]+sum[k*2+1];
    return res; 
}
signed main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i],b[++tot]=a[i];
    for(int i=1;i<=q;i++)
    {
        cin>>l[i]>>r[i]>>x[i];
        b[++tot]=l[i],b[++tot]=r[i],b[++tot]=x[i];
    }
    sort(b+1,b+tot+1);
    int m=unique(b+1,b+tot+1)-b-1;
    for(int i=1;i<=n;i++)
    {
        int t=lower_bound(b+1,b+m+1,a[i])-b;
        change(1,1,m,t,1*a[i],1);
    }
    cout<<t[1]<<endl;
    for(int i=1;i<=q;i++)
    {
        int L=lower_bound(b+1,b+m+1,l[i])-b;
        int R=lower_bound(b+1,b+m+1,r[i])-b;
        int cnt=_(1,1,m,L,R);
        update(1,1,m,L,R);
        int X=lower_bound(b+1,b+m+1,x[i])-b;
        change(1,1,m,X,cnt*x[i],cnt);
        cout<<query(1,1,m,1,m)<<endl;
    }

    return 0;
}

额，long long 是个好氡锡。

题解：P12194 [NOISG 2025 Prelim] Snacks

笔因

前言

思路

code