心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
线段树维护区间取反、区间覆盖。
拿日华哥哥的代码对拍了好久终于AC啦。
以下是我的代码:
/*
 * Author:  lee1r
 * Created Time:  2011/8/21 10:04:48
 * File Name: hdu3397.cpp
 
*/
#include
<iostream>
#include
<sstream>
#include
<fstream>
#include
<vector>
#include
<list>
#include
<deque>
#include
<queue>
#include
<stack>
#include
<map>
#include
<set>
#include
<bitset>
#include
<algorithm>
#include
<cstdio>
#include
<cstdlib>
#include
<cstring>
#include
<cctype>
#include
<cmath>
#include
<ctime>
#define L(x) ((x)<<1)
#define R(x) ((x)<<1|1)
#define Half(x) ((x)>>1)
#define Lowbit(x) ((x)&(-(x)))
using namespace std;
const int kInf(0x7f7f7f7f);
const double kEps(1e-8);
typedef unsigned 
int uint;
typedef 
long long int64;
typedef unsigned 
long long uint64;

int scanf(int &num)
{
    
char in;
    
while((in=getchar())!=EOF && (in>'9' || in<'0'));
    
if(in==EOF) return 0;
    num
=in-'0';
    
while(in=getchar(),in>='0' && in<='9') num*=10,num+=in-'0';
    
return 1;
}

const int kMaxn(100007);

struct Node
{
    
int a,b;
    
int max0,lmax0,rmax0;
    
int max1,lmax1,rmax1;
    
int cnt0,cnt1;
    
int cover,reverse;
};

int N,M;
bool r[kMaxn];
Node tree[kMaxn
<<2];

void PushDown(int node)
{
    
if(tree[node].cover!=-1)
    {
        tree[L(node)].reverse
=tree[R(node)].reverse=0;
        tree[L(node)].cover
=tree[R(node)].cover=tree[node].cover;
        
if(tree[node].cover==0)
        {
            tree[L(node)].cnt0
=tree[L(node)].max0=tree[L(node)].lmax0=tree[L(node)].rmax0=(tree[L(node)].b-tree[L(node)].a+1);
            tree[L(node)].cnt1
=tree[L(node)].max1=tree[L(node)].lmax1=tree[L(node)].rmax1=0;
            tree[R(node)].cnt0
=tree[R(node)].max0=tree[R(node)].lmax0=tree[R(node)].rmax0=(tree[R(node)].b-tree[R(node)].a+1);
            tree[R(node)].cnt1
=tree[R(node)].max1=tree[R(node)].lmax1=tree[R(node)].rmax1=0;
        }
        
else
        {
            tree[L(node)].cnt0
=tree[L(node)].max0=tree[L(node)].lmax0=tree[L(node)].rmax0=0;
            tree[L(node)].cnt1
=tree[L(node)].max1=tree[L(node)].lmax1=tree[L(node)].rmax1=(tree[L(node)].b-tree[L(node)].a+1);
            tree[R(node)].cnt0
=tree[R(node)].max0=tree[R(node)].lmax0=tree[R(node)].rmax0=0;
            tree[R(node)].cnt1
=tree[R(node)].max1=tree[R(node)].lmax1=tree[R(node)].rmax1=(tree[R(node)].b-tree[R(node)].a+1);
        }
        tree[node].cover
=-1;
    }
    
if(tree[node].reverse)
    {
        tree[node].reverse
=0;
        swap(tree[L(node)].max0,tree[L(node)].max1);
        swap(tree[L(node)].lmax0,tree[L(node)].lmax1);
        swap(tree[L(node)].rmax0,tree[L(node)].rmax1);
        swap(tree[L(node)].cnt0,tree[L(node)].cnt1);
        swap(tree[R(node)].max0,tree[R(node)].max1);
        swap(tree[R(node)].lmax0,tree[R(node)].lmax1);
        swap(tree[R(node)].rmax0,tree[R(node)].rmax1);
        swap(tree[R(node)].cnt0,tree[R(node)].cnt1);
        
        tree[L(node)].reverse
=!tree[L(node)].reverse;
        tree[R(node)].reverse
=!tree[R(node)].reverse;
    }
}

void PushUp(int node)
{
    tree[node].max0
=max(tree[L(node)].max0,tree[R(node)].max0);
    tree[node].max0
=max(tree[node].max0,tree[L(node)].rmax0+tree[R(node)].lmax0);
    
if(tree[L(node)].lmax0==tree[L(node)].b-tree[L(node)].a+1)
        tree[node].lmax0
=tree[L(node)].lmax0+tree[R(node)].lmax0;
    
else
        tree[node].lmax0
=tree[L(node)].lmax0;
    
if(tree[R(node)].rmax0==tree[R(node)].b-tree[R(node)].a+1)
        tree[node].rmax0
=tree[R(node)].rmax0+tree[L(node)].rmax0;
    
else
        tree[node].rmax0
=tree[R(node)].rmax0;
    
    tree[node].max1
=max(tree[L(node)].max1,tree[R(node)].max1);
    tree[node].max1
=max(tree[node].max1,tree[L(node)].rmax1+tree[R(node)].lmax1);
    
if(tree[L(node)].lmax1==tree[L(node)].b-tree[L(node)].a+1)
        tree[node].lmax1
=tree[L(node)].lmax1+tree[R(node)].lmax1;
    
else
        tree[node].lmax1
=tree[L(node)].lmax1;
    
if(tree[R(node)].rmax1==tree[R(node)].b-tree[R(node)].a+1)
        tree[node].rmax1
=tree[R(node)].rmax1+tree[L(node)].rmax1;
    
else
        tree[node].rmax1
=tree[R(node)].rmax1;
    
    tree[node].cnt0
=tree[L(node)].cnt0+tree[R(node)].cnt0;
    tree[node].cnt1
=tree[L(node)].cnt1+tree[R(node)].cnt1;
}

void Build(int node,int x,int y)
{
    tree[node].a
=x;
    tree[node].b
=y;
    tree[node].cover
=-1;
    tree[node].reverse
=0;
    
if(x==y)
    {
        tree[node].cnt0
=tree[node].max0=tree[node].lmax0=tree[node].rmax0=!r[x];
        tree[node].cnt1
=tree[node].max1=tree[node].lmax1=tree[node].rmax1=r[x];
    }
    
else
    {
        
int m(Half(x+y));
        Build(L(node),x,m);
        Build(R(node),m
+1,y);
        PushUp(node);
    }
}

void Modify(int node,int x,int y,int type)
{
    
if(x<=tree[node].a && tree[node].b<=y)
    {
        
if(type==0)
        {
            tree[node].reverse
=0;
            tree[node].cover
=0;
            tree[node].cnt0
=tree[node].max0=tree[node].lmax0=tree[node].rmax0=tree[node].b-tree[node].a+1;
            tree[node].cnt1
=tree[node].max1=tree[node].lmax1=tree[node].rmax1=0;
        }
        
else if(type==1)
        {
            tree[node].reverse
=0;
            tree[node].cover
=1;
            tree[node].cnt0
=tree[node].max0=tree[node].lmax0=tree[node].rmax0=0;
            tree[node].cnt1
=tree[node].max1=tree[node].lmax1=tree[node].rmax1=tree[node].b-tree[node].a+1;
        }
        
else if(type==2)
        {
            tree[node].reverse
=!tree[node].reverse;
            swap(tree[node].cnt0,tree[node].cnt1);
            swap(tree[node].max0,tree[node].max1);
            swap(tree[node].lmax0,tree[node].lmax1);
            swap(tree[node].rmax0,tree[node].rmax1);
        }
    }
    
else
    {
        PushDown(node);
        
int m(Half(tree[node].a+tree[node].b));
        
if(m>=x)
            Modify(L(node),x,y,type);
        
if(m<y)
            Modify(R(node),x,y,type);
        PushUp(node);
    }
}

int Query1(int node,int x,int y)
{
    
if(x<=tree[node].a && tree[node].b<=y)
        
return tree[node].cnt1;
    PushDown(node);
    
int m(Half(tree[node].a+tree[node].b)),re(0);
    
if(m>=x)
        re
+=Query1(L(node),x,y);
    
if(m<y)
        re
+=Query1(R(node),x,y);
    
return re;
}

int Query2(int node,int x,int y)
{
    
if(x<=tree[node].a && tree[node].b<=y)
        
return tree[node].max1;
    PushDown(node);
    
int m(Half(tree[node].a+tree[node].b));
    
if(m>=y)
        
return Query2(L(node),x,y);
    
if(m<x)
        
return Query2(R(node),x,y);
    
return max(max(Query2(L(node),x,m),Query2(R(node),m+1,y)),min(tree[L(node)].rmax1,m-x+1)+min(tree[R(node)].lmax1,y-m));
}

int main()
{
    
int T;
    scanf(T);
    
while(T--)
    {
        scanf(N);
        scanf(M);
        
for(int i=1;i<=N;i++)
        {
            
int t;
            scanf(t);
            
if(t)
                r[i]
=true;
            
else
                r[i]
=false;
        }
        
//  Input
        
        Build(
1,1,N);
        
//  Build
        
        
while(M--)
        {
            
int c,a,b;
            scanf(c);
            scanf(a);
            scanf(b);
            a
++;b++;
            
if(c<=2)
                Modify(
1,a,b,c);
            
else if(c==3)
                printf(
"%d\n",Query1(1,a,b));
            
else
                printf(
"%d\n",Query2(1,a,b));
        }
    }
    
    
return 0;
}
posted on 2011-08-22 18:57 lee1r 阅读(455) 评论(2)  编辑 收藏 引用 所属分类: 题目分类:数据结构

FeedBack:
# re: HDU 3397 Sequence operation[未登录]
2011-08-22 19:02 | Starry
好飘逸的代码~  回复  更多评论
  
# re: HDU 3397 Sequence operation
2011-08-22 19:05 | snowye
DBL  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理