社区讨论

求助:问:queryl怎么写?

P2572[SCOI2010] 序列操作参与者 5已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mhjhz3u7
此快照首次捕获于
2025/11/04 02:52
4 个月前
此快照最后确认于
2025/11/04 02:52
4 个月前
查看原帖
CPP
#include <bits/stdc++.h>

using namespace std;

const int N = 110000;
struct TreeNode {
    int q[2];
    int h[2];
    int num[2];
    int maxn[2];
    int sz;
    int tag;
} seg[N * 4];
int n, m, a[N];

inline void settag(int id) {
    swap(seg[id].q[0], seg[id].q[1]);
    swap(seg[id].h[0], seg[id].h[1]);
    swap(seg[id].num[0], seg[id].num[1]);
    swap(seg[id].maxn[0], seg[id].maxn[1]);
}

inline void update(int id) {
    seg[id].q[0] = seg[id * 2].q[0] + (seg[id * 2].sz == seg[id * 2].q[0] ? seg[id * 2 + 1].q[0] : 0);
    seg[id].q[1] = seg[id * 2].q[1] + (seg[id * 2].sz == seg[id * 2].q[1] ? seg[id * 2 + 1].q[1] : 0);
    seg[id].h[0] = seg[id * 2 + 1].h[0] + (seg[id * 2 + 1].sz == seg[id * 2 + 1].h[0] ? seg[id * 2].h[0] : 0);
    seg[id].h[1] = seg[id * 2 + 1].h[1] + (seg[id * 2 + 1].sz == seg[id * 2 + 1].h[1] ? seg[id * 2].h[1] : 0);
    seg[id].num[0] = seg[id * 2].num[0] + seg[id * 2 + 1].num[0];
    seg[id].num[1] = seg[id * 2].num[1] + seg[id * 2 + 1].num[1];
    seg[id].maxn[0] = max(seg[id * 2].h[0] + seg[id * 2 + 1].q[0], max(seg[id * 2].q[0], seg[id * 2 + 1].h[0]));
    seg[id].maxn[1] = max(seg[id * 2].h[1] + seg[id * 2 + 1].q[1], max(seg[id * 2].q[1], seg[id * 2 + 1].h[1]));
}

inline void pushdown(int id) {
    int tag = seg[id].tag;
    if (tag) {
        settag(id * 2);
        settag(id * 2 + 1);
        seg[id].tag = 0;
    }
}

inline void build(int id, int l, int r) {
    seg[id] = {{0, 0}, {0, 0}, {0, 0}, {0, 0}, r - l + 1, 0};
    if (l == r) {
        seg[id].q[0] = (a[l] == 0);
        seg[id].q[1] = (a[l] == 1);
        seg[id].h[0] = (a[l] == 0);
        seg[id].h[1] = (a[l] == 1);
        seg[id].num[0] = (a[l] == 0);
        seg[id].num[1] = (a[l] == 1);
        seg[id].maxn[0] = (a[l] == 0);
        seg[id].maxn[1] = (a[l] == 1);
        return;
    }
    int m = (l + r) / 2;
    build(id * 2, l, m);
    build(id * 2 + 1, m + 1, r);
    update(id);
}

inline void modify(int id, int l, int r, int ql, int qr, int ty) {
    if (l >= ql && r <= qr) {
        if (ty == 0) {
            seg[id].q[0] = seg[id].sz;
            seg[id].q[1] = 0;
            seg[id].h[0] = seg[id].sz;
            seg[id].h[1] = 0;
            seg[id].num[0] = seg[id].sz;
            seg[id].num[1] = 0;
            seg[id].maxn[0] = seg[id].sz;
            seg[id].maxn[1] = 0;
            seg[id].tag = 0;
        }
        else if (ty == 1) {
            seg[id].q[0] = 0;
            seg[id].q[1] = seg[id].sz;
            seg[id].h[0] = 0;
            seg[id].h[1] = seg[id].sz;
            seg[id].num[0] = 0;
            seg[id].num[1] = seg[id].sz;
            seg[id].maxn[0] = 0;
            seg[id].maxn[1] = seg[id].sz;
            seg[id].tag = 0;           
        }
        else {
            swap(seg[id].q[0], seg[id].q[1]);
            swap(seg[id].h[0], seg[id].h[1]);
            swap(seg[id].num[0], seg[id].num[1]);
            swap(seg[id].maxn[0], seg[id].maxn[1]);
            seg[id].tag ^= 1;
        }
        return;
    }
    pushdown(id);
    int m = (l + r) / 2;
    if (ql <= m)
        modify(id * 2, l, m, ql, qr, ty);
    if (qr > m)
        modify(id * 2 + 1, m + 1, r, ql, qr, ty);
    update(id);
}

inline int queryt(int id, int l, int r, int ql, int qr) {
    if (l >= ql && r <= qr) 
        return seg[id].num[1];
    pushdown(id);
    int m = (l + r) / 2;
    if (ql <= m && qr > m)
        return queryt(id * 2, l, m, ql, qr) + queryt(id * 2 + 1, m + 1, r, ql, qr);
    if (ql <= m)
        return queryt(id * 2, l, m, ql, qr);
    else
        return queryt(id * 2 + 1, m + 1, r, ql, qr);
}

inline int queryl(int id, int l, int r, int ql, int qr) {
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    build(1, 1, n);
    for (; m--; ) {
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        x++, y++;
        if (op == 0)
            modify(1, 1, n, x, y, 0);
        else if (op == 1)
            modify(1, 1, n, x, y, 1);
        else if (op == 2)
            modify(1, 1, n, x, y, 2);
        else if (op == 3)
            printf("%d\n", queryt(1, 1, n, x, y));
        else
            printf("%d\n", queryl(1, 1, n, x, y));
    }
    return 0;
}
有点屎山……
调出必关

回复

4 条回复,欢迎继续交流。

正在加载回复...