0pts求调!
查看原帖
0pts求调!
1076915
zhongjisailuo楼主2024/11/30 17:58
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
struct node
{
	int l,r;
	int low,high;
}t[4 * N];
void makeadd(int p,int h)
{
	t[p].low=max(t[p].low,h);
	t[p].high=max(t[p].high,h);
}
void makerem(int p,int h)
{
	t[p].low=min(t[p].low,h);
	t[p].high=min(t[p].high,h);
}
void pushdown(int p)
{
	makeadd(p * 2,t[p].low);
	makeadd(p * 2 + 1,t[p].low);
	
	makerem(p * 2,t[p].high);
	makerem(p * 2 + 1,t[p].high);
	t[p].low = 0;
	t[p].high = 100000;
} 
void build(int p,int l,int r)
{
	t[p].l = l;
	t[p].r = r;
	t[p].low = 0;
	t[p].high = 100000;
	if(l == r)
	{
		return ;
	}
	int mid = l + r >> 1;
	build(p * 2,l,mid);
	build(p * 2 + 1,mid + 1,r);
}

void update(int p,int l,int r,int h,int op)//加,乘 
{
	if(t[p].l == l&&t[p].r == r)
	{
		if(op == 1)
		{
			makeadd(p,h);
		}
		else
		{
			makerem(p,h);
		}
		return;
	}
	//下放标记 
	pushdown(p);
	int mid = t[p].l + t[p].r >> 1;
	if(r <= mid)
	{
		update(p * 2,l,r,h,op);
	}
	else if(l > mid)
	{
		update(p * 2 + 1,l,r,h,op);
	}
	else
	{
		update(p * 2,l,mid,h,op);
		update(p * 2 + 1,mid + 1,r,h,op);

	}
}

void query(int p,int l,int r)
{
	if(l == r)
	{
		cout<<max(0,max(t[p].low,t[p].high))<<"\n";
		return ;
	}
	//下放
	pushdown(p);
	int mid = t[p].l + t[p].r >> 1;
	if(r <= mid)
	{
		return query(p * 2,l,r);
	}
	else if(l>mid)
	{
		query(p * 2 + 1,l,r);
	}
	else
	{
		query(p * 2,l,mid);
		query(p * 2 + 1,mid + 1,r);
	} 
} 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0); 
	int n,k;
	cin>>n>>k;
	int op,x,y,h;
	build(1,1,n);
	while(k--)
	{
		cin>>op>>x>>y>>h;
		x+=1;
		y+=1;
		update(1,x,y,h,op);
	}
	return 0;
}
2024/11/30 17:58
加载中...