求助,听说灌水区大佬多
  • 板块灌水区
  • 楼主MarsNotFound
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/10/18 20:08
  • 上次更新2024/10/18 21:59:40
查看原帖
求助,听说灌水区大佬多
973789
MarsNotFound楼主2024/10/18 20:08

线段树调了好久找不出错,但就是过不了样例

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=200005;

int n,m,a[N],t[N<<2],w[N<<2],sum[N<<2];

int lazy[N<<2],lazzy[N<<2],tag1[N<<2],tag2[N<<2];

int opt,ll,rr,kk;

void Pushup(int k)
{
	sum[k]=sum[k<<1]+sum[k<<1|1];
	t[k]=max(t[k<<1],t[k<<1|1]);
	w[k]=max(w[k<<1],w[k<<1|1]);
}

void Pushdown(int k)
{
	if(tag1[k]!=-1)
	{
		lazy[k<<1]=lazy[k<<1|1]=0;
		tag1[k<<1]=tag1[k<<1|1]=tag1[k];
		t[k<<1]=t[k<<1|1]=tag1[k];
		tag1[k]=-1;
	}
	if(tag2[k]!=-1)
	{
		lazzy[k<<1]=lazzy[k<<1|1]=0;
		tag2[k<<1]=tag2[k<<1|1]=tag2[k];
		w[k<<1]=w[k<<1|1]=tag2[k];
		tag2[k]=-1;
	}
	if(tag1[k])
	{
		t[k<<1]+=t[k];
		t[k<<1|1]+=t[k];
		tag1[k<<1]+=tag1[k];
		tag1[k<<1|1]+=tag1[k];
		tag1[k]=0; 
	}
	if(tag2[k])
	{
		w[k<<1]+=w[k];
		w[k<<1|1]+=w[k];
		tag2[k<<1]+=tag2[k];
		tag2[k<<1|1]+=tag2[k];
		tag2[k]=0; 
	}
}

void build(int k,int l,int r)
{
	lazy[k]=lazzy[k]=-1;
	if(l==r){
		sum[k]=1;
		return;
	}
	else
	{
		int mid=(l+r)>>1;
		build(k<<1,l,mid);
		build(k<<1|1,mid+1,r);
		Pushup(k);
	}
}

inline int read()
{
	int date=0,ww=1;
	char x=getchar();
	while(x<'0' || x>'9')
	{
		if(x=='-')ww=-1;
		x=getchar();
	}
	while(x>='0' && x<='9')
	{
		date=date*10+x-'0';
		x=getchar();
	}
	return date*ww;
}

void update(int k,int l,int r,int L,int R,int v)
{
	if(L<=l && r<=R)
	{
		tag1[k]=0;
		lazy[k]=t[k]=v;
		return;
	}
	else
	{
		Pushdown(k);
		int mid=(l+r)>>1;
		if(L<=mid)
			update(k<<1,l,mid,L,R,v);
		if(mid<R)
			update(k<<1|1,mid+1,r,L,R,v);
		Pushup(k);
	}
}

void update2(int k,int l,int r,int L,int R,int v)
{
	if(L<=l && r<=R)
	{
		tag2[k]=0;
		lazzy[k]=w[k]=v;
		return;
	}
	else
	{
		Pushdown(k);
		int mid=(l+r)>>1;
		if(L<=mid)
			update2(k<<1,l,mid,L,R,v);
		if(mid<R)
			update2(k<<1|1,mid+1,r,L,R,v);
		Pushup(k);
	}
}

void update3(int k,int l,int r,int L,int R,int v)
{
	if(L<=l && r<=R)
	{
		tag1[k]+=v;
		lazy[k]+=v;
		return;
	}
	else
	{
		Pushdown(k);
		int mid=(l+r)>>1;
		if(L<=mid)
			update(k<<1,l,mid,L,R,v);
		if(mid<R)
			update(k<<1|1,mid+1,r,L,R,v);
		Pushup(k);
	}
}

void update4(int k,int l,int r,int L,int R,int v)
{
	if(L<=l && r<=R)
	{
		tag2[k]+=v;
		lazzy[k]+=v;
		return;
	}
	else
	{
		Pushdown(k);
		int mid=(l+r)>>1;
		if(L<=mid)
			update2(k<<1,l,mid,L,R,v);
		if(mid<R)
			update2(k<<1|1,mid+1,r,L,R,v);
		Pushup(k);
	}
}

void distory(int k,int l,int r,int L,int R,int v)
{
	if(L<=l && r<=R)
	{
		sum[k]=0;
		return;
	}
	else
	{
		Pushdown(k);
		int mid=(l+r)>>1;
		if(R<=mid)distory(k<<1,l,mid,L,R,v);
		else if(L>mid)distory(k<<1|1,mid+1,r,L,R,v);
		else distory(k<<1,l,mid,L,R,v),distory(k<<1|1,mid+1,r,L,R,v);
		Pushup(k);
	}
}

signed main()
{
	n=read(),m=read();
	build(1,1,n);
	while(m--)
	{
		opt=read();
		if(opt==1)
		{
			ll=read(),rr=read(),kk=read();
			update(1,1,n,ll,rr,kk);
			update2(1,1,n,1,ll-1,kk);
			update2(1,1,n,rr+1,n,kk);
			update3(1,1,n,ll,rr,kk);
			update4(1,1,n,1,ll-1,kk);
			update4(1,1,n,rr+1,n,kk);
		}
		else if(opt==2)
		{
			ll=read(),rr=read(),kk=read();
			distory(1,1,n,ll,rr,kk);
		}
		else
			cout<<sum[1]<<"\n";
	}
	return 0;
}

P0120

2024/10/18 20:08
加载中...