线段树小结

 线段树小结篇：
 2  基本是按着HH专辑来练的：http://www.notonlysuccess.com/index.php/segment-tree-complete/
 按分类为单点更新,成段更新，区间合并，扫描线；
 做了一些题目，显然对于明显的操作如单纯的单点更新，敲出代码是不成问题的；
 但对于稍微麻烦一点的操作，如果没有很好的代码能力和平时的积累，就很难在比赛时一气呵成写出代码；
 因此写本文在于总结线段树代码的一些细节之处，给自己以后遗忘复习用；
 
 1:lazy标记；
  　 lazy标记主要运用于成段更新时，这也是线段树经常用到的，因为每次更新只需要更新到当前位置，
　　　　 等到下次更新或者询问时再更新，使得更新的复杂度降低。
 　　lazy标记对于初写线段数的人来说是个不小的挑战，刚开始写成段更新时，可能会遇到的问题：
        a：lazy标记是对于当前节点rt来说，还是对于子节点rt<<1，rt<<1|1来说，
              即对当前col[rt]，当pushdown(rt)时,是更新rt节点的值,还是更新子节点的值？
        b: 在update()时，lazy标记会被更新，此时要不要对当前rt更新值？ 

        这些问题主要是因为当时不明白lazy标记到底表示的是什么意思；
        col[rt]的含义：    col[rt]标记为空；
                          col[rt]不为空： 当前段被标记，
　　　　　　　　　　　　　　　　　当update(),query()到当前段是，要先pushdown()下去，再递归到子节点；
         
        lazy标记的精髓就在于延迟操作，但提前是延迟操作不会使结果不正确，那为什么不会使结果不正确呢？
                  因为线段树操作不管是update(),query()都是从根节点开始的，
　　　　　　           当询问或更新到需要的当前段后，已经完成了操作，

                  我们直接从该段pushup()上去，不会导致最终解错误，对于该段的子段来说我们不需要它的解，
　　　　　　　　　　　　 所以我们把这些我们当前不需要的段不进行更新，

                  用lazy标记记录下来，  当需要的时候先把它更新了，再进行必要操作；
 
                  也就是col[rt]不为空时，它只对子节点产生影响，
　　　　　　　　　　　　 并且col[rt]不为空时，sum[rt],cnt[rt]，rt节点的值都是正确的，在pushudown()时，

　　　　　　　　　　把标记传给col[rt<<1]和col[rt<<1|1],所以rt<<1,和rt<<1|1的值就要更新，
　　　　　　　　　　　 col[rt]已经把标记传下去了，所以要清空；在update()时，被标记的当前段也要更新为正确值；  

         http://acm.hdu.edu.cn/showproblem.php?pid=3397

　　　　

　　2:离散化的一些细节；

　　a:对于数据范围超过10^6，和double类型的数据都要进行离散化，但离散化后一般会遇到一些问题，
　　线段树里的一个节点代表的是一段距离，但离散后一个点就是一个点；比如更新（1,3），会更新到（1,2）（3,3）
　　如果单纯的计算距离的会3-3=0,so在更新的时候要处理一下更新（1,3），传入的值为（1,2）然后在计算距离是用xi[3]-xi[1]

　　b:原先代表是一段区域；

　　c:要考虑端点和中间，要乘2；

//hdu3397
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int MAXN=111111;
int mx_0[MAXN<<2];//改段连续0的个数
int mx_1[MAXN<<2];//该段连续1的个数
int conl_1[MAXN<<2],conr_1[MAXN<<2];//左边连续1的个数，右边连续1的个数
int conl_0[MAXN<<2],conr_0[MAXN<<2];//同上
int cnt[MAXN<<2];//记录该段1的个数
int col[MAXN<<2];//lazy标记
int n,m;
void pushup(int l,int m,int r,int rt)
{
        cnt[rt]=cnt[rt<<1]+cnt[rt<<1|1];
        if (conl_1[rt<<1]==m-l+1)
        {
                conl_1[rt]=conl_1[rt<<1]+conl_1[rt<<1|1];
        }        else conl_1[rt]=conl_1[rt<<1];
        if (conr_1[rt<<1|1]==r-m)
        {
                conr_1[rt]=conr_1[rt<<1|1]+conr_1[rt<<1];
        }        else conr_1[rt]=conr_1[rt<<1|1];
        
        if (conl_0[rt<<1]==m-l+1)
        {
                conl_0[rt]=conl_0[rt<<1]+conl_0[rt<<1|1];
        }        else conl_0[rt]=conl_0[rt<<1];
        if (conr_0[rt<<1|1]==r-m)
        {
                conr_0[rt]=conr_0[rt<<1|1]+conr_0[rt<<1];
        }        else conr_0[rt]=conr_0[rt<<1|1];
        
        int tmx=conr_1[rt<<1]+conl_1[rt<<1|1];
        mx_1[rt]=max(tmx,max(mx_1[rt<<1],mx_1[rt<<1|1]));
        
        tmx=conr_0[rt<<1]+conl_0[rt<<1|1];
        mx_0[rt]=max(tmx,max(mx_0[rt<<1],mx_0[rt<<1|1]));
}
void build(int l,int r,int rt)
{    
        col[rt]=-1;
        if (l==r)
        {
            scanf("%d",&col[rt]);
            if (col[rt]==1){
                mx_0[rt]=0;
                conl_0[rt]=conr_0[rt]=0;
                mx_1[rt]=conl_1[rt]=conr_1[rt]=cnt[rt]=1;
            }
            else {
                mx_0[rt]=1;
                cnt[rt]=mx_1[rt]=0;
                conl_0[rt]=conr_0[rt]=1;
                conl_1[rt]=conr_1[rt]=0;
            }
            return;
        }
        int m=(l+r)>>1;
        build(lson);
        build(rson);
        pushup(l,m,r,rt);
}
void pushdown(int l,int m,int r,int rt)//还是lazy标志的改变是难点；
{
        if (col[rt]!=-1)
        {
                if (col[rt]==1)
                {
                         col[rt<<1]=1;
                         conl_1[rt<<1]=conr_1[rt<<1]=mx_1[rt<<1]=m-l+1;
                         conl_0[rt<<1]=conr_0[rt<<1]=mx_0[rt<<1]=0;
                         cnt[rt<<1]=m-l+1;
                         
                         col[rt<<1|1]=1;
                              conl_1[rt<<1|1]=conr_1[rt<<1|1]=mx_1[rt<<1|1]=r-m;
                         conl_0[rt<<1|1]=conr_0[rt<<1|1]=mx_0[rt<<1|1]=0;
                         cnt[rt<<1|1]=r-m;
                }else if (col[rt]==0)
                {
                        col[rt<<1]=0;
                         conl_1[rt<<1]=conr_1[rt<<1]=mx_1[rt<<1]=0;
                        conl_0[rt<<1]=conr_0[rt<<1]=mx_0[rt<<1]=m-l+1;
                        cnt[rt<<1]=0;
                        
                        col[rt<<1|1]=0;
                        conl_1[rt<<1|1]=conr_1[rt<<1|1]=mx_1[rt<<1|1]=0;
                         conl_0[rt<<1|1]=conr_0[rt<<1|1]=mx_0[rt<<1|1]=r-m;
                         cnt[rt<<1|1]=0;
                }else if (col[rt]==2)
                {
                        
                    swap(conl_0[rt<<1],conl_1[rt<<1]);
                    swap(conr_0[rt<<1],conr_1[rt<<1]);
                    swap(mx_0[rt<<1],mx_1[rt<<1]);
                    cnt[rt<<1]=m-l+1-cnt[rt<<1];
                    
                    swap(conl_0[rt<<1|1],conl_1[rt<<1|1]);
                    swap(conr_0[rt<<1|1],conr_1[rt<<1|1]);
                    swap(mx_0[rt<<1|1],mx_1[rt<<1|1]);
                    cnt[rt<<1|1]=r-m-cnt[rt<<1|1];
                        
                     if (col[rt<<1]==0)//子段的标记不同，影响也不同
                     {
                         col[rt<<1]=1;    
                     }    else if (col[rt<<1]==1)
                     {
                         col[rt<<1]=0;
                     }    else if (col[rt<<1]==2)
                     {
                         col[rt<<1]=-1;
                     }    else if (col[rt<<1]==-1)
                     {
                            col[rt<<1]=2;
                     }
                     
                     if (col[rt<<1|1]==0)
                     {
                         col[rt<<1|1]=1;    
                     }    else if (col[rt<<1|1]==1)
                      {    
                         col[rt<<1|1]=0;
                     }    else if (col[rt<<1|1]==2)
                     {
                         col[rt<<1|1]=-1;
                     }    else if (col[rt<<1|1]==-1)
                     {
                            col[rt<<1|1]=2;
                     }    
                         
                }
                col[rt]=-1;    //清除lazy标志
        }
}
void update(int L,int R,int c,int l,int r,int rt)
{
        if (L<=l && r<=R)
        {
                if (c==2)
                {
                    swap(conl_0[rt],conl_1[rt]);
                    swap(conr_0[rt],conr_1[rt]);
                    swap(mx_0[rt],mx_1[rt]);
                    cnt[rt]=r-l+1-cnt[rt];
                    //这里lazy标志的改变，错了好久，只能说lazy标识的不熟悉；
                    //lazy标记只对子段起作用，所以要更新当前段；
                    if (col[rt]==0)
                        {
                         col[rt]=1;//原先标记不同，标记更新也不同；    
                        }    else if (col[rt]==1)
                     {
                         col[rt]=0;
                     }    else if (col[rt]==2)
                     {
                         col[rt]=-1;
                     }    else if (col[rt]==-1)
                     {
                            col[rt]=2;
                     }
                }else if (c==1)
                {
                    conl_1[rt]=conr_1[rt]=mx_1[rt]=r-l+1;
                    conl_0[rt]=conr_0[rt]=mx_0[rt]=0;
                    cnt[rt]=r-l+1;
                    
                    col[rt]=1;//更新标记；
                }if (c==0)
                {
                    conl_1[rt]=conr_1[rt]=mx_1[rt]=0;
                    conl_0[rt]=conr_0[rt]=mx_0[rt]=r-l+1;
                    cnt[rt]=0;
                    
                    col[rt]=0;
                }
                 
                return;
        }
        int m=(l+r)>>1;
        pushdown(l,m,r,rt);
        if (L<=m) update(L,R,c,lson);
        if (m< R) update(L,R,c,rson);
        pushup(l,m,r,rt);
}
int query_num(int L,int R,int l,int r,int rt)//统计个数
{
        if (L<=l && r<=R)
        {
            return cnt[rt];
        }        
        int m=(l+r)>>1;
        pushdown(l,m,r,rt);//每次询问都要先pushdown();
        int t1,t2;
        t1=t2=0;
        if (L<=m) t1=query_num(L,R,lson);
        if (m< R) t2=query_num(L,R,rson);
        return t1+t2;
}
int query_con(int L,int R,int l,int r,int rt)//统计连续1
{
        if (L<=l && r<=R)
        {
                return mx_1[rt];
        }
        int m=(l+r)>>1;
        pushdown(l,m,r,rt);
        int t1,t2;
        t1=t2=0;
        if (L<=m) t1=query_con(L,R,lson);
        if (m< R) t2=query_con(L,R,rson);
        int cl,cr,tmx=0;
        if (L<=m && m<R)
        {
            cl=min(conr_1[rt<<1],m-L+1);
            cr=min(conl_1[rt<<1|1],R-m);
            tmx=cl+cr;        
        } 
        return max(tmx,max(t1,t2));
}
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
            scanf("%d%d",&n,&m);
            build(1,n,1);
            while (m--)
            {
                int a,b,c;
                scanf("%d%d%d",&a,&b,&c);
                b++;c++;
                if (a==0)
                {
                    update(b,c,a,1,n,1);    
                }else if (a==1)
                {
                    update(b,c,a,1,n,1);             
                
                }else if (a==2)
                {
                    update(b,c,a,1,n,1);        
                }else if (a==3)
                {
                    int t=query_num(b,c,1,n,1);
                    printf("%d\n",t);
                }else if (a==4)
                {
                    int t=query_con(b,c,1,n,1);
                    printf("%d\n",t);
                }
                
            }
    }
    return 0;
}