HDU ACM 4578 Transformation-＆gt; Segment tree - interval change

Hello everyone , I meet you again , I'm the king of the whole stack

analysis ： Complex business segment tree .

There is only one query operation , It's a requirement [l,r] Between the number of p Sum of thorium . Not all queries, all nodes , meeting TLE. The best part is the query part [a.b]. We are equal for all of these interval values , I can return to （b-a+1）*val Value . An interval in which all values in the interval are the same . For initial value setting and addition and multiplication operations . There are two situations ：1、 When it is set to initial value . Just cover the interval directly . And assign the marked addition and multiplication operation as the initial value .2、 When it is an addition and multiplication operation . First, infer whether the current interval segment is the same value , If yes, add and multiply directly , Maintain the same value . Assumptions are different , See whether the interval has an addition and multiplication mark , Pass this addition and multiplication mark all the way down . Stop until you meet the same value of that interval . Finally, assign this addition and multiplication to the initial interval . Simply put , The override operation can be maintained directly , If it is not an override operation . Only one addition and multiplication operation can be reserved in the interval .

#include<iostream>
using namespace std;

#define lz t<<1,l,mid           // Left interval 
#define rz (t<<1)|1,mid+1,r     // The right range 
#define N 100005
#define MOD 10007
__int64 add[N<<2],mul[N<<2],chan[N<<2],sum[N<<2];

void Build(int t,int l,int r)  // Create a line tree 
{
	int mid;

	mul[t]=1;
	add[t]=sum[t]=0;
	chan[t]=0;
	if(l==r)
	{
		chan[t]=1;           // Set leaf node to 1. Convenient inquiry 
		return ;
	}
	mid=(l+r)>>1;
	Build(lz);
	Build(rz);
}

void PushDown(int t,int l,int r)   // Mark down 
{
	int mid;

	if(l==r) return ;
	mid=(l+r)>>1;
	if(chan[t])      //set Mark down 
	{
		add[t<<1]=0,mul[t<<1]=1;
		add[(t<<1)|1]=0,mul[(t<<1)|1]=1;
		chan[t<<1]=chan[(t<<1)|1]=1;
		sum[t<<1]=sum[(t<<1)|1]=sum[t];
		chan[t]=0;
	}
	else 
	{
		if(add[t])  // Mark and download 
		{
	    	if(chan[t<<1]) sum[t<<1]=(sum[t<<1]+add[t])%MOD; // Zuo Zi Shu you set Mark 
    		else
			{
	    		PushDown(lz);   // Next 
	    		add[t<<1]=(add[t<<1]+add[t])%MOD;
			}
	     	if(chan[(t<<1)|1]) sum[(t<<1)|1]=(sum[(t<<1)|1]+add[t])%MOD; // Zuo Zi Shu you set Mark 
	    	else
			{
	    		PushDown(rz);   // Next 
	    		add[(t<<1)|1]=(add[(t<<1)|1]+add[t])%MOD;
			}
	    	add[t]=0;
		}
		if(mul[t]>1) // Multiply the mark and pass it down 
		{
    		if(chan[t<<1]) sum[t<<1]=(sum[t<<1]*mul[t])%MOD; // Zuo Zi Shu you set Mark 
	     	else
			{
		    	PushDown(lz);   // Next 
		    	mul[t<<1]=(mul[t<<1]*mul[t])%MOD;
			}
	    	if(chan[(t<<1)|1]) sum[(t<<1)|1]=(sum[(t<<1)|1]*mul[t])%MOD; // Zuo Zi Shu you set Mark 
	    	else
			{
	     		PushDown(rz);   // Next 
	    		mul[(t<<1)|1]=(mul[(t<<1)|1]*mul[t])%MOD;
			}
	    	mul[t]=1;
		}
	}
}

void Update(int t,int l,int r,int ul,int ur,int c,int op)
{
	int mid;

	if(l>=ul && ur>=r) // The border 
	{
		if(op==3)
			chan[t]=1,mul[t]=1,add[t]=0,sum[t]=c;
		else if(chan[t])
		{
			if(op==1) sum[t]=(sum[t]+c)%MOD;
			else sum[t]=(sum[t]*c)%MOD;
		}
		else
		{
			PushDown(t,l,r);  // Next 
			if(op==1) add[t]=(add[t]+c)%MOD;
			else mul[t]=(mul[t]*c)%MOD;
		}
		return ;
	}
	PushDown(t,l,r);
	mid=(l+r)>>1;
	if(ur<=mid) Update(lz,ul,ur,c,op);
	else if(ul>mid) Update(rz,ul,ur,c,op);
	else
	{
		Update(lz,ul,mid,c,op);
		Update(rz,mid+1,ur,c,op);
	}
}

__int64 Query(int t,int l,int r,int ul,int ur,int p)
{
	int mid,i;
	__int64 ans,tp,t1,t2;

	if(ul<=l && r<=ur)
		if(chan[t])
		{
			ans=1;
			tp=sum[t];
			for(i=1;i<=p;i++) ans=(ans*tp)%MOD;
			return (r-l+1)*ans%MOD;              // Because every part of the interval is the same 
		}
	PushDown(t,l,r);  // Mark down 
	mid=(l+r)>>1;
	if(ur<=mid) return Query(lz,ul,ur,p);
	else if(ul>mid) return Query(rz,ul,ur,p);
	else
	{
		t1=Query(lz,ul,mid,p);
		t2=Query(rz,mid+1,ur,p);
		return (t1+t2)%MOD;
	}
}

int main()
{
	int n,m,i,l,r,c,op;

	while(scanf("%d%d",&n,&m)==2 && n+m)
	{
		Build(1,1,n);    //1 Root node 
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d%d",&op,&l,&r,&c);
			if(op<=3) Update(1,1,n,l,r,c,op);
			else
				printf("%I64d\n",Query(1,1,n,l,r,c)%MOD);
		}
	}
	return 0;
}

Copy

Copyright notice ： This article is the original article of the blogger . Blog , Do not reprint without permission .

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/116783.html Link to the original text ：https://javaforall.cn