P4560 [IOI2014] Wall 砖墙

*原题链接*

做法：线段树

一道比较基础的线段树练手题，区间赋值，在修改时加些判断剪枝。

对于add操作，如果此时区间里的最小值都大于等于h的话，就没必要操作，如果最大值都小于h的话，就直接区间赋值为h。对于remove操作同理。

时间复杂度大致为，实际会比这个要大一些。

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10,INF=0x3f3f3f3f;

int n,k;

struct node{
	int l,r;
	int mn,mx,tag;
}tr[N*4];

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

void pushdown(int u){
	if(tr[u].tag==INF) return;
	tr[u<<1].mn=tr[u<<1].mx=tr[u<<1].tag=tr[u].tag;
	tr[u<<1|1].mn=tr[u<<1|1].mx=tr[u<<1|1].tag=tr[u].tag;
	tr[u].tag=INF;
}

void pushup(int u){
	tr[u].mn=min(tr[u<<1].mn,tr[u<<1|1].mn);
	tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);
}

void build(int u,int l,int r){
	if(l==r) tr[u]={l,r,0,0,INF};
	else{
		tr[u].l=l,tr[u].r=r;
		int mid=(l+r)>>1;
		build(u<<1,l,mid),build(u<<1|1,mid+1,r);
		pushup(u);
	}
}

void modify1(int u,int l,int r,int x){//Add
	if(tr[u].l>=l&&tr[u].r<=r){
		if(tr[u].mn>=x) return;
		if(tr[u].mx<=x){
			tr[u].mn=tr[u].mx=tr[u].tag=x;
			return;
		}
	}
	pushdown(u);
	int mid=(tr[u].l+tr[u].r)>>1;
	if(l<=mid) modify1(u<<1,l,r,x);
	if(r>mid) modify1(u<<1|1,l,r,x);
	pushup(u);
}

void modify2(int u,int l,int r,int x){//Remove
	if(tr[u].l>=l&&tr[u].r<=r){
		if(tr[u].mx<=x) return;
		if(tr[u].mn>=x){
			tr[u].mn=tr[u].mx=tr[u].tag=x;
			return;
		}
	}
	pushdown(u);
	int mid=(tr[u].l+tr[u].r)>>1;
	if(l<=mid) modify2(u<<1,l,r,x);
	if(r>mid) modify2(u<<1|1,l,r,x);
	pushup(u);
}

int query(int u,int x){
	if(tr[u].l==x&&tr[u].r==x) return tr[u].mx;
	pushdown(u);
	int mid=(tr[u].l+tr[u].r)>>1;
	if(x<=mid) return query(u<<1,x);
	return query(u<<1|1,x);
}

int main(){
	
	n=read(),k=read();
	build(1,1,n);
	while(k--){
		int opt=read(),l=read(),r=read(),h=read();
		l++,r++;
		if(opt==1) modify1(1,l,r,h);
		else modify2(1,l,r,h);
	}
	for(int i=1;i<=n;i++) cout<<query(1,i)<<endl;
	
	return 0;
}