求助

P2572 [SCOI2010]序列操作

样例

5
2
6
5

我的输出是

5
2
6
7

#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define reg register int
#define isdigit(x) ('0' <= x&&x <= '9')
template<typename T>
inline T Read(T Type)
{
    T x = 0,f = 1;
    char a = getchar();
    while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
    while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
    return x * f;
}
//快读 
const int MAXN = 100010;
struct segment_tree
{
    struct node
    {
        int len,sum,lazy,rev,lsum[2],rsum[2],maxl[2];
    }tree[MAXN << 2];
    void update(int k,int k1,int k2,int lenl,int lenr,int x)//标记下传后(k1,k2)修改k 
    {
        tree[k].maxl[x] = max(tree[k1].maxl[x],max(tree[k2].maxl[x],tree[k1].rsum[x] + tree[k2].lsum[x]));
        tree[k].lsum[x] = tree[k1].lsum[x];
        if(tree[k1].lsum[x] == lenl) tree[k].lsum[x] += tree[k2].lsum[x];
        tree[k].rsum[x] = tree[k2].rsum[x];
        if(tree[k2].rsum[x] == lenr) tree[k].rsum[x] += tree[k1].rsum[x];
        tree[k].sum = tree[k1].sum + tree[k2].sum;
    }
    void build(int k,int l,int r)//建树 
    {
        if(l == r)
        {
            int x = tree[k].sum = Read(1);
            tree[k].maxl[x] = tree[k].lsum[x] = tree[k].rsum[x] = 1;
            tree[k].maxl[!x] = tree[k].lsum[!x] = tree[k].rsum[!x] = 0;
            tree[k].lazy = -1,tree[k].rev = 0;
            return;
        }
        int mid = l + r >> 1;
        tree[k].lazy = -1,tree[k].rev = 0;
        build(k << 1,l,mid);
        build(k << 1 | 1,mid + 1,r);
        update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid + 1,0);
        update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid + 1,1);
    }
    void pushdown(int k,int k1,int len)//标记下传 
    {
        if(tree[k].lazy != -1)
        {
            int x = tree[k].lazy;
            tree[k1].lazy = x;
            tree[k1].sum = (x == 1?len:0);
            tree[k1].maxl[x] = tree[k1].lsum[x] = tree[k1].rsum[x] = len;
            tree[k1].maxl[!x] = tree[k1].lsum[!x] = tree[k1].rsum[!x] = 0;
        }
        if(tree[k].rev)
        {
            tree[k1].rev = !tree[k1].rev;
            tree[k1].sum = len - tree[k1].sum;
            swap(tree[k1].lsum[0],tree[k1].lsum[1]);
            swap(tree[k1].rsum[0],tree[k1].rsum[1]);
            swap(tree[k1].maxl[0],tree[k1].maxl[1]);
        }
    }
    void change(int k,int l,int r,int L,int R,int x)//[L,R]改x 
    {
        if(L <= l&&r <= R)
        {
            tree[k].lazy = x;
            tree[k].sum = (x == 1?r - l + 1:0);
            tree[k].maxl[x] = tree[k].lsum[x] = tree[k].rsum[x] = r - l + 1;
            tree[k].maxl[!x] = tree[k].lsum[!x] = tree[k].rsum[!x] = 0;
            return;
        }
        int mid = l + r >> 1;
        pushdown(k,k << 1,mid - l + 1);
        pushdown(k,k << 1 | 1,r - mid + 1);
        tree[k].lazy = -1,tree[k].rev = 0;
        if(L <= mid) change(k << 1,l,mid,L,R,x);
        if(mid < R) change(k << 1 | 1,mid + 1,r,L,R,x);
        update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid + 1,0);
        update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid + 1,1);
    }
    void inverse(int k,int l,int r,int L,int R)//反转 
    {
        if(L <= l&&r <= R)
        {
            tree[k].rev = !tree[k].rev;
            tree[k].sum = r - l + 1 - tree[k].sum;
            swap(tree[k].lsum[0],tree[k].lsum[1]);
            swap(tree[k].rsum[0],tree[k].rsum[1]);
            swap(tree[k].maxl[0],tree[k].maxl[1]);
            return;
        }
        int mid = l + r >> 1;
        pushdown(k,k << 1,mid - l + 1);
        pushdown(k,k << 1 | 1,r - mid + 1);
        tree[k].lazy = -1,tree[k].rev = 0;
        if(L <= mid) inverse(k << 1,l,mid,L,R);
        if(mid < R) inverse(k << 1 | 1,mid + 1,r,L,R);
        update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid + 1,0);
        update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid + 1,1);
    }
    int query(int k,int l,int r,int L,int R)//1的个数 
    {
        if(L <= l&&r <= R) return tree[k].sum;
        int mid = l + r >> 1;
        pushdown(k,k << 1,mid - l + 1);
        pushdown(k,k << 1 | 1,r - mid + 1);
        tree[k].lazy = -1,tree[k].rev = 0;
        int ans = 0;
        if(L <= mid) ans = query(k << 1,l,mid,L,R);
        if(mid < R) ans += query(k << 1 | 1,mid + 1,r,L,R);
        update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid + 1,0);
        update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid + 1,1);
        return ans;
    }
    node Sum(int k,int l,int r,int L,int R)//连续一的个数 
    {
        if(L <= l&&r <= R) 
        {
            tree[k].len = r - l + 1;
            return tree[k];
        }
        int mid = l + r >> 1;
        pushdown(k,k << 1,mid - l + 1);
        pushdown(k,k << 1 | 1,r - mid + 1);
        tree[k].lazy = -1,tree[k].rev = 0;
        node k1[2];
        memset(k1,0,sizeof(k1));
        if(L <= mid) k1[0] = Sum(k << 1,l,mid,L,R);
        if(mid < R) k1[1] = Sum(k << 1 | 1,mid + 1,r,L,R);
        update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid + 1,0);
        update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid + 1,1);
        node k3;
        k3.maxl[1] = max(k1[0].maxl[1],max(k1[1].maxl[1],k1[0].rsum[1] + k1[1].lsum[1]));
        k3.lsum[1] = k1[0].lsum[1];
        if(k1[0].lsum[1] == k1[0].len) k3.lsum[1] += k1[1].lsum[1];
        k3.rsum[1] = k1[1].rsum[1];
        if(k1[1].rsum[1] == k1[1].len) k3.rsum[1] += k1[0].rsum[1];
        return k3;
    }
}T;
//线段树 
int main()
{
    int n = Read(1),m = Read(1);
    memset(T.tree,0,sizeof(T.tree));
    T.build(1,1,n);
    while(m--)
    {
        int ans,op = Read(1),l = Read(1) + 1,r = Read(1) + 1;
        switch(op)
        {
            case 0: T.change(1,1,n,l,r,0); break;//改0 
            case 1: T.change(1,1,n,l,r,1); break;//改1 
            case 2: T.inverse(1,1,n,l,r); break;//反转 
            case 3: ans = T.query(1,1,n,l,r); printf("%d\n",ans); break;//1的个数 
            case 4: ans = T.Sum(1,1,n,l,r).maxl[1]; printf("%d\n",ans); break;//连续1的个数 
        }
    }
    return 0;
}