HDU3397(Sequence operation)线段树的多种操作

[cpp]  
/********************************************** 
题目大意： 
0 a b将区间[a,b]所有数全部变成0 
1 a b将区间[a,b]所有数全部变成1 
2 a b将区间[a,b]中所有数0 1互换，0变1,1变0 
3 a b输出区间[a,b]中1的个数 
4 a b输出区间[a,b]中最长连续1的个数 
 
算法分析： 
涉及到线段树的多种操作; 
0,1两种操作可以合并到一起写; 
0,1互换即线段树的异或操作; 
查询区间最长连续1个数的过程中; 
maxl=[l,m]上最长连续1个数; 
maxl=[m+1,r]上最长连续1的个数; 
maxm=min(m-l+1,左孩子的rs)+min(r-m,右孩子的ls); 
结果应该是这三个中的最大值,即max(maxl,maxr,maxm); 
其中查询操作和pku3667类似; 
***********************************************/  
#include<iostream>  
#include<cstring>  
#include<cstdlib>  
#include<cstdio>  
#include<climits>  
#include<algorithm>  
using namespace std;  
  
#define L l,m,u<<1  
#define R m+1,r,u<<1|1  
  
const int N =100010;  
  
struct node  
{  
    int l,r;  
    int ls,ms,rs;//ls左边最长连续1数量;ms:最长连续1数量;rs:右边最长连续1数量;  
    int flag;//01状态  
    int total;//区间1的总数  
} t[N*3];  
  
int len(int u)  
{  
    return t[u].r-t[u].l+1;  
}  
  
int mid(int u)  
{  
    return (t[u].l+t[u].r)>>1;  
}  
  
void PushUp(int u,int x)//把当前结点的信息更新到父结点  
{  
    t[u].ls=t[u].ms=t[u].rs=t[u].total=x*(t[u].r-t[u].l+1);  
    t[u].flag=x;  
}  
  
void build(int l,int r,int u)//建树  
{  
    t[u].l=l;  
    t[u].r=r;  
    t[u].ls=t[u].rs=t[u].ms=t[u].total=t[u].flag=0;  
    if(l==r)  
        return;  
    int m=mid(u);  
    build(L);  
    build(R);  
  
}  
  
void PushUp(int u)//把当前结点的信息更新到父结点  
{  
    t[u].flag=(t[u<<1].flag==t[u<<1|1].flag?t[u<<1].flag:-1);//更新状态  
    t[u].ls=t[u<<1].ls+((t[u<<1].ls==len(u<<1))?t[u<<1|1].ls:0);//更新左  
    t[u].rs=t[u<<1|1].rs+((t[u<<1|1].rs==len(u<<1|1))?t[u<<1].rs:0);//更新右  
    t[u].ms=max(t[u<<1].rs+t[u<<1|1].ls,max(t[u<<1].ms,t[u<<1|1].ms));//更新整体  
    t[u].total=t[u<<1].total+t[u<<1|1].total;//更新1的总数  
}  
  
void update(int l,int r,int u,int x)//更新区间[l,r]0、1状态  
{  
    if(t[u].flag==x)  
        return;  
    if(t[u].l==l&&t[u].r==r)  
    {  
        PushUp(u,x);  
        return;  
    }  
    if(t[u].flag>=0)  
    {  
        PushUp(u<<1,t[u].flag);  
        PushUp(u<<1|1,t[u].flag);  
        t[u].flag=-1;  
    }  
    int m=mid(u);  
    if(r<=m)  
    {  
        update(l,r,u<<1,x);  
    }  
    else if(l>m)  
    {  
        update(l,r,u<<1|1,x);  
    }  
    else  
    {  
        update(L,x);  
        update(R,x);  
    }  
    PushUp(u);  
}  
  
void swap(int l,int r,int u)//[l,r]0、1交换  
{  
    if(t[u].l>=l&&t[u].r<=r&&(t[u].flag==0||t[u].flag==1))  
    {  
        int x=t[u].flag^1;  
        PushUp(u,x);  
        return;  
    }  
    if(t[u].flag>=0)  
    {  
        PushUp(u<<1,t[u].flag);  
        PushUp(u<<1|1,t[u].flag);  
    }  
    int m=mid(u);  
    if(r<=m)  
    {  
        swap(l,r,u<<1);  
    }  
    else if(l>m)  
    {  
        swap(l,r,u<<1|1);  
    }  
    else  
    {  
        swap(L);  
        swap(R);  
    }  
    PushUp(u);  
}  
  
int find1(int l,int r,int u)//找区间[l,r]内的1的个数  
{  
    if(t[u].l==l&&t[u].r==r)  
    {  
        return t[u].total;  
    }  
    if(t[u].flag>=0)  
    {  
        PushUp(u<<1,t[u].flag);  
        PushUp(u<<1|1,t[u].flag);  
    }  
    int m=mid(u);  
    if(r<=m)  
    {  
        return find1(l,r,u<<1);  
    }  
    else if(l>m)  
    {  
        return find1(l,r,u<<1|1);  
    }  
    else  
    {  
        return find1(L)+find1(R);  
    }  
}  
  
int find2(int l,int r,int u)//找区间[l,r]内最长连续1的个数  
{  
    if(t[u].l==l&&t[u].r==r)  
    {

补充：软件开发 , C++ ,