求条WA on #6
查看原帖
求条WA on #6
795344
lfxxx_楼主2025/1/16 09:03

rt

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int col[N<<2],sum[N<<2],tag[N<<2];
void pushup(int p)
{
	sum[p]=sum[p<<1]+sum[p<<1|1];
	if(col[p<<1]==col[p<<1|1])
		col[p]=col[p<<1];
	else
		col[p]=0;
} 
void addtag(int p,int pl,int pr,int c)
{
	sum[p]+=abs(col[p]-c)*(pr-pl+1);
	tag[p]=col[p]=c;
}
void pushdown(int p,int pl,int pr)
{
	int mid=(pl+pr)>>1;
	if(tag[p])
	{
		addtag(p<<1,pl,mid,tag[p]);
		addtag(p<<1|1,mid+1,pr,tag[p]);
		tag[p]=0;
	}
}
void build(int p,int pl,int pr)
{
	if(pl==pr)
	{
		sum[p]=0;
		col[p]=pl;
		return ;
	}
	int mid=(pl+pr)>>1;
	build(p<<1,pl,mid);
	build(p<<1|1,mid+1,pr);
	pushup(p);
}
void update(int p,int pl,int pr,int L,int R,int c)
{
	if(R<pl||pr<L)
		return ;
	if(L<=pl&&pr<=R&&col[p]!=0)
	{
		addtag(p,pl,pr,c);
		return ;
	}
	int mid=(pl+pr)>>1;
	pushdown(p,pl,pr);
	update(p<<1,pl,mid,L,R,c);
	update(p<<1|1,mid+1,pr,L,R,c);
	pushup(p); 
}
int query(int p,int pl,int pr,int L,int R)
{
	if(R<pl||pr<L)
		return 0;
	if(L<=pl&&pr<=R)
		return sum[p];
	pushdown(p,pl,pr);
	int mid=(pl+pr)>>1;
	return query(p<<1,pl,mid,L,R)+query(p<<1|1,mid+1,pr,L,R);
} 
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	build(1,1,n);
	while(m--)
	{
		int op,x,y,k;
		cin>>op>>x>>y;
		if(op==1)
			cin>>k,update(1,1,n,x,y,k);
		if(op==2)
			cout<<query(1,1,n,x,y)<<'\n';
	}
}
2025/1/16 09:03
加载中...