有点玄乎,区间长度赋值成负数了还能过
查看原帖
有点玄乎,区间长度赋值成负数了还能过
732906
4BboIkm7h楼主2024/11/27 15:17

请问有没有大佬来给我解释一下,建树部分我手误把区间长度赋成了 l-r+1 ,本应是r-l+1,这样所有非叶子区间长度不都变成负数了吗?为什么也没影响到pushuppushdown部分呢?
有误代码的AC记录
下面是那一次提交时的代码,将此处更正后仍然能正常AC

#include<bits/stdc++.h>
#define ls p << 1
#define rs p << 1 | 1
using namespace std;
const int N = 2e5 + 10;
int n, m;
struct node {
	int l, r, tag, sum1, lmax0, rmax0, max0, len;
} t[N << 2];
void pushup(int p) {
	t[p].sum1 = t[ls].sum1 + t[rs].sum1;
	t[p].len = t[ls].len + t[rs].len;
	if (t[ls].lmax0 == t[ls].len) t[p].lmax0 = t[ls].len + t[rs].lmax0;
	else t[p].lmax0 = t[ls].lmax0;
	if (t[rs].rmax0 == t[rs].len) t[p].rmax0 = t[ls].rmax0 + t[rs].len;
	else t[p].rmax0 = t[rs].rmax0;
	t[p].max0 = max(max(t[ls].max0, t[rs].max0), t[ls].rmax0 + t[rs].lmax0);
}
void build(int p, int l, int r) {
	t[p].l = l;
	t[p].r = r;
	t[p].tag = -1;
	t[p].len = l - r + 1;//此处区间长度我打成了“左 - 右 + 1”
	if (l == r) {
		t[p].sum1 = 1;
		t[p].lmax0 = t[p].rmax0 = 0;
		return;
	}
	int mid = (l + r) >> 1;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	pushup(p);
}
void down1(int p){
	t[p].tag = 1;
	t[p].max0 = t[p].lmax0 = t[p].rmax0 = 0;
	t[p].sum1 = t[p].len;
}
void down0(int p){
	t[p].tag = 0;
	t[p].max0 = t[p].lmax0 = t[p].rmax0 = t[p].len;
	t[p].sum1 = 0;
}
void pushdown(int p) {
	//填上
	if (t[p].tag == 1) {
		down1(ls);
		down1(rs);
	}
	//挖走
	if (t[p].tag == 0) {
		down0(ls);
		down0(rs);
	}
	t[p].tag = -1;
}
void dig(int p, int L, int R) {
	if (L <= t[p].l && t[p].r <= R) {
		down0(p);
		return;
	}
	pushdown(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if (L <= mid) dig(ls, L, R);
	if (R > mid) dig(rs, L, R);
	pushup(p);
}
void fil(int p, int L, int R) {
	if (L <= t[p].l && t[p].r <= R) {
		down1(p);
		return;
	}
	pushdown(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if (L <= mid) fil(ls, L, R);
	if (R > mid) fil(rs, L, R);
	pushup(p);
}
int query_sum1(int p, int L, int R) {
	if (L <= t[p].l && t[p].r <= R) return t[p].sum1;
	pushdown(p);
	int mid = (t[p].l + t[p].r) >> 1, res = 0;
	if (L <= mid) res += query_sum1(ls, L, R);
	if (R > mid) res += query_sum1(rs, L, R);
	return res;
}
int query_sum0(int p, int L, int R) {
	if (L <= t[p].l && t[p].r <= R) return t[p].len - t[p].sum1;
	pushdown(p);
	int mid = (t[p].l + t[p].r) >> 1, res = 0;
	if (L <= mid) res += query_sum0(ls, L, R);
	if (R > mid) res += query_sum0(rs, L, R);
	return res;
}
int query_max0(int p, int L, int R) {
	if (L <= t[p].l && t[p].r <= R) return t[p].max0;
	pushdown(p);
	if(t[ls].r < L) return query_max0(rs, L, R);
	if(t[rs].l > R) return query_max0(ls, L, R);
	return max(max(query_max0(ls, L, R), query_max0(rs, L, R)), min(t[ls].rmax0, t[rs].l - L) + min(t[rs].lmax0, R - t[ls].r));
}
void fix(int L0, int R0, int L1, int R1) {
	int s1 = query_sum1(1, L0, R0);
	if (s1 == 0) return;
	dig(1, L0, R0);
	int l = L1, r = R1 + 1;
	while (l + 1 < r) {
		int mid = (l + r) >> 1;
		if (query_sum0(1, L1, mid) <= s1) l = mid;
		else r = mid;
	}
	fil(1, L1, l);
}
int main() {
	scanf("%d%d", &n, &m);
	build(1, 1, n);
	int op, l, r, l0, r0, l1, r1;
	while (m--) {
		scanf("%d", &op);
		if (op == 0) {
			scanf("%d%d", &l, &r);
			dig(1, l, r);
		}
		if (op == 1) {
			scanf("%d%d%d%d", &l0, &r0, &l1, &r1);
			fix(l0, r0, l1, r1);
		}
		if (op == 2) {
			scanf("%d%d", &l, &r);
			printf("%d\n", query_max0(1, l, r));
		}
	}
	return 0;
}
2024/11/27 15:17
加载中...