专栏文章

题解：P12194 [NOISG 2025 Prelim] Snacks

llzt415
P12194题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip10pez
此快照首次捕获于
2025/12/03 04:24
3 个月前
此快照最后确认于
2025/12/03 04:24
3 个月前
查看原文

笔因

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

前言

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

思路

我们发现这道题只有两个操作，即把值在 ll 和 rr 间的数全部删掉，然后将值为 xx 的数的个数增加等量的数量。这其实挺明显用权值线段树维护的，而且要离散化。但是细节有点恶心心。
如下：（只是指我犯的，不代表大家，勿喷）
  1. 输出所有元素的总和，但我二话没说写了个元素个数之和。这个应该都没错，只能说我太蒟了。
  2. 这个我觉得可能有一点易错，就是这个 xjx_j 也要放进离散化数组里，因为这个数可能是原来没有的，所以要先全部把数据读入在统一处理做题。
  3. 注意有时候行与行的位置不能放反，有时候有后效性，改变了原先的值，比如计算满足条件的 aia_i 的个数时。

code

其实本人的马蜂挺好的，只不过这次的码不小心写的有点随性。
凑合地看吧。
CPP
#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;
}
额，longlong longlong 是个好氡锡。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...