求调求调要疯了

LiuCarry @ 2024-10-19 10:36:55

10 10
1 0 0 1 0 1 1 1 0 1 
2 0 4
2 9 9
1 5 7
2 3 8
4 5 9
0 4 8
2 0 3
1 0 1
4 5 6
3 1 2

1
0
1

1
2
1

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int a[100005];
struct ST
{
    int l,r;
    int cnt0,cnt1,pre0,pre1,suf0,suf1,ans0,ans1;
    ST operator+(const ST &bb) const
    {
        ST res;
        res.l=l;
        res.r=bb.r;
        res.cnt0=cnt0+bb.cnt0;
        res.cnt1=cnt1+bb.cnt1;
        if(cnt0==0) res.pre1=cnt1+bb.pre1;
        else res.pre1=pre1;
        if(cnt1==0) res.pre0=cnt0+bb.pre0;
        else res.pre0=pre0;
        if(bb.cnt0==0) res.suf1=suf1+bb.cnt1;
        else res.suf1=bb.suf1;
        if(bb.cnt1==0) res.suf0=suf0+bb.cnt0;
        else res.suf0=bb.suf0;
        res.ans0=max({ans0,bb.ans0,suf0+bb.pre0});
        res.ans1=max({ans1,bb.ans1,suf1+bb.pre1});
        return res;
    }
    void set0()
    {
        *this={l,r,r-l+1,0,r-l+1,0,r-l+1,0,r-l+1,0};
    }
    void set1()
    {
        *this={l,r,0,r-l+1,0,r-l+1,0,r-l+1,0,r-l+1};
    }
    void inv()
    {
        swap(cnt0,cnt1);
        swap(pre0,pre1);
        swap(suf0,suf1);
        swap(ans0,ans1);
    }
}tr[400005];
int tag[400005][2];
void build(int k,int l,int r)
{
    tag[k][0]=-1;
    if(l==r)
    {
        if(a[l]) tr[k]={l,r,0,1,0,1,0,1,0,1};
        else tr[k]={l,r,1,0,1,0,1,0,1,0};
        return;
    }
    int mid=(l+r)>>1;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    tr[k]=tr[k*2]+tr[k*2+1];
}
void push_down(int k)
{
    if(tag[k][0]==0)
    {
        tag[k*2][0]=0;
        tag[k*2+1][0]=0;
        tag[k*2][1]=0;
        tag[k*2+1][1]=0;
        tr[k*2].set0();
        tr[k*2+1].set0();
    }
    if(tag[k][0]==1)
    {
        tag[k*2][0]=1;
        tag[k*2+1][0]=1;
        tag[k*2][1]=0;
        tag[k*2+1][1]=0;
        tr[k*2].set1();
        tr[k*2+1].set1();
    }
    if(tag[k][1]==1)
    {
        tag[k*2][1]^=1;
        tag[k*2+1][1]^=1;
        tr[k*2].inv();
        tr[k*2+1].inv();
    }
    tag[k][0]=-1;
    tag[k][1]=0;
}
void upd0(int k,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)
    {
        tag[k][0]=0;
        tr[k].set0();
        return;
    }
    push_down(k);
    int mid=(l+r)>>1;
    if(x<=mid) upd0(k*2,l,mid,x,y);
    if(y>mid) upd0(k*2+1,mid+1,r,x,y);
    tr[k]=tr[k*2]+tr[k*2+1];
}
void upd1(int k,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)
    {
        tag[k][0]=1;
        tr[k].set1();
        return;
    }
    push_down(k);
    int mid=(l+r)>>1;
    if(x<=mid) upd1(k*2,l,mid,x,y);
    if(y>mid) upd1(k*2+1,mid+1,r,x,y);
    tr[k]=tr[k*2]+tr[k*2+1];
}
void updinv(int k,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)
    {
        tag[k][1]=1;
        tr[k].inv();
        return;
    }
    push_down(k);
    int mid=(l+r)>>1;
    if(x<=mid) updinv(k*2,l,mid,x,y);
    if(y>mid) updinv(k*2+1,mid+1,r,x,y);
    tr[k]=tr[k*2]+tr[k*2+1];
}
ST query(int k,int l,int r,int x,int y)
{
    if(x<=l&&r<=y) return tr[k];
    push_down(k);
    int mid=(l+r)>>1;
    ST res={l,r,0,0,0,0,0,0,0,0};
    if(x<=mid) res=res+query(k*2,l,mid,x,y);
    if(y>mid) res=res+query(k*2+1,mid+1,r,x,y);
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    int op,l,r;
    for(int i=1;i<=m;i++)
    {
        cin>>op>>l>>r;
        l++,r++;
        if(op==0) upd0(1,1,n,l,r);
        if(op==1) upd1(1,1,n,l,r);
        if(op==2) updinv(1,1,n,l,r);
        if(op==3) cout<<query(1,1,n,l,r).cnt1<<endl;
        if(op==4) cout<<query(1,1,n,l,r).ans1<<endl;
    }
    return 0;
}
/*
10 10
1 0 0 1 0 1 1 1 0 1 
2 0 4
2 9 9
1 5 7
2 3 8
4 5 9
0 4 8
2 0 3
1 0 1
4 5 6
3 1 2

2 0 4   0 1 1 0 1 1 1 1 0 1
2 9 9   0 1 1 0 1 1 1 1 0 0
1 5 7   0 1 1 0 1 1 1 1 0 0
2 3 8   0 1 1 1 0 0 0 0 1 0
4 5 9   1
0 4 8   0 1 1 1 0 0 0 0 0 0
2 0 3   1 0 0 0 0 0 0 0 0 0
1 0 1   1 1 0 0 0 0 0 0 0 0
4 5 6   0

*/

by yanbinmu @ 2024-10-19 12:19:10

你是不是标记记反了？

手模 5-6 有两个 0

by LiuCarry @ 2024-10-19 22:13:32

@yanbinmu 对啊我也知道，就是调不出来了。。。

by LiuCarry @ 2024-10-19 22:14:10

@yanbinmu 你看我的手摸数据都在代码底下的注释里了，真调不出来了

by yanbinmu @ 2024-10-20 10:49:05

我重构我的代码去了

by hyf_9134 @ 2024-10-28 17:00:46

佬 您过了吗 我也是样例过了，hack过了，而且你上面那组数据也过了，但是0pts

#include <bits/stdc++.h>

#define int long long
#define all(x) (x).begin(), (x).end()
#define len(x) (x).size()
#define endl '\n'
#define lowbit(x) ((x) & -(x))

//using namespace std;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int N = 1e5 + 10;
struct node {
    int l, r, len;
    int maxl0, maxr0, maxl1, maxr1, ans0, ans1, sum1, sum0;
    int or0, or1, tag;
};

std::vector<node> tree(N << 2);
std::vector<int> a(N);

void push_up(int root, int ls, int rs) {
    tree[root].maxl0 = tree[ls].maxl0;
    tree[root].maxl1 = tree[ls].maxl1;
    tree[root].maxr0 = tree[rs].maxr0;
    tree[root].maxr1 = tree[rs].maxr1;
    tree[root].sum0 = tree[ls].sum0 + tree[rs].sum0;
    tree[root].sum1 = tree[ls].sum1 + tree[rs].sum1;
    if (tree[ls].maxl0 == tree[ls].len) {
        tree[root].maxl0 += tree[rs].maxl0;
    }
    if (tree[ls].maxl1 == tree[ls].len) {
        tree[root].maxl1 += tree[rs].maxl1;
    }
    if (tree[rs].maxr0 == tree[rs].len) {
        tree[root].maxr0 += tree[ls].maxr0;
    }
    if (tree[rs].maxr1 == tree[rs].len) {
        tree[root].maxr1 += tree[ls].maxr1;
    }
    tree[root].ans0 = std::max({tree[ls].ans0, tree[rs].ans0, tree[ls].maxr0 + tree[rs].maxl0});
    tree[root].ans1 = std::max({tree[ls].ans1, tree[rs].ans1, tree[ls].maxr1 + tree[rs].maxl1});
}

void build(int root, int l, int r) {
    tree[root].l = l;
    tree[root].r = r;
    tree[root].len = (r - l + 1);
    if (l == r) {
        if (a[l]) {
            tree[root].maxl0 = 0;
            tree[root].maxr0 = 0;
            tree[root].maxl1 = 1;
            tree[root].maxr1 = 1;
            tree[root].ans1 = 1;
            tree[root].sum1 = 1;
            tree[root].ans0 = 0;
            tree[root].sum0 = 0;

        } else {
            tree[root].maxl0 = 1;
            tree[root].maxr0 = 1;
            tree[root].maxl1 = 0;
            tree[root].maxr1 = 0;
            tree[root].ans0 = 1;
            tree[root].sum0 = 1;
            tree[root].ans1 = 0;
            tree[root].sum1 = 0;
        }
        return;
    }
    int mid = (l + r) >> 1;
    int ls = root << 1;
    int rs = root << 1 | 1;

    build(ls, l, mid);
    build(rs, mid + 1, r);
    push_up(root, ls, rs);
}

void tag_change0(int root) {
    tree[root].or0 = 1;
    tree[root].or1 = 0;
    tree[root].tag = 0;
    tree[root].maxl0 = tree[root].len;
    tree[root].maxr0 = tree[root].len;
    tree[root].maxl1 = 0;
    tree[root].maxr1 = 0;
    tree[root].ans1 = 0;
    tree[root].ans0 = tree[root].len;
    tree[root].sum0 = tree[root].len;
    tree[root].sum1 = 0;
}

void tag_change1(int root) {
    tree[root].or0 = 0;
    tree[root].or1 = 1;
    tree[root].tag = 0;
    tree[root].maxl0 = 0;
    tree[root].maxr0 = 0;
    tree[root].maxl1 = tree[root].len;
    tree[root].maxr1 = tree[root].len;
    tree[root].ans1 = tree[root].len;
    tree[root].ans0 = 0;
    tree[root].sum0 = 0;
    tree[root].sum1 = tree[root].len;
}

void tag_change2(int root) {
    tree[root].or0 = 0;
    tree[root].or1 = 0;
    tree[root].tag = 1;
    std::swap(tree[root].ans0, tree[root].ans1);
    std::swap(tree[root].maxl1, tree[root].maxl0);
    std::swap(tree[root].maxr1, tree[root].maxr0);
    std::swap(tree[root].sum1, tree[root].sum0);
}

void push_down(int root, int ls, int rs) {
    if (tree[root].or0) {
        tag_change0(ls);
        tag_change0(rs);
    }
    if (tree[root].or1) {
        tag_change1(ls);
        tag_change1(rs);
    }
    if (tree[root].tag) {
        tag_change2(ls);
        tag_change2(rs);
    }
    tree[root].tag = tree[root].or0 = tree[root].or1 = 0;
}

void update(int root, int l, int r, int L, int R, int x) {
    if (L <= l && r <= R) {
        if (l != r) {
            int ls = root << 1;
            int rs = root << 1 | 1;
            push_down(root, ls, rs);
        }
        if (x == 0) {
            tag_change0(root);
        } else if (x == 1) {
            tag_change1(root);
        } else {
            tag_change2(root);
        }
        return;
    }

    int mid = (l + r) >> 1;
    int ls = root << 1;
    int rs = root << 1 | 1;
    push_down(root, ls, rs);
    if (L <= mid) {
        update(ls, l, mid, L, R, x);
    }
    if (R >= mid + 1) {
        update(rs, mid + 1, r, L, R, x);
    }
    push_up(root, ls, rs);
}

int query3(int root, int l, int r, int L, int R) {
    if (L <= l && r <= R) {
        return tree[root].sum1;
    }
    int mid = (l + r) >> 1;
    int ls = root << 1;
    int rs = root << 1 | 1;
    int sum = 0;
    push_down(root, ls, rs);
    if (L <= mid) {
        sum += query3(ls, l, mid, L, R);
    }
    if (R >= mid + 1) {
        sum += query3(rs, mid + 1, r, L, R);
    }
    return sum;
}

node query4(int root, int l, int r, int L, int R) {
    if (L <= l && r <= R) {
        return tree[root];
    }
    int mid = (l + r) >> 1;
    int ls = root << 1;
    int rs = root << 1 | 1;
    push_down(root, ls, rs);

    if (R <= mid) {
        return query4(ls, l, mid, L, R);
    } else if (L >= mid + 1) {
        return query4(rs, mid + 1, r, L, R);
    } else {
        node t, t1, t2;
        t1 = query4(ls, l, mid, L, R);
        t2 = query4(rs, mid + 1, r, L, R);
        t.l = t1.l;
        t.r = t2.r;
        t.len = t.r - t.l + 1;
        t.maxl0 = t1.maxl0;
        t.maxl1 = t1.maxl1;
        t.maxr0 = t2.maxr0;
        t.maxr1 = t2.maxr1;
        if (t1.maxl0 == t1.len) {
            t.maxl0 += t2.maxl0;
        }
        if (t1.maxl1 == t1.len) {
            t.maxl1 += t2.maxl1;
        }
        if (t2.maxr0 == t2.len) {
            t.maxr0 += t1.maxr0;
        }
        if (t2.maxr1 == t2.len) {
            t.maxr1 += t1.maxr1;
        }
        t.ans0 = std::max({t1.ans0, t2.ans0, t1.maxr0 + t2.maxl0});
        t.ans1 = std::max({t1.ans1, t2.ans1, t1.maxr1 + t2.maxl1});
        return t;
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    //std::cout.precision(10);
    int n, q;
    std::cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    build(1, 1, n);
    for (int i = 1; i <= q; i++) {
        int op, l, r;
        std::cin >> op >> l >> r;
        l++, r++;
        if (op <= 2) {
            update(1, 1, n, l, r, op);
        } else if (op == 3) {
            std::cout << query3(1, 1, n, l, r) << endl;
        } else {
            std::cout << query4(1, 1, n, l, r).ans1 << endl;
        }
    }

    return 0;
}