【bzoj1858】[Scoi2010]序列操作

2015.04.15 10:31 Wed | 5次阅读 | 旧日oi | 固定链接 | 源码

Description

lxhgww最近收到了一个01序列,序列里面包含了n个数,这些数要么是0,要么是1,现在对于这个序列有五种变换操作和询问操作: 0 a b 把[a, b]区间内的所有数全变成0 1 a b 把[a, b]区间内的所有数全变成1 2 a b 把[a,b]区间内的所有数全部取反,也就是说把所有的0变成1,把所有的1变成0 3 a b 询问[a, b]区间内总共有多少个1 4 a b 询问[a, b]区间内最多有多少个连续的1 对于每一种询问操作,lxhgww都需要给出回答,聪明的程序员们,你们能帮助他吗?

Input

输入数据第一行包括2个数,n和m,分别表示序列的长度和操作数目 第二行包括n个数,表示序列的初始状态 接下来m行,每行3个数,op, a, b,(0<=op<=4,0<=a<=b

Output

对于每一个询问操作,输出一行,包括1个数,表示其对应的答案

Sample Input

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

Sample Output

5
2
6
5

HINT

对于30%的数据,1<=n, m<=1000
对于100%的数据,1<=n, m<=100000

题解

题意很裸,方法很裸,代码很长,调试很难
之前因为把取反看成翻转写了一颗大splay……………………

我的程序

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define maxn 400005
using namespace std;
int n,m,op,x,y;
struct node
{
    int siz,sum,l[2],r[2],m[2];
    int f1,f2;
}a[maxn];
void pushup(int rt)
{
    a[rt].siz=a[rt<<1].siz+a[rt<<1|1].siz;
    a[rt].sum=a[rt<<1].sum+a[rt<<1|1].sum;
    if(a[rt<<1].sum==a[rt<<1].siz) a[rt].l[1]=a[rt<<1].siz+a[rt<<1|1].l[1];
    else a[rt].l[1]=a[rt<<1].l[1];
    if(a[rt<<1].sum==0) a[rt].l[0]=a[rt<<1].siz+a[rt<<1|1].l[0];
    else a[rt].l[0]=a[rt<<1].l[0];
    if(a[rt<<1|1].sum==a[rt<<1|1].siz) a[rt].r[1]=a[rt<<1|1].siz+a[rt<<1].r[1];
    else a[rt].r[1]=a[rt<<1|1].r[1];
    if(a[rt<<1|1].sum==0) a[rt].r[0]=a[rt<<1|1].siz+a[rt<<1].r[0];
    else a[rt].r[0]=a[rt<<1|1].r[0];
    a[rt].m[0]=max(max(a[rt<<1].m[0],a[rt<<1|1].m[0]),a[rt<<1].r[0]+a[rt<<1|1].l[0]);
    a[rt].m[1]=max(max(a[rt<<1].m[1],a[rt<<1|1].m[1]),a[rt<<1].r[1]+a[rt<<1|1].l[1]);
}
void same(int rt,int val)
{
    a[rt].f1=val;a[rt].f2=0;
    a[rt].l[val]=a[rt].r[val]=a[rt].m[val]=a[rt].siz;
    a[rt].l[val^1]=a[rt].r[val^1]=a[rt].m[val^1]=0;
    a[rt].sum=val*a[rt].siz;
}
void rev(int rt)
{
    if(a[rt].f1!=-1)
    {
        same(rt,a[rt].f1^1);
        return;
    }
    a[rt].f2^=1;
    a[rt].sum=a[rt].siz-a[rt].sum;
    swap(a[rt].l[0],a[rt].l[1]);
    swap(a[rt].r[0],a[rt].r[1]);
    swap(a[rt].m[0],a[rt].m[1]);
}
void pushdown(int rt)
{
    if(a[rt].f1!=-1)
    {
        same(rt<<1,a[rt].f1);
        same(rt<<1|1,a[rt].f1);
        a[rt].f1=-1;
    }
    if(a[rt].f2)
    {
        rev(rt<<1);
        rev(rt<<1|1);
        a[rt].f2=0;
    }
}
void build(int l,int r,int rt)
{
    a[rt].f1=-1;
    if(l==r)
    {
        scanf("%d",&x);
        a[rt].sum=x;
        a[rt].siz=a[rt].m[x]=a[rt].l[x]=a[rt].r[x]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt);
}
void make_same(int l,int r,int rt,int L,int R,int c)
{
    if(L<=l&&R>=r)
    {
        same(rt,c);
        return;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    if(L<=mid) make_same(lson,L,R,c);
    if(R>mid) make_same(rson,L,R,c);
    pushup(rt);
}
void reverse(int l,int r,int rt,int L,int R)
{
    if(L<=l&&R>=r)
    {
        rev(rt);
        return;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    if(L<=mid) reverse(lson,L,R);
    if(R>mid) reverse(rson,L,R);
    pushup(rt);
}
int query(int l,int r,int rt,int L,int R)
{
    if(L<=l&&R>=r) return a[rt].sum;
    pushdown(rt);
    int mid=(l+r)>>1,ret=0;
    if(L<=mid) ret=query(lson,L,R);
    if(R>mid) ret+=query(rson,L,R);
    return ret;
}
node combine(node x,node y)
{
    node t;
    t.siz=x.siz+y.siz;
    t.sum=x.sum+y.sum;
    if(x.sum==x.siz) t.l[1]=x.siz+y.l[1];
    else t.l[1]=x.l[1];
    if(x.sum==0) t.l[0]=x.siz+y.l[0];
    else t.l[0]=x.l[0];
    if(y.sum==y.siz) t.r[1]=y.siz+x.r[1];
    else t.r[1]=y.r[1];
    if(y.sum==0) t.r[0]=y.siz+x.r[0];
    else t.r[0]=y.r[0];
    t.m[0]=max(max(x.m[0],y.m[0]),x.r[0]+y.l[0]);
    t.m[1]=max(max(x.m[1],y.m[1]),y.l[1]+x.r[1]);
    return t;
}
node get_ans(int l,int r,int rt,int L,int R)
{
    if(L<=l&&R>=r) return a[rt];
    pushdown(rt);
    int mid=(l+r)>>1;
    node t1,t2;
    bool v1=0,v2=0;
    if(L<=mid) t1=get_ans(lson,L,R),v1=1;
    if(R>mid) t2=get_ans(rson,L,R),v2=1;
    if(v1&&v2) return combine(t1,t2);
    else return v1?t1:t2;
}
int main()
{
    cin>>n>>m;
    build(1,n,1);
    while(m--)
    {
        scanf("%d%d%d",&op,&x,&y);x++;y++;
        switch (op)     {
            case 0:make_same(1,n,1,x,y,0);break;
            case 1:make_same(1,n,1,x,y,1);break;
            case 2:reverse(1,n,1,x,y);break;
            case 3:printf("%d\n",query(1,n,1,x,y));break;
            case 4:printf("%d\n",get_ans(1,n,1,x,y).m[1]);break;
        }
    }
    return 0;
}```