线段树 0 分求调

P2572 [SCOI2010] 序列操作

幸存者 @ 2022-07-07 15:47:04

rt，没过样例

#include <bits/stdc++.h>
using namespace std;
int w1[400010], w2[400010], w3[400010], w4[400010], b1[400010], b2[400010], b3[400010], b4[400010];
bool a[100010], lzy1[400010], lzy2[400010], lzy3[400010];
void maketag1(int u, int len)
{
    lzy1[u] = 1;
    lzy2[u] = lzy3[u] = w1[u] = w2[u] = w3[u] = w4[u] = 0;
    b1[u] = b2[u] = b3[u] = b4[u] = len;
}
void maketag2(int u, int len)
{
    lzy2[u] = 1;
    lzy1[u] = lzy3[u] = b1[u] = b2[u] = b3[u] = b4[u] = 0;
    w1[u] = w2[u] = w3[u] = w4[u] = len;
}
void maketag3(int u, int len)
{
    lzy3[u] ^= 1;
    w1[u] = len - w1[u];
    swap(w2[u], b2[u]);
    swap(w3[u], b3[u]);
    swap(w4[u], b4[u]);
}
void pushdown(int u, int L, int R)
{
    int M = L + R >> 1;
    if (lzy1[u])
    {
        maketag1(u << 1, M - L + 1);
        maketag1(u << 1 | 1, R - M);
    }
    if (lzy2[u])
    {
        maketag2(u << 1, M - L + 1);
        maketag2(u << 1 | 1, R - M);
    }
    if (lzy3[u])
    {
        maketag3(u << 1, M - L + 1);
        maketag3(u << 1 | 1, R - M);
    }
    lzy1[u] = lzy2[u] = lzy3[u] = 0;
}
void pushup(int u, int len)
{
    w1[u] = w1[u << 1] + w1[u << 1 | 1];
    w2[u] = max(max(w2[u << 1], w2[u << 1 | 1]), w3[u << 1] + w4[u << 1 | 1]);
    if (w3[u << 1 | 1] == len) w3[u] = w3[u << 1] + len;
    else w3[u] = max(w3[u << 1], w3[u << 1 | 1]);
    if (w4[u << 1] == len) w4[u] = w4[u << 1 | 1] + len;
    else w4[u] = max(w4[u << 1], w4[u << 1 | 1]);
    b1[u] = b1[u << 1] + b1[u << 1 | 1];
    w2[u] = max(max(w2[u << 1], w2[u << 1 | 1]), w3[u << 1] + w4[u << 1 | 1]);
    if (b3[u << 1 | 1] == len) b3[u] = b3[u << 1] + len;
    else b3[u] = max(b3[u << 1], b3[u << 1 | 1]);
    if (b4[u << 1] == len) b4[u] = b4[u << 1 | 1] + len;
    else b4[u] = max(b4[u << 1], b4[u << 1 | 1]);
}
void build(int u, int L, int R)
{
    if (L == R)
    {
        w1[u] = a[L];
        b1[u] = !a[L];
        return;
    }
    int M = L + R >> 1;
    build(u << 1, L, M);
    build(u << 1 | 1, M + 1, R);
    pushup(u, R - L + 1);
}
void update1(int u, int L, int R, int l, int r)
{
    if (l <= L && R <= r) maketag1(u, R - L + 1);
    else if (L <= r && R >= l)
    {
        int M = L + R >> 1;
        pushdown(u, L, R);
        update1(u << 1, L, M, l, r);
        update1(u << 1 | 1, M + 1, R, l, r);
        pushup(u, R - L + 1);
    }
}
void update2(int u, int L, int R, int l, int r)
{
    if (l <= L && R <= r) maketag2(u, R - L + 1);
    else if (L <= r && R >= l)
    {
        int M = L + R >> 1;
        pushdown(u, L, R);
        update2(u << 1, L, M, l, r);
        update2(u << 1 | 1, M + 1, R, l, r);
        pushup(u, R - L + 1);
    }
}
void update3(int u, int L, int R, int l, int r)
{
    if (l <= L && R <= r) maketag3(u, R - L + 1);
    else if (L <= r && R >= l)
    {
        int M = L + R >> 1;
        pushdown(u, L, R);
        update3(u << 1, L, M, l, r);
        update3(u << 1 | 1, M + 1, R, l, r);
        pushup(u, R - L + 1);
    }
}
int query1(int u, int L, int R, int l, int r)
{
    if (l <= L && R <= r) return w1[u];
    else if (L <= r && R >= l)
    {
        int M = L + R >> 1;
        pushdown(u, L, R);
        return query1(u << 1, L, M, l, r) + query1(u << 1 | 1, M + 1, R, l, r);
    }
    else return 0;
}
int query3(int u, int L, int R, int l, int r)
{
    if (l <= L && R <= r) return w3[u];
    else if (L <= r && R >= l)
    {
        int M = L + R >> 1;
        pushdown(u, L, R);
        int x = query3(u << 1, L, M, l, r), y = query3(u << 1 | 1, M + 1, R, l, r);
        return (y == R - M ? x + y : max(x, y));
    }
    else return 0;
}
int query4(int u, int L, int R, int l, int r)
{
    if (l <= L && R <= r) return w3[u];
    else if (L <= r && R >= l)
    {
        int M = L + R >> 1;
        pushdown(u, L, R);
        int x = query4(u << 1, L, M, l, r), y = query4(u << 1 | 1, M + 1, R, l, r);
        return (x == M - L + 1 ? x + y : max(x, y));
    }
    else return 0;
}
int query2(int u, int L, int R, int l, int r)
{
    if (l <= L && R <= r) return w2[u];
    else if (L <= r && R >= l)
    {
        int M = L + R >> 1;
        pushdown(u, L, R);
        return max(max(query2(u << 1, L, M, l, r), query2(u << 1 | 1, M + 1, R, l, r)), query3(u << 1, L, M, l, r) + query4(u << 1 | 1, M + 1, R, l, r));
    }
    else return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (m--)
    {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 0) update1(1, 1, n, l + 1, r + 1);
        else if (op == 1) update2(1, 1, n, l + 1, r + 1);
        else if (op == 2) update3(1, 1, n, l + 1, r + 1);
        else if (op == 3) cout << query1(1, 1, n, l + 1, r + 1) << endl;
        else cout << query2(1, 1, n, l + 1, r + 1) << endl;
    }
    return 0;
}

样例正确输出：

5
2
6
5

我的代码输出：


5
2
4
5
``

by 幸存者 @ 2022-07-07 15:47:56

等一下，我的代码输出应该是：

5
2
4
5

by Rubidium_Chloride @ 2022-07-07 15:55:14

@幸存者 我怀疑啊，你这个 pushup 写挂了。

比如这里

if (w3[u << 1 | 1] == len) w3[u] = w3[u << 1] + len;

by 幸存者 @ 2022-07-07 15:56:40

改了一下代码：

#include <bits/stdc++.h>
using namespace std;
int w1[400010], w2[400010], w3[400010], w4[400010], b1[400010], b2[400010], b3[400010], b4[400010];
bool a[100010], lzy1[400010], lzy2[400010], lzy3[400010];
void maketag1(int u, int len)
{
    lzy1[u] = 1;
    lzy2[u] = lzy3[u] = w1[u] = w2[u] = w3[u] = w4[u] = 0;
    b1[u] = b2[u] = b3[u] = b4[u] = len;
}
void maketag2(int u, int len)
{
    lzy2[u] = 1;
    lzy1[u] = lzy3[u] = b1[u] = b2[u] = b3[u] = b4[u] = 0;
    w1[u] = w2[u] = w3[u] = w4[u] = len;
}
void maketag3(int u, int len)
{
    lzy3[u] ^= 1;
    w1[u] = len - w1[u];
    swap(w2[u], b2[u]);
    swap(w3[u], b3[u]);
    swap(w4[u], b4[u]);
}
void pushdown(int u, int L, int R)
{
    int M = L + R >> 1;
    if (lzy1[u])
    {
        maketag1(u << 1, M - L + 1);
        maketag1(u << 1 | 1, R - M);
    }
    if (lzy2[u])
    {
        maketag2(u << 1, M - L + 1);
        maketag2(u << 1 | 1, R - M);
    }
    if (lzy3[u])
    {
        maketag3(u << 1, M - L + 1);
        maketag3(u << 1 | 1, R - M);
    }
    lzy1[u] = lzy2[u] = lzy3[u] = 0;
}
void pushup(int u, int L, int R)
{
    int M = L + R >> 1;
    w1[u] = w1[u << 1] + w1[u << 1 | 1];
    w2[u] = max(max(w2[u << 1], w2[u << 1 | 1]), w3[u << 1] + w4[u << 1 | 1]);
    if (w3[u << 1 | 1] == R - M) w3[u] = w3[u << 1] + w3[u << 1 | 1];
    else w3[u] = max(w3[u << 1], w3[u << 1 | 1]);
    if (w4[u << 1] == M - L + 1) w4[u] = w4[u << 1] + w4[u << 1 | 1];
    else w4[u] = max(w4[u << 1], w4[u << 1 | 1]);
    b1[u] = b1[u << 1] + b1[u << 1 | 1];
    b2[u] = max(max(b2[u << 1], b2[u << 1 | 1]), b3[u << 1] + b4[u << 1 | 1]);
    if (b3[u << 1 | 1] == R - M) b3[u] = b3[u << 1] + b3[u << 1 | 1];
    else b3[u] = max(b3[u << 1], b3[u << 1 | 1]);
    if (b4[u << 1] == M - L + 1) b4[u] = b4[u << 1] + b4[u << 1 | 1];
    else b4[u] = max(b4[u << 1], b4[u << 1 | 1]);
}
void build(int u, int L, int R)
{
    if (L == R)
    {
        w1[u] = a[L];
        b1[u] = !a[L];
        return;
    }
    int M = L + R >> 1;
    build(u << 1, L, M);
    build(u << 1 | 1, M + 1, R);
    pushup(u, L, R);
}
void update1(int u, int L, int R, int l, int r)
{
    if (l <= L && R <= r) maketag1(u, R - L + 1);
    else if (L <= r && R >= l)
    {
        int M = L + R >> 1;
        pushdown(u, L, R);
        update1(u << 1, L, M, l, r);
        update1(u << 1 | 1, M + 1, R, l, r);
        pushup(u, L, R);
    }
}
void update2(int u, int L, int R, int l, int r)
{
    if (l <= L && R <= r) maketag2(u, R - L + 1);
    else if (L <= r && R >= l)
    {
        int M = L + R >> 1;
        pushdown(u, L, R);
        update2(u << 1, L, M, l, r);
        update2(u << 1 | 1, M + 1, R, l, r);
        pushup(u, L, R);
    }
}
void update3(int u, int L, int R, int l, int r)
{
    if (l <= L && R <= r) maketag3(u, R - L + 1);
    else if (L <= r && R >= l)
    {
        int M = L + R >> 1;
        pushdown(u, L, R);
        update3(u << 1, L, M, l, r);
        update3(u << 1 | 1, M + 1, R, l, r);
        pushup(u, L, R);
    }
}
int query1(int u, int L, int R, int l, int r)
{
    if (l <= L && R <= r) return w1[u];
    else if (L <= r && R >= l)
    {
        int M = L + R >> 1;
        pushdown(u, L, R);
        return query1(u << 1, L, M, l, r) + query1(u << 1 | 1, M + 1, R, l, r);
    }
    else return 0;
}
int query3(int u, int L, int R, int l, int r)
{
    if (l <= L && R <= r) return w3[u];
    else if (L <= r && R >= l)
    {
        int M = L + R >> 1;
        pushdown(u, L, R);
        int x = query3(u << 1, L, M, l, r), y = query3(u << 1 | 1, M + 1, R, l, r);
        return (y == R - M ? x + y : max(x, y));
    }
    else return 0;
}
int query4(int u, int L, int R, int l, int r)
{
    if (l <= L && R <= r) return w3[u];
    else if (L <= r && R >= l)
    {
        int M = L + R >> 1;
        pushdown(u, L, R);
        int x = query4(u << 1, L, M, l, r), y = query4(u << 1 | 1, M + 1, R, l, r);
        return (x == M - L + 1 ? x + y : max(x, y));
    }
    else return 0;
}
int query2(int u, int L, int R, int l, int r)
{
    if (l <= L && R <= r) return w2[u];
    else if (L <= r && R >= l)
    {
        int M = L + R >> 1;
        pushdown(u, L, R);
        return max(max(query2(u << 1, L, M, l, r), query2(u << 1 | 1, M + 1, R, l, r)), query3(u << 1, L, M, l, r) + query4(u << 1 | 1, M + 1, R, l, r));
    }
    else return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (m--)
    {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 0) update1(1, 1, n, l + 1, r + 1);
        else if (op == 1) update2(1, 1, n, l + 1, r + 1);
        else if (op == 2) update3(1, 1, n, l + 1, r + 1);
        else if (op == 3) cout << query1(1, 1, n, l + 1, r + 1) << endl;
        else cout << query2(1, 1, n, l + 1, r + 1) << endl;
    }
    return 0;
}

但是还是不对

by Rubidium_Chloride @ 2022-07-07 15:58:12

而且你是不是build的时候忘记把 w[1~4] b[1~4] 都初始化了。

by 幸存者 @ 2022-07-07 16:01:25

@Reality_Creator 改了之后输出变成 5 4 6 5 了？？？

by 幸存者 @ 2022-07-07 16:06:38

结果把 hack 数据给过了……

by 幸存者 @ 2022-07-07 16:16:48

现在样例过了还是 0 分

|