[IOI2014]Wall

题目大意：

给你一个长度为\(n(n\le2\times10^6)\)的数列，初始全为\(0\)。\(m(m\le5\times10^5)\)次操作，每次让区间\([l_i,r_i]\)对\(h_i\)取\(\max/\min\)，求最后每一个数的值。

思路：

线段树维护区间内数的上界和下界。

源代码：

#include<climits>

#include<algorithm>

#include"lib1895.h"

const int N=2e6+1;

class SegmentTree {

	#define _left <<1

	#define _right <<1|1

	#define mid ((b+e)>>1)

	private:

		int u[N<<2],d[N<<2];

		void upd1(const int &p,const int &x) {

			if(u[p]!=INT_MAX&&d[p]>=x) return;

			d[p]=std::max(d[p],x);

			u[p]=std::max(u[p],x);

		}

		void upd2(const int &p,const int &x) {

			if(d[p]!=INT_MIN&&u[p]<=x) return;

			u[p]=std::min(u[p],x);

			d[p]=std::min(d[p],x);

		}

		void push_down(const int &p) {

			if(d[p]!=INT_MIN) {

				upd1(p _left,d[p]);

				upd1(p _right,d[p]);

				d[p]=INT_MIN;

			}

			if(u[p]!=INT_MAX) {

				upd2(p _left,u[p]);

				upd2(p _right,u[p]);

				u[p]=INT_MAX;

			}

		}

	public:

		void build(const int &p,const int &b,const int &e) {

			u[p]=INT_MAX;

			d[p]=INT_MIN;

			if(b==e) return;

			build(p _left,b,mid);

			build(p _right,mid+1,e);

 		}

		void modify1(const int &p,const int &b,const int &e,const int &l,const int &r,const int &x) {

			if(b==l&&e==r) {

				upd1(p,x);

				return;

			}

			push_down(p);

			if(l<=mid) modify1(p _left,b,mid,l,std::min(mid,r),x);

			if(r>mid) modify1(p _right,mid+1,e,std::max(mid+1,l),r,x);

		}

		void modify2(const int &p,const int &b,const int &e,const int &l,const int &r,const int &x) {

			if(b==l&&e==r) {

				upd2(p,x);

				return;

			}

			push_down(p);

			if(l<=mid) modify2(p _left,b,mid,l,std::min(mid,r),x);

			if(r>mid) modify2(p _right,mid+1,e,std::max(mid+1,l),r,x);

		}

		int query(const int &p,const int &b,const int &e,const int &x) {

			if(b==e) {

				int ret=0;

				ret=std::max(ret,d[p]);

				ret=std::min(ret,u[p]);

				return ret;

			}

			int ret=0;

			push_down(p);

			if(x<=mid) ret=query(p _left,b,mid,x);

			if(x>mid) ret=query(p _right,mid+1,e,x);

			return ret;

		}

	#undef _left

	#undef _right

	#undef mid

};

SegmentTree sgt;

void buildWall(int n,int m,int opt[],int l[],int r[],int h[],int ans[]) {

	sgt.build(1,1,n);

	for(register int i=0;i<m;i++) l[i]++;

	for(register int i=0;i<m;i++) r[i]++;

	for(register int i=0;i<m;i++) {

		if(opt[i]==1) sgt.modify1(1,1,n,l[i],r[i],h[i]);

		if(opt[i]==2) sgt.modify2(1,1,n,l[i],r[i],h[i]);

	}

	for(register int i=0;i<n;i++) {

		ans[i]=sgt.query(1,1,n,i+1);

	}

}