求调线段树板子题。。。
  • 板块学术版
  • 楼主songziyu
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/9 22:42
  • 上次更新2024/11/10 10:17:25
查看原帖
求调线段树板子题。。。
543078
songziyu楼主2024/11/9 22:42

RT
本来想锻炼一下码力和处理细节的能力的,结果写挂了,已经调了2个月了。。。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int long long
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int N = 2e6 + 5;
int mod = 1e18 + 3;
const int inf = 2e18;
inline int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')
		{
			f = -1;
		}
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
	{
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
struct Node
{
	int l, r;
	long long w;//区间左端点、区间右端点、区间和
	int tag, tag2, tag3;//加法标记、乘法标记、赋值标记
	int maxx, minn;//最大、最小
} t[N << 2];
int a[N];
void push_up(int p)
{
	t[p].w = (t[ls].w + t[rs].w);
	t[p].minn = min(t[ls].minn, t[rs].minn);
	t[p].maxx = max(t[ls].maxx, t[rs].maxx);
}
void build(int p, int l, int r)//建树
{
	t[p].l = l, t[p].r = r;
	t[p].tag = 0, t[p].tag2 = 1, t[p].tag3 = -inf;
	if (l == r)
	{
		t[p].w = a[l], t[p].minn = a[l], t[p].maxx = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	push_up(p);
}
void cover_down(int p)//赋值标记下传
{
	if (t[p].tag3 != -inf)
	{
		t[ls].w = t[p].tag3, t[rs].w = t[p].tag3;
		t[ls].tag = 0, t[rs].tag = 0;
		t[ls].tag2 = 1, t[rs].tag2 = 1;
		t[ls].maxx = t[rs].maxx = t[p].tag3;
		t[ls].minn = t[rs].minn = t[p].tag3;
		t[ls].tag3 = t[p].tag3;
		t[rs].tag3 = t[p].tag3;
		t[p].tag3 = -inf;
	}
}
void sum_down(int p)//加法、乘法标记下传
{
	t[ls].w = (t[ls].w * t[p].tag2 + t[p].tag * (t[ls].r - t[ls].l + 1));
	t[rs].w = (t[rs].w * t[p].tag2 + t[p].tag * (t[rs].r - t[rs].l + 1));
	t[ls].tag2 = t[ls].tag2 * t[p].tag2;
	t[rs].tag2 = t[rs].tag2 * t[p].tag2;
	t[ls].tag = (t[ls].tag * t[p].tag2 + t[p].tag);
	t[rs].tag = (t[rs].tag * t[p].tag2 + t[p].tag);
	t[ls].minn = (t[p].tag2 * t[ls].minn + t[p].tag);
	t[rs].minn = (t[p].tag2 * t[rs].minn + t[p].tag);
	t[ls].maxx = (t[p].tag2 * t[ls].maxx + t[p].tag);
	t[rs].maxx = (t[p].tag2 * t[rs].maxx + t[p].tag);
	t[p].tag = 0, t[p].tag2 = 1;
}
void push_down(int p)
{
	cover_down(p), sum_down(p);
}
void mul(int p, int l, int r, int k)//区间乘
{
	if (l <= t[p].l && r >= t[p].r)
	{
		cover_down(p);
		t[p].maxx = t[p].maxx * k  ;
		t[p].minn = t[p].minn * k;
		t[p].w = t[p].w * k;
		t[p].tag = t[p].tag * k;
		t[p].tag2 = t[p].tag2 * k;
		return;
	}
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if (l <= mid)
	{
		mul(ls, l, r, k);
	}
	if (r > mid)
	{
		mul(rs, l, r, k);
	}
	push_up(p);
}
void add(int p, int l, int r, int k)//区间加
{
	if (l <= t[p].l && r >= t[p].r)
	{
		t[p].tag = (t[p].tag + k);
		t[p].maxx = (t[p].maxx + k);
		t[p].minn = (t[p].minn + k);
		t[p].w = (t[p].w + k * (t[p].r - t[p].l + 1));
		return;
	}
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if (l <= mid)
	{
		add(ls, l, r, k);
	}
	if (r > mid)
	{
		add(rs, l, r, k);
	}
	push_up(p);
}
int ask(int p, int l, int r)//区间求和
{
	if (l <= t[p].l && r >= t[p].r)
	{
		return t[p].w;
	}
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1, ans = 0;
	if (l <= mid)
	{
		ans = (ans + ask(ls, l, r));
	}
	if (r > mid)
	{
		ans = (ans + ask(rs, l, r));
	}
	return ans;
}
void add2(int p, int idx, int v)//单点加
{
	if (t[p].l == t[p].r && t[p].l == idx)
	{
		t[p].w = (t[p].w + v) ;
		return;
	}
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if (idx <= mid)
	{
		add2(ls, idx, v);
	}
	else
	{
		add2(rs, idx, v);
	}
	push_up(p);
}
int ask2(int p, int idx)//单点查询
{
	if (t[p].l == t[p].r)
	{
		return t[p].w;
	}
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if (idx <= mid)
	{
		return ask2(ls, idx);
	}
	else
	{
		return ask2(rs, idx);
	}
}
int askmin(int p, int l, int r)//区间min
{
	if (l <= t[p].l && r >= t[p].r)
	{
		return t[p].minn;
	}
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1, minnn = inf;
	if (l <= mid)
	{
		minnn = min(minnn, askmin(ls, l, r));
	}
	if (r > mid)
	{
		minnn = min(minnn, askmin(rs, l, r));
	}
	return minnn;
}
int askmax(int p, int l, int r)//区间max
{
	if (l <= t[p].l && r >= t[p].r)
	{
		return t[p].maxx;
	}
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1, maxxx = -inf;
	if (l <= mid)
	{
		maxxx = max(maxxx, askmax(ls, l, r));
	}
	if (r > mid)
	{
		maxxx = max(maxxx, askmax(rs, l, r));
	}
	return maxxx;
}
void modify(int p, int l, int r, int k)//区间赋值
{
	if (l <= t[p].l && r >= t[p].r)
	{
		t[p].w = k * (t[p].r - t[p].l + 1);
		t[p].tag = 0, t[p].tag2 = 1;
		t[p].maxx = k, t[p].minn = k;
		t[p].tag3 = k;
		return;
	}
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if (l <= mid)
	{
		modify(ls, l, r, k);
	}
	if (r > mid)
	{
		modify(rs, l, r, k);
	}
	push_up(p);
}
signed main()
{
	ios;
	int n = read(), m = read();
//	mod = read();
	for (int i = 1; i <= n; i++)
	{
		a[i] = read();
	}
	build(1, 1, n);
	for (int i = 1; i <= m; i++)
	{
		int op = read();
		if (op == 1) //区间加
		{
			int l = read(), r = read(), k = read();
			add(1, l, r, k);
		}
		if (op == 2) //区间乘
		{
			int l = read(), r = read(), k = read();
			mul(1, l, r, k);
		}
		if (op == 3) //区间查询
		{
			int l = read(), r = read();
			cout << ask(1, l, r)   << '\n';
		}
		if (op == 4) //区间max
		{
			int l = read(), r = read();
			cout << askmax(1, l, r)  << '\n';
		}
		if (op == 5) //区间min
		{
			int l = read(), r = read();
			cout << askmin(1, l, r) << '\n';
		}
		if (op == 6) //单点加
		{
			int x = read(), k = read();
			add2(1, x, k);
		}
		if (op == 7) //单点查询
		{
			int x = read();
			cout << ask2(1, x) << '\n';
		}
		if (op == 8) //区间修改
		{
			int l = read(), r = read(), x = read();
			modify(1, l, r, x);
		}
	}
	return 0;
}

现在已经通过了P3372,P3373,P3374,P3368,P1253啦!!!
但是在ask与modify函数兼容的时候好像有点问题。。。
hack:

6 6
1 1 4 5 1 4
3 1 4
8 1 6 10
3 1 2
7 2
7 1
3 3 6

期望输出:

11
20
10
10
40

实际输出:

11
10
10
10
20

救救孩子吧。。。

2024/11/9 22:42
加载中...