A5903.涂色 题解

/*
-----------fjn-----------
*/
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define F (100000007)
#define MAXN (1000000+5)
typedef long long ll;
ll n,m;
ll arr[MAXN]; 
struct node{
	ll l,r,w;//左儿子  右儿子  值
	ll lg;//懒惰标记  lazytag
};
node tree[4*MAXN];//线段树需要开辟四倍空间
void pushup(int p){
	tree[p].w=tree[p*2].w+tree[p*2+1].w;
} 
void js(ll p,ll l,ll r){//build  根节点  左节点  右节点 
	tree[p].l=l;//存入左节点(结点) 
	tree[p].r=r;//存入右节点
	if(l==r){
		tree[p].w=0;
		return ;
	} 
	int mid=(l+r)/2;//切割一半 
	js(p*2,l,mid);//构建左子树 
	js(p*2+1,mid+1,r);//构建右子树 
}
void lan(int p){//pushdown 懒标记下传 
	if(tree[p].lg){//当前这个位置是存在懒标记的 
		tree[p*2  ].w=tree[p].lg;//左区间更新
		tree[p*2+1].w=tree[p].lg;//右区间更新
		tree[p*2  ].lg=tree[p].lg;
		tree[p*2+1].lg=tree[p].lg;
		tree[p].lg=0;//清空 
	} 
}
ll cx(int p,int x,int y){//query 区间查询 
	if(x<=tree[p].l&&y>=tree[p].r){//需要查询的范围包含了p下标的所有 
		return tree[p].w;//返回值 
	}
	lan(p);
	int mid =(tree[p].l+tree[p].r)/2;//二分
	int flag;
	if(x<=mid)flag=cx(p*2,x,y);
	if(y>mid)flag=cx(p*2+1,x,y);
	return flag; 
}
void xg(ll p,ll x,ll y,ll z){//update  根 需要修改的左端点  需要修改的右端点  修改的值 
//	cout<<"==="<<p<<"=="<<tree[p].l<<"=="<<tree[p].r<<" "<< x<<" "<<y<<" "<<z<<endl;
	if(x<=tree[p].l&&y>=tree[p].r){//需要查询的范围包含了p下标的所有 
		tree[p].w=z;//值 
		tree[p].lg=z;//懒标记标记
		return ;
	}
	lan(p);
	int mid =(tree[p].l+tree[p].r)/2;//二分
	if(x<=mid)xg(p*2,x,y,z);//如果需要修改的范围正好包含
	if(y>mid) xg(p*2+1,x,y,z); //y>=mid+1 如果需要修改的范围正好包含
} 
int main(){
	cin>>n>>m;
	js(1,1,n);
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
//		cout<<"--"<<endl;
		xg(1,x,y,z);
//		for(int i=1;i<=n;i++){
//			cout<<cx(1,i,i)<<" ";
//		}
//		cout<<endl;
	}
	
	for(int i=1;i<=n;i++){
		cout<<cx(1,i,i)<<" ";
	}
	
	
	return 0;
}