TLE 90 pts on #10

TLE记录

#include <bits/stdc++.h>

#define int long long 

#define root 1,n,1

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

using namespace std;

const int N=1e6+10;

struct Node{
	int l,r;
	int maxx;
	int tag_plus;
	int tag_equiv;
	Node() {
		l=r=tag_plus=tag_equiv=0;
		maxx=INT_MIN;
		tag_equiv=INT_MIN;
	}
}z[N+N<<2];

Node operator +(const Node& a,const Node& b){
	Node c;
	c.l=a.l;
	c.r=b.r;
	c.maxx=max(a.maxx,b.maxx);
	return c;
}

int a[N];
int n,q;

void build(int l,int r,int rt){
	if(l==r){
		z[rt].l=z[rt].r=l;
		z[rt].maxx=a[l];
		return;
	}
	int m=(l+r)>>1;
	build(lson);
	build(rson);
	z[rt]=z[rt<<1]+z[rt<<1|1];
}

void color_plus(int rt,int v){
	z[rt].tag_plus+=v;
	z[rt].maxx+=v;
}

void color_equal(int rt,int v){
	z[rt].tag_plus=0;
	z[rt].tag_equiv=v;
	z[rt].maxx=v;
	z[rt].tag_plus=0;
}

void push_col_plus(int rt){
	if(z[rt].tag_plus!=0){
		int tag_plus=z[rt].tag_plus;
		color_plus(rt<<1,tag_plus);
		color_plus(rt<<1|1,tag_plus);
		z[rt].tag_plus=0;
	}
}

void push_col_equal(int rt){
	if(z[rt].tag_equiv!=INT_MIN){
		int tag_equal=z[rt].tag_equiv;
		color_equal(rt<<1,tag_equal);
		color_equal(rt<<1|1,tag_equal);
		z[rt].tag_equiv=INT_MIN;	
	}
}

void modify_plus(int l,int r,int rt,int nowl,int nowr,int v){
	if(l>=nowl&&r<=nowr){
		push_col_equal(rt);
		color_plus(rt,v);
		return;
	}
	push_col_equal(rt);
	push_col_plus(rt);
	int m=(l+r)>>1;
	if(nowl<=m){
		modify_plus(lson,nowl,nowr,v);
	}
	if(nowr>m){
		modify_plus(rson,nowl,nowr,v);
	}
	z[rt]=z[rt<<1]+z[rt<<1|1];
}

void modify_equal(int l,int r,int rt,int nowl,int nowr,int v){
	if(l>=nowl&&r<=nowr){
		push_col_equal(rt);
		color_equal(rt,v);
		return;
	}
	push_col_equal(rt);
	push_col_plus(rt);
	int m=(l+r)>>1;
	if(nowl<=m){
		modify_equal(lson,nowl,nowr,v);
	}
	if(nowr>m){
		modify_equal(rson,nowl,nowr,v);
	}	
	z[rt]=z[rt<<1]+z[rt<<1|1];
}
Node query(int l,int r,int rt,int nowl,int nowr){
	if(l>=nowl&&r<=nowr){
		return z[rt];
	}
	push_col_equal(rt);
	push_col_plus(rt);
	int m=(l+r)>>1;
	if(nowl<=m&&nowr>m){
		return query(lson,nowl,nowr)+query(rson,nowl,nowr);
	}
	else if(nowl<=m&&nowr<=m){
		return query(lson,nowl,nowr);
	}
	else{
		return query(rson,nowl,nowr);
	}
}

signed main() {
	cin>>n>>q;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	build(root);
	while(q--){
		int opt;
		cin>>opt;
		if(opt==1){
			int l,r,v;
			cin>>l>>r>>v;
			modify_equal(root,l,r,v);
		}
		else if(opt==2){
			int l,r,v;
			cin>>l>>r>>v;
			modify_plus(root,l,r,v);
		}
		else{
			int l,r;
			cin>>l>>r;
			cout<<query(root,l,r).maxx<<"\n";
		}
	}
	return 0;
}