【UOJ25】【IOI2014】Wall | q234rty's Blog

线段树即可。

We need to build a wall!（雾）

标记：表示将小于的数变为，大于的数变为，其余的数不变。显然对取min就是，对取max就是。

其中先执行，后执行。

直接上线段树，最后dfs一遍算出答案即可。

Code

#include <bits/stdc++.h>
using namespace std;
const int INF=100000;
struct tag{
	int l,r;
	tag():l(0),r(INF){}
	tag(int x):l(x),r(x){}
	tag(int l,int r):l(l),r(r){}
	tag operator +(const tag& rhs)const{
		if (r<rhs.l)
			return rhs.l;
		if (rhs.r<l)
			return rhs.r;
		return tag(max(l,rhs.l),min(r,rhs.r));
	}
	tag& operator +=(const tag& rhs){
		return *this=*this+rhs;
	}
};
const int maxn=2000001;
struct segtree{
	int n;
	tag tagv[maxn*4];
	void build(int o,int l,int r){
		if (l==r){
			tagv[o]=0;
			return;
		}
		int mid=(l+r)/2;
		build(o*2,l,mid);
		build(o*2+1,mid+1,r);
	}
	void init(int n){
		this->n=n;
		build(1,0,n-1);
	}
	void pushdown(int o){
		tagv[o*2]+=tagv[o];
		tagv[o*2+1]+=tagv[o];
		tagv[o]=tag();
	}
	int ul,ur;
	tag v;
	void update(int o,int l,int r){
		if (ul<=l && ur>=r){
			tagv[o]+=v;
			return;
		}
		int mid=(l+r)/2;
		pushdown(o);
		if (ul<=mid)
			update(o*2,l,mid);
		if (ur>mid)
			update(o*2+1,mid+1,r);
	}
	void update(int op,int l,int r,int h){
		ul=l,ur=r;
		v=op==1?tag(h,INF):tag(0,h);
		update(1,0,n-1);
	}
	int* ans;
	void dfs(int o,int l,int r,tag t=tag()){
		if (l==r){
			ans[l]=(tagv[o]+t).l;
			return;
		}
		int mid=(l+r)/2;
		tag w=tagv[o]+t;
		dfs(o*2,l,mid,w);
		dfs(o*2+1,mid+1,r,w);
	}
	void query(int *ans){
		this->ans=ans;
		dfs(1,0,n-1);
	}
}t;
void buildWall(int n,int m,int *op,int *l,int *r,int *h,int *ans){
	t.init(n);
	for(int i=0;i<m;i++)
		t.update(op[i],l[i],r[i],h[i]);
	t.query(ans);
}

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2017/03/28/uoj25/