样例通过其余全部WA求调

Prolystic @ 2024-07-07 21:59:07

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m;
int cvt[N << 2], xrt[N << 2];
struct Sgt{
    int s0, s1, m0, m1, l0, l1, r0, r1;
}t[N << 2];
inline void read(int& x){
    int s = 0, w = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { w = (ch == '-' ? -1 : w); ch = getchar(); }
    while(ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); }
    x = s * w;
}
inline void write(int x){
    if(x < 0) { x = -x; putchar('-'); }
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
inline void write(int x, char ch) { write(x); putchar(ch); }
inline int ls(int p) { return p << 1; }
inline int rs(int p) { return p << 1 | 1; }
inline Sgt merge(Sgt a, Sgt b){
    int ns0 = a.s0 + b.s0, ns1 = a.s1 + b.s1;
    int nl0 = (a.s1 ? a.m0 : a.s0 + b.l0), nl1 = (a.s0 ? a.l1 : a.s1 + b.l1);
    int nr0 = (b.s1 ? b.r0 : b.s0 + a.r0), nr1 = (b.s0 ? b.r1 : b.s1 + a.r1);
    int nm0 = max(max(a.m0, b.m0), a.r0 + b.l0), nm1 = max(max(a.m1, b.m1), a.r1 + b.l1);
    return Sgt{ns0, ns1, nm0, nm1, nl0, nl1, nr0, nr1};
}
inline void push_up(int p) { t[p] = merge(t[ls(p)], t[rs(p)]); }
inline void build(int p, int l, int r){
    if(l == r){
        int tmp; read(tmp);
        t[p].s1 = t[p].m1 = t[p].l1 = t[p].r1 = tmp;
        t[p].s0 = t[p].m0 = t[p].l0 = t[p].r0 = 1 - tmp;
        return;
    }
    int mid = l + r >> 1;
    build(ls(p), l, mid), build(rs(p), mid + 1, r);
    push_up(p), cvt[p] = -1, xrt[p] = 0;
}
inline void cover(int p, int l, int r, int k){
    int len = r - l + 1;
    xrt[p] = 0, cvt[p] = k;
    t[p].s0 = t[p].l0 = t[p].r0 = t[p].m0 = (k == 0 ? len : 0);
    t[p].s1 = t[p].l1 = t[p].r1 = t[p].m1 = (k == 1 ? len : 0);
}
inline void xr(int p){
    xrt[p] ^= 1;
    if(!xrt[p])
        return;
    swap(t[p].s0, t[p].s1), swap(t[p].m0, t[p].m1);
    swap(t[p].l0, t[p].l1), swap(t[p].r0, t[p].r1);
}
inline void push_down(int p, int l, int r){
    int mid = l + r >> 1;
    if(cvt[p] != -1){
        cover(ls(p), l, mid, cvt[p]), cover(rs(p), mid + 1, r, cvt[p]);
        cvt[p] = -1;
    }
    if(xrt[p]){
        xr(ls(p)), xr(rs(p));
        xrt[p] = 0;
    }
}
inline void upd_cvr(int p, int l, int r, int x, int y, int k){
    if(x <= l && r <= y){
        cover(p, l, r, k);
        return;
    }
    push_down(p, l, r);
    int mid = l + r >> 1;
    if(x <= mid)
        upd_cvr(ls(p), l, mid, x, y, k);
    if(y > mid)
        upd_cvr(rs(p), mid + 1, r, x, y, k);
    push_up(p);
}
inline void upd_xor(int p, int l, int r, int x, int y){
    if(x <= l && r <= y){
        xr(p);
        return;
    }
    push_down(p, l, r);
    int mid = l + r >> 1;
    if(x <= mid)
        upd_xor(ls(p), l, mid, x, y);
    if(y > mid)
        upd_xor(rs(p), mid + 1, r, x, y);
    push_up(p);
}
inline int qry_s1(int p, int l, int r, int x, int y){
    if(x <= l && r <= y)
        return t[p].s1;
    push_down(p, l, r);
    int mid = l + r >> 1, ans = 0;
    if(x <= mid)
        ans += qry_s1(ls(p), l, mid, x, y);
    if(y > mid)
        ans += qry_s1(rs(p), mid + 1, r, x, y);
    return ans;
}
inline Sgt qry_m1(int p, int l, int r, int x, int y){
    if(x <= l && r <= y)
        return t[p];
    else if(y < l || x > r)
        return Sgt{0, 0, 0, 0, 0, 0, 0, 0};
    push_down(p, l, r);
    int mid = l + r >> 1;
    return merge(qry_m1(ls(p), l, mid, x, y), qry_m1(rs(p), mid + 1, r, x, y));
}
int main(){
    read(n), read(m);
    build(1, 1, n);
    while(m--){
        int op, x, y;
        read(op), read(x), read(y);
        x++, y++;
        if(op == 0)
            upd_cvr(1, 1, n, x, y, 0);
        else if(op == 1)
            upd_cvr(1, 1, n, x, y, 1);
        else if(op == 2)
            upd_xor(1, 1, n, x, y);
        else if(op == 3)
            write(qry_s1(1, 1, n, x, y), '\n');
        else if(op == 4)
            write(qry_m1(1, 1, n, x, y).m1, '\n');
    }
    return 0;
}

by ln_zm @ 2024-07-10 13:15:00

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int n, m;
int cvt[N << 2], xrt[N << 2];

struct Sgt {
    //s0 --> 0 的个数
    //s1 --> 1 的个数
    //m0 --> ? 
    //m1 --> ?
    //l0 --> 左边起 0 的最长长度
    //l1 --> 左边起 1 的最长长度
    //r0 --> 右边起 0 的最长长度
    //r1 --> 右边起 1 的最长长度  
    int s0, s1, m0, m1, l0, l1, r0, r1;
} t[N << 2];

inline void read(int& x) {
    int s = 0, w = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { w = (ch == '-' ? -1 : w); ch = getchar(); }
    while (ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); }
    x = s * w;
}

inline void write(int x) {
    if (x < 0) { x = -x; putchar('-'); }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

inline void write(int x, char ch) { write(x); putchar(ch); }

//ls --> 左区间
//rs --> 右区间 
inline int ls(int p) { return p << 1; }
inline int rs(int p) { return p << 1 | 1; }

inline Sgt merge(Sgt a, Sgt b) {
    //ns0 --> new s0?
    //ns1 --> new s1?
    //nl0 --> new l1
    //nl1 --> new l1
    //nr0 --> new r0
    //nr1 --> new r1
    //nm0 --> new m0 区间最长 0 的长度 
    //nm1 --> new m1 区间最长 1 的长度 
    int ns0 = a.s0 + b.s0, ns1 = a.s1 + b.s1;
    int nl0 = (a.s1 ? a.l0 : a.s0 + b.l0), nl1 = (a.s0 ? a.l1 : a.s1 + b.l1);
    int nr0 = (b.s1 ? b.r0 : b.s0 + a.r0), nr1 = (b.s0 ? b.r1 : b.s1 + a.r1);
    int nm0 = max(max(a.m0, b.m0), a.r0 + b.l0), nm1 = max(max(a.m1, b.m1), a.r1 + b.l1);
    return Sgt{ns0, ns1, nm0, nm1, nl0, nl1, nr0, nr1};
}

inline void push_up(int p) { t[p] = merge(t[ls(p)], t[rs(p)]); }

inline void build(int p, int l, int r) {
    if (l == r) {
        int tmp; read(tmp);
        //读入 tmp 1/0
        //读入  1 s1 = l1 = r1 = m1 = 1
        //        s0 = l0 = r0 = m0 = 1 - 1 = 0
        //读入  0 s1 = l1 = r1 = m1 = 0
        //        s0 = l0 = r0 = m0 = 1 - 0 = 1 
        t[p].s1 = t[p].m1 = t[p].l1 = t[p].r1 = tmp;
        t[p].s0 = t[p].m0 = t[p].l0 = t[p].r0 = 1 - tmp;
        return;
    }

    int mid = l + r >> 1;
    build(ls(p), l, mid), build(rs(p), mid + 1, r);
    push_up(p);
    cvt[p] = -1, xrt[p] = 0;//?
}

//区间赋值为 k ? 
inline void cover(int p, int l, int r, int k) {
    int len = r - l + 1;
    xrt[p] = 0, cvt[p] = k;
    t[p].s0 = t[p].l0 = t[p].r0 = t[p].m0 = (k == 0 ? len : 0);
    t[p].s1 = t[p].l1 = t[p].r1 = t[p].m1 = (k == 1 ? len : 0);
}
//区间取反 
inline void xr(int p) {
    xrt[p] ^= 1;
//    if (!xrt[p]) return; 这是干啥呢？ 
    swap(t[p].s0, t[p].s1), swap(t[p].m0, t[p].m1);
    swap(t[p].l0, t[p].l1), swap(t[p].r0, t[p].r1);
}

inline void push_down(int p, int l, int r) {
    int mid = l + r >> 1;
    if (cvt[p] != -1) {
        cover(ls(p), l, mid, cvt[p]), cover(rs(p), mid + 1, r, cvt[p]);
    }
    if (xrt[p]) {
        xr(ls(p)), xr(rs(p));
    }
    cvt[p] = -1;
    xrt[p] = 0;
}

inline void upd_cvr(int p, int l, int r, int x, int y, int k) {
    if (x <= l && r <= y) {
        cover(p, l, r, k);
        return;
    }
    push_down(p, l, r);
    int mid = l + r >> 1;
    if (x <= mid) upd_cvr(ls(p), l, mid, x, y, k);
    if (y > mid) upd_cvr(rs(p), mid + 1, r, x, y, k);
    push_up(p);
}

inline void upd_xor(int p, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
        xr(p);
        return;
    }
    push_down(p, l, r);
    int mid = l + r >> 1;
    if (x <= mid) upd_xor(ls(p), l, mid, x, y);
    if (y > mid) upd_xor(rs(p), mid + 1, r, x, y);
    push_up(p);
}

//x 左边界？
//y 右边界？ 
inline int qry_s1(int p, int l, int r, int x, int y) {
    if (x <= l && r <= y) return t[p].s1;
    push_down(p, l, r);
    int mid = l + r >> 1, ans = 0;
    if (x <= mid) ans += qry_s1(ls(p), l, mid, x, y);
    if (y > mid) ans += qry_s1(rs(p), mid + 1, r, x, y);
    return ans;
}

inline Sgt qry_m1(int p, int l, int r, int x, int y) {
    if (x <= l && r <= y) return t[p];
    else if (y < l || x > r) return Sgt{0, 0, 0, 0, 0, 0, 0, 0};
    push_down(p, l, r);
    int mid = l + r >> 1;
    return merge(qry_m1(ls(p), l, mid, x, y), qry_m1(rs(p), mid + 1, r, x, y));
}

int main() {
    read(n), read(m);

    build(1, 1, n);
    while (m--) {
        int op, x, y;
        read(op), read(x), read(y);
        x++, y++;
        if (op == 0) {
            upd_cvr(1, 1, n, x, y, 0);
        } else if (op == 1) {
            upd_cvr(1, 1, n, x, y, 1);
        } else if (op == 2) {
            upd_xor(1, 1, n, x, y);
        } else if (op == 3) {
            write(qry_s1(1, 1, n, x, y), '\n');
        } else if (op == 4) {
            write(qry_m1(1, 1, n, x, y).m1, '\n');
        }
    }
    return 0;
}

by Prolystic @ 2024-08-08 18:03:53

@ln_zm 好强，会啦\bx