请问有没有大佬来给我解释一下,建树部分我手误把区间长度赋成了
l-r+1
,本应是r-l+1,这样所有非叶子区间长度不都变成负数了吗?为什么也没影响到pushup和pushdown部分呢?
有误代码的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;
}