【[IOI2014]Wall 砖墙】

好像随便一卡就最优解了

malao告诉我这道题挺不错的，于是就去写了写

这两个操作很有灵性啊，感觉这么有特点的数大概是需要分块维护的吧

但是并没有什么区间查询，只是在最后输出整个序列

于是我们就直接用线段树维护

设置两个标记\(tag[0],tag[1]\)，分别表示对应区间的最小值和最大值

初始值我们分别设成\(-inf\)和\(inf\)

之后我们分别维护就好了

如果是\(1\)操作我们要把区间的最小值更新，但是如果原来区间的最小值大于当前的值，那么就不更新

同时如果这个区间的最大值比需要更新的值还小，那么最大值也一起更新

操作\(2\)还有标记下放同理

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#define re register

#define maxn 2000005

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define INF 100002

int l[maxn<<2],r[maxn<<2],tag[2][maxn<<2];

int n,Q;

void write(int x)

{

	if(x>9) write(x/10);

	putchar(x%10+48);

}

inline int read()

{

    char c=getchar();

    int x=0;

    while(c<'0'||c>'9') c=getchar();

    while(c>='0'&&c<='9')

      x=(x<<3)+(x<<1)+c-48,c=getchar();

    return x;

}

void build(int x,int y,int i)

{

	l[i]=x,r[i]=y;

	if(x==y) return;

	int mid=x+y>>1;

	build(x,mid,i<<1),build(mid+1,y,i<<1|1);

	tag[1][i]=INF,tag[0][i]=-INF;

}

inline void pushdown(int i)

{

	if(tag[0][i]!=-INF)

	{

		tag[0][i<<1]=max(tag[0][i],tag[0][i<<1]);

		tag[1][i<<1]=max(tag[1][i<<1],tag[0][i]);

		tag[0][i<<1|1]=max(tag[0][i],tag[0][i<<1|1]);

		tag[1][i<<1|1]=max(tag[1][i<<1|1],tag[0][i]);

		tag[0][i]=-INF;

	}

	if(tag[1][i]!=INF)

	{

		tag[1][i<<1]=min(tag[1][i],tag[1][i<<1]);

		tag[0][i<<1]=min(tag[0][i<<1],tag[1][i]);

		tag[1][i<<1|1]=min(tag[1][i<<1|1],tag[1][i]);

		tag[0][i<<1|1]=min(tag[0][i<<1|1],tag[1][i]);

		tag[1][i]=INF;

	}

}

void change(int op,int val,int x,int y,int i)

{

	if(x<=l[i]&&y>=r[i])

	{

		if(op)

		{

			if(val<tag[op][i]) tag[op][i]=val;

			if(tag[0][i]>val) tag[0][i]=val;

		}

		if(!op)

		{

			if(val>tag[op][i]) tag[op][i]=val;

			if(tag[1][i]<val) tag[1][i]=val;

		}

		return;

	}

	pushdown(i);

	int mid=l[i]+r[i]>>1;

	if(y<=mid) change(op,val,x,y,i<<1);

	else if(x>mid) change(op,val,x,y,i<<1|1);

	else change(op,val,x,y,i<<1),change(op,val,x,y,i<<1|1);

}

void print(int i)

{

	if(l[i]==r[i])

	{

		write(tag[0][i]);

		putchar(10);

		return;

	}

	pushdown(i);

	print(i<<1);

	print(i<<1|1);

}

int main()

{

	n=read(),Q=read();

	build(0,n-1,1);

	int opt,x,y,h;

	while(Q--)

	{

		opt=read(),x=read(),y=read(),h=read();

		change(opt-1,h,x,y,1);

	}

	print(1);

	return 0;

}

巴特西

【[IOI2014]Wall 砖墙】

最新文章

热门文章