线段树懒操作模板求调
  • 板块学术版
  • 楼主_sh1kong_
  • 当前回复15
  • 已保存回复15
  • 发布时间2023/1/26 12:11
  • 上次更新2023/10/24 03:03:33
查看原帖
线段树懒操作模板求调
823773
_sh1kong_楼主2023/1/26 12:11

rt , 想实现区间修改为v和区间查询最大值操作,可是有问题,有奆佬帮忙看看嘛

#include <iostream>

const int N = 1100;

using namespace std;//区间修改 && 查询区间最值 

int n, m;

int a[N];

struct node

{
	int l, r;
	int mx;
	int lz;//lazy
}tree[4 * N];

void build (int l, int r, int k)

{
	tree[k].l = l;
	tree[k].r = r;
	if (l == r) return ;
	int mid = (l + r) >> 1;
	build (l, mid, k << 1) , build (mid + 1, r, k << 1 | 1);
}

void lazy (int k, int v)

{
	tree[k].mx = v;
	tree[k].lz = v;
}

void pushdown (int k)

{
	lazy (k << 1, tree[k].lz);
	lazy (k << 1 | 1, tree[k].lz);
	tree[k].lz = -1;
}

void modify (int k, int x, int y, int v)//[l ... r]区间修改为v 

{
	int l = tree[k].l , r = tree[k].r;
	if (l >= x && r <= y) return lazy (k, v);//懒标记 && 标记数值 
	if (tree[k].lz != -1) pushdown (k);//懒标记下传给儿子节点
	int mid = (l + r) >> 1;
	if (x <= mid) modify (k << 1, x, y, v);
	if (y > mid) modify (k << 1 | 1, x, y, v);
	tree[k].mx = max (tree[k << 1].mx , tree[k << 1 | 1].mx);
}

int query (int k, int x, int y)

{
	int l = tree[k].l , r = tree[k].r;
	if (l >= x && r <= y) return tree[k].mx;
	if (tree[k].lz != -1) pushdown (k);
	int mid = (l + r) >> 1;
	int ans = 0;
	if (x <= mid) ans = max (ans , query (k << 1, x, y));
	if (y > mid) ans = max (ans , query (k << 1 | 1, x, y));
	return ans;/
}

int main()

{
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	build (1, n, 1);
	while (m --)
	{
		int opt, x, y;
		cin >> opt >> x >> y;
		if (opt == 1)
		{
			//区间修改
			int v;
			cin >> v;
			modify (1, x, y, v); 
		}
		else
		{
			//区间查询最值
			cout << query (1, x, y) << endl; 
		}
	}
}
2023/1/26 12:11
加载中...