线段树：旨在自己看，题目来源与报告来自是某位大牛写的，很犀利。。。

（1）：单点更新

         HDU 1166敌兵布阵                       

#include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 50005int seg_tree[MAXN<<2];void build_tree(int l,int r,int id);int query_tree(int left,int right,int l,int r,int id);void update_point_tree(int left,int right,int value,int l,int r,int id);void push_up_tree(int id);int main(){    int tcase,n,i,left,right,value;    char str[20];    while(scanf("%d",&tcase)==1)    {        for(i=1;i<=tcase;i++)        {            printf("Case %d:\n",i);          scanf("%d",&n);              build_tree(1,n,1);        while(scanf("%s",str)!=EOF)        {            if(!strcmp(str,"Query"))            {                scanf("%d%d",&left,&right);                printf("%d\n",query_tree(left,right,1,n,1));            }            if(!strcmp(str,"Add"))            {                scanf("%d%d",&left,&value);                update_point_tree(left,left,value,1,n,1);            }            if(!strcmp(str,"Sub"))            {                scanf("%d%d",&left,&value);                update_point_tree(left,left,-value,1,n,1);            }            if(!strcmp(str,"End"))                break;        }                }    }}void build_tree(int l,int r,int id){    if(l==r)    {        scanf("%d",&seg_tree[id]);        return ;    }    int mid=(l+r)/2;    build_tree(l,mid,id<<1);    build_tree(mid+1,r,id<<1|1);   push_up_tree(id);    }int query_tree(int left,int right,int l,int r,int id){    if(left<=l&&right>=r)        return seg_tree[id];    int mid=(l+r)>>1,ret=0;    if(left<=mid)        ret+=query_tree(left,right,l,mid,id<<1);    if(right>mid)        ret+=query_tree(left,right,mid+1,r,id<<1|1);    return ret;}void update_point_tree(int left,int right,int value,int l,int r,int id){    if(l==r)    {    seg_tree[id]+=value;    return ;}    int mid=(l+r)>>1;    if(left<=mid)        update_point_tree(left,right,value,l,mid,id<<1);    else         update_point_tree(left,right,value,mid+1,r,id<<1|1);    push_up_tree(id);    }void push_up_tree(int id){    seg_tree[id]=seg_tree[id<<1]+seg_tree[id<<1|1];}
         
        
       
      

         HDU 1754 I Hate it                       

#include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 200005int seg_tree[MAXN<<2];void build_tree(int l,int r,int id);int query_tree(int left,int right,int l,int r,int id);void update_point_tree(int left,int right,int value,int l,int r,int id);void push_up_tree(int id);int main(){int tcase,n,i,left,right,value,m;char str[20];while(scanf("%d%d",&n,&m)==2){build_tree(1,n,1);while(m--){scanf("%s",str);if(str[0]=='Q'){scanf("%d%d",&left,&right);printf("%d\n",query_tree(left,right,1,n,1));}if(str[0]=='U'){scanf("%d%d",&left,&value);update_point_tree(left,right,value,1,n,1);}}}}void build_tree(int l,int r,int id){if(l==r){scanf("%d",&seg_tree[id]);return ;}int mid=(l+r)/2;build_tree(l,mid,id<<1);build_tree(mid+1,r,id<<1|1);push_up_tree(id);}int query_tree(int left,int right,int l,int r,int id){if(left<=l&&right>=r)return seg_tree[id];int mid=(l+r)>>1,ret0=0,ret1=0;if(left<=mid)ret0=query_tree(left,right,l,mid,id<<1);if(right>mid)ret1=query_tree(left,right,mid+1,r,id<<1|1);return ret0>=ret1?ret0:ret1;}void update_point_tree(int left,int right,int value,int l,int r,int id){if(l==r){    seg_tree[id]=value;return ;}int mid=(l+r)>>1;if(left<=mid)update_point_tree(left,right,value,l,mid,id<<1);else update_point_tree(left,right,value,mid+1,r,id<<1|1);push_up_tree(id);}void push_up_tree(int id){int temp1,temp2;temp1=seg_tree[id<<1];temp2=seg_tree[id<<1|1];seg_tree[id]=(temp1>=temp2?temp1:temp2);}
         
        
       
      

        hdu Minimum Inversion Number     

#include
      
       #include
       
        #include
        
         #include
         
          #define MAXN  5010int seg_tree[MAXN<<2];void build_tree(int l,int r,int id);int query_tree(int left,int right,int l,int r,int id);void update_tree(int left,int right,int l,int r,int id);void push_up_tree(int id);int x[MAXN];int main(){    int n,i,j,k,sum;    while(scanf("%d",&n)==1)    {        sum=0;        build_tree(0,n-1,1);        for(i=0;i
          
           =0;i--)        {            sum+=query_tree(0,x[i],0,n-1,1);            update_tree(x[i],x[i],0,n-1,1);        }        int ret=sum;        for(i=0;i
           
            sum) ret=sum; } printf("%d\n",ret); }}void build_tree(int l,int r,int id){ if(l==r) {seg_tree[id]=0; return ; } int m=(l+r)>>1; build_tree(l,m,id<<1); build_tree(m+1,r,id<<1|1); push_up_tree(id);}int query_tree(int left,int right,int l,int r,int id){ if(left<=l&&right>=r) return seg_tree[id]; int m=(l+r)>>1,ret=0; if(left<=m) ret+=query_tree(left,right,l,m,id<<1); if(right>m) ret+=query_tree(left,right,m+1,r,id<<1|1); return ret;}void update_tree(int left,int right,int l,int r,int id){ if(l==r) {seg_tree[id]++; return ; } int m=(l+r)>>1; if(left<=m) update_tree(left,right,l,m,id<<1); else update_tree(left,right,m+1,r,id<<1|1); push_up_tree(id);}void push_up_tree(int id){ seg_tree[id]=seg_tree[id<<1]+seg_tree[id<<1|1];}
           
          
         
        
       
      

        HDU Billboard                              

#include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 200002void build_tree(int l,int r,int id);void push_up_tree(int id);void update_tree(int value,int *x,int l,int r,int id);int m_max(int a,int b);int seg_tree[MAXN<<2];int h,w,n;int main() {    int temp,value,x;    while(scanf("%d%d%d",&h,&w,&n)==3)    {        h=(h>=n?n:h);        build_tree(1,h,1);        while(n--)        {            scanf("%d",&value);            if(value>seg_tree[1])            {                printf("-1\n");            }            else             {                update_tree(value,&x,1,h,1);                printf("%d\n",x);            }                    }    }}void build_tree(int l,int r,int id){    if(l==r)    {        seg_tree[id]=w;        return ;    }    int m=(l+r)>>1;    build_tree(l,m,id<<1);    build_tree(m+1,r,id<<1|1);    push_up_tree(id);    }void push_up_tree(int id){    seg_tree[id]=m_max(seg_tree[id<<1],seg_tree[id<<1|1]);}int m_max(int a,int b){    return a>=b?a:b;}void update_tree(int value,int *x,int l,int r,int id){    if(l==r)    {        *x=l;        seg_tree[id]-=value;        return ;    }    int m=(l+r)>>1;    if(seg_tree[id<<1]>=value)        update_tree(value,x,l,m,id<<1);    else update_tree(value,x,m+1,r,id<<1|1);    push_up_tree(id);}
         
        
       
      

       poj Buy Tickets                             

#include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 200005int seg_tree[MAXN<<2];void build_tree(int l,int r,int id);void push_up_tree(int id);void update_tree(int left,int right,int l,int r,int id);int ans[MAXN],cur;struct Node{    int i;    int num;};Node temp[MAXN];int main(){        int n,i,j,k;    while(scanf("%d",&n)==1)    {        build_tree(1,n,1);        for(i=1;i<=n;i++)        {scanf("%d%d",&temp[i].i,&temp[i].num);}        for(i=n;i>0;i--)           {               cur=temp[i].num;               update_tree(temp[i].i+1,n,1,n,1);                   }        for(i=1;i<=n;i++)        {
     if(i-1) printf(" ");            printf("%d",ans[i]);        }        printf("\n");    }   }void build_tree(int l,int r,int id){        if(l==r)    {        seg_tree[id]=1;        return ;    }  int m=(l+r)>>1;  build_tree(l,m,id<<1);  build_tree(m+1,r,id<<1|1);  push_up_tree(id);    }void push_up_tree(int id){    seg_tree[id]=seg_tree[id<<1]+seg_tree[id<<1|1];}void update_tree(int left,int right,int l,int r,int id){    if(l==r)    {        seg_tree[id]--;        ans[l]=cur;        return ;    }    int m=(l+r)>>1;        if(left<=seg_tree[id<<1])        update_tree(left,right,l,m,id<<1);    else     {        left-=seg_tree[id<<1];        update_tree(left,right,m+1,r,id<<1|1);    }    push_up_tree(id);}
         
        
       
      

     poj Who Gets the Most Candies?         

#include
      
       #include
       
        #include
        
         #include
         
          int seg_tree[500010<<2];void build_tree(int l,int r,int id);void push_tree_up(int id);void update_tree(int value,int l,int r,int id);int f[500010];void get_f();int num[500010],h;char str[500010][10];int cur_n,cur_i,next_i,ans,ans1;int main(){    int n,k,i,j,cur,temp;    //freopen("d:\\2.txt","r",stdin);    //freopen("d:\\3.txt","w",stdout);    memset(f,0,sizeof(f));    get_f();    while(scanf("%d%d%*c",&n,&k)!=EOF)    {        for(i=1;i<=n;i++)            scanf("%s%d",str[i],num+i);        cur_n=n;        cur_i=n;        next_i=k;        build_tree(1,n,1);        ans=0;        ans1=1;        h=1;        for(i=1;i<=n;i++)        {        //  printf("cur_i=%d next_i=%d",cur_i,next_i);                  if(next_i>=0)                      cur_i--;                  cur=(cur_i+next_i%cur_n+cur_n)%cur_n;              //   printf(" cur=%d\n",cur);            update_tree(cur+1,1,n,1);            cur_i=cur;            h++;        }        printf("%s %d\n",str[ans1],ans);    }}void build_tree(int l,int r,int id){    if(l==r)    {        seg_tree[id]=1;        return ;    }    int mid=(l+r)>>1;    build_tree(l,mid,id<<1);    build_tree(mid+1,r,id<<1|1);    push_tree_up(id);}void push_tree_up(int id){    seg_tree[id]=seg_tree[id<<1]+seg_tree[id<<1|1];}void update_tree(int value,int l,int r,int id){    if(l==r)    {        seg_tree[id]--;    // printf("tree[id]=%d",seg_tree[id]);    //    printf("l=%d\n",l);            next_i=num[l];        cur_n--;        if(ans
          
           >1;    if(value<=seg_tree[id<<1])    {        update_tree(value,l,mid,id<<1);    }    else    {        update_tree(value-seg_tree[id<<1],mid+1,r,id<<1|1);    }    push_tree_up(id);}void get_f(){    int i,j;    for(i=1;i<=500000;i++)    for(j=1;i*j<=500000;j++)    {        f[i*j]++;    }}
          
         
        
       
      

 （2）：成段更新：

      1：hdu 1698 just a hook                   

#include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 200010int color[MAXN<<2];int tree[MAXN<<2];void build_tree(int l,int r,int id);void up_date_tree(int left,int right,int l,int r,int id,int value);void push_down(int l,int r,int id);void push_up_tree(int id);int main(){    int tcase,i,j,k,n,value,left,right,num;    while(scanf("%d",&tcase)==1)    {        for(j=1;j<=tcase;j++)        {            scanf("%d",&n);            build_tree(1,n,1);            scanf("%d",&num);            for(i=0;i
          
           >1;    build_tree(l,mid,id<<1);    build_tree(mid+1,r,id<<1|1);}void up_date_tree(int left,int right,int l,int r,int id,int value){    if(left<=l&&right>=r)    {        tree[id]=(r-l+1)*value;        color[id]=value;        return ;    }    push_down(l,r,id);    int mid=l+r>>1;   if(left<=mid) up_date_tree(left,right,l,mid,id<<1,value);   if(right>mid) up_date_tree(left,right,mid+1,r,id<<1|1,value);   push_up_tree(id);}void push_down(int l,int r,int id){    if(color[id])    {        color[id<<1]=color[id];        color[id<<1|1]=color[id];        int mid=l+r>>1;        tree[id<<1]=(mid-l+1)*color[id];        tree[id<<1|1]=(r-mid)*color[id];    }    color[id]=0;}void push_up_tree(int id){    tree[id]=tree[id<<1]+tree[id<<1|1];}
          
         
        
       
      

 (3): poj 3468 A Simple Problem with Integers   

#include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 100010__int64 color[MAXN<<2];__int64 tree[MAXN<<2];int n,num;void build_tree(int l,int r,int id);void push_up_tree(int id);__int64 query_tree(int left,int right,int l,int r,int id);void update_tree(int left,int right,int l,int r,int id,__int64 value);void push_down(int l,int r,int id);int main(){    int i,left,right;    __int64 value;    char str[10];    while(scanf("%d%d",&n,&num)==2)    {        build_tree(1,n,1);        //printf("%I64d\n",tree[4]);        for(i=1;i<=num;i++)        {            scanf("%s",str);            if(str[0]=='Q')            {                scanf("%d%d",&left,&right);               // printf("%s %d %d\n",str,left,right);                printf("%I64d\n",query_tree(left,right,1,n,1));            }            if(str[0]=='C')            {                scanf("%d%d%I64d",&left,&right,&value);              update_tree(left,right,1,n,1,value);            }        }    }}void build_tree(int l,int r,int id){    color[id]=0;    if(l==r)    {        scanf("%I64d",&tree[id]);        return ;    }    int mid=l+r>>1;    build_tree(l,mid,id<<1);    build_tree(mid+1,r,id<<1|1);    push_up_tree(id);}void push_up_tree(int id){    tree[id]=tree[id<<1]+tree[id<<1|1];}__int64 query_tree(int left,int right,int l,int r,int id){    if(left<=l&&right>=r)        return tree[id];    push_down(l,r,id);    int mid=l+r>>1;__int64 ret0=0;    if(left<=mid)        ret0+=query_tree(left,right,l,mid,id<<1);    if(right>mid)        ret0+=query_tree(left,right,mid+1,r,id<<1|1);    return ret0;}void push_down(int l,int r,int id){    if(color[id])    {        int mid=l+r>>1;        color[id<<1]+=color[id];        color[id<<1|1]+=color[id];        tree[id<<1]+=(mid-l+1)*color[id];        tree[id<<1|1]+=(r-mid)*color[id];        color[id]=0;    }}void update_tree(int left,int right,int l,int r,int id, __int64 value){      if(left<=l&&right>=r)      {          color[id]+=value;          tree[id]+=(r-l+1)*value;          return ;      }      push_down(l,r,id);      int mid=l+r>>1;      if(left<=mid)      {         update_tree(left,right,l,mid,id<<1,value);      }      if(right>mid)          update_tree(left,right,mid+1,r,id<<1|1,value);      push_up_tree(id);}
         
        
       
      

 （4）：poj 3255 Help with Intervals                                                          

#include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 131072int c_cover[MAXN<<2],c_xor[MAXN<<2];bool hash[MAXN+10];void update(char op,int left,int right,int l,int r,int id);void f_xor(int id);void push_down(int id);void push_down(int id);void query(int l,int r,int id);int main(){    char op,c_left,c_right;    int i,left,right;    c_xor[1]=0;        c_cover[1]=0;    while(~scanf("%c %c%d,%d%c\n",&op,&c_left,&left,&right,&c_right))    {        left<<=1;        right<<=1;        if(c_left=='(')            left++;        if(c_right==')')            right--;        if(left>right)        {            if(op=='C'||op=='I')            c_cover[1]=c_xor[1]=0;        }        else update(op,left,right,0,MAXN,1);    }        query(0,MAXN,1);        int a=-1,b;        bool flag=false;        for(i=0;i<=MAXN;i++)        {            if(hash[i])               {                   b=i;                   if(a==-1)a=i;               }           else if(a!=-1)           {               if(flag)               printf(" ");               printf("%c%d,%d%c",a&1?'(':'[',a>>1,(b+1)>>1,b&1?')':']');                   flag=true;                   a=-1;           }        }        if(!flag)        printf("empty set");        puts("");}void update(char op,int left,int right,int l,int r,int id){     if(left<=l&&right>=r)     {         if(op=='U')         {             c_cover[id]=1;             c_xor[id]=0;         }         else if(op=='D')         {             c_cover[id]=0;             c_xor[id]=0;         }         else if(op=='S'||op=='C')         {         f_xor(id);         }         return ;    }     push_down(id);     int mid=(l+r)>>1;     if(left<=mid)         update(op,left,right,l,mid,id<<1);     else if(op=='I'||op=='C')     {         c_cover[id<<1]=0;         c_xor[id<<1]=0;     }     if(right>mid)     {         update(op,left,right,mid+1,r,id<<1|1);     }     else if(op=='I'||op=='C')     {         c_cover[id<<1|1]=0;         c_xor[id<<1|1]=0;     }}void f_xor(int id){    if(c_cover[id]!=-1)        c_cover[id]^=1;    else        c_xor[id]^=1;}void push_down(int id){    if(c_cover[id]!=-1)    {        c_cover[id<<1]=c_cover[id<<1|1]=c_cover[id];        c_xor[id<<1]=c_xor[id<<1|1]=0;        c_cover[id]=-1;    }     if(c_xor[id])    {        f_xor(id<<1);        f_xor(id<<1|1);        c_xor[id]=0;    }}void query(int l,int r,int id){    if(c_cover[id]==1)    {        int i;        for(i=l;i<=r;i++)        {            hash[i]=1;        }        return ;    }    else if(c_cover[id]==0)        return ;    if(l==r)        return ;      push_down(id);    int mid=(l+r)>>1;    query(l,mid,id<<1);    query(mid+1,r,id<<1|1);}
         
        
       
      

 （5）：poj 3667 Hotel                     

#include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 55555int lmax[MAXN<<2],rmax[MAXN<<2],mmax[MAXN<<2],cover[MAXN<<2];void build(int l,int r,int id);void update(int left,int right,int l,int r,int id,int value);int query(int value,int l,int r,int id);void pushdown(int id,int l,int r);void pushup(int id,int l,int r);int max(int a,int b);int main(){     int n,m,op,value,left,right,i;     while(scanf("%d%d",&n,&m)==2)     {         build(1,n,1);         while(m--)         {             scanf("%d",&op);             if(op==1)             {                 scanf("%d",&value);                 if(value>mmax[1])                     printf("0\n");                 else                 {                   left=query(value,1,n,1);                   printf("%d\n",left);                   update(left,left+value-1,1,n,1,0);                 }             }             else             {                 scanf("%d%d",&left,&right);                 update(left,left+right-1,1,n,1,1);             }         }     }}void build(int l,int r,int id){    lmax[id]=rmax[id]=mmax[id]=(r-l+1);    cover[id]=-1;    if(l==r)        return;        int mid=l+r>>1;    build(l,mid,id<<1);    build(mid+1,r,id<<1|1);}void update(int left,int right,int l,int r,int id,int value){    if(left<=l&&right>=r)    {        cover[id]=value;        rmax[id]=mmax[id]=lmax[id]=(r-l+1)*value;        return ;    }    if(l==r)    return ;    int mid=l+r>>1;    pushdown(id,l,r);    if(left<=mid)        update(left,right,l,mid,id<<1,value);    if(right>mid)        update(left,right,mid+1,r,id<<1|1,value);    pushup(id,l,r);}int query(int value,int l,int r ,int id){    if(l==r)        return l;        pushdown(id,l,r);    int mid=l+r>>1;    if(mmax[id<<1]>=value)          return query(value,l,mid,id<<1);    else if(rmax[id<<1]+lmax[id<<1|1]>=value)        return mid-rmax[id<<1]+1;    else return query(value,mid+1,r,id<<1|1);    //pushup(id,l,r);}void pushdown(int id,int l,int r){    if(cover[id]!=-1)    {        int mid=l+r>>1;        cover[id<<1]=cover[id<<1|1]=cover[id];        lmax[id<<1]=mmax[id<<1]=rmax[id<<1]=(mid-l+1)*cover[id];        lmax[id<<1|1]=rmax[id<<1|1]=mmax[id<<1|1]=(r-mid)*cover[id];        cover[id]=-1;    }}void pushup(int id,int l,int r){    int mid=r+l>>1;   rmax[id]=rmax[id<<1|1]+((rmax[id<<1|1]==r-mid)?rmax[id<<1]:0);   lmax[id]=lmax[id<<1]+((lmax[id<<1]==mid-l+1)?lmax[id<<1|1]:0);   mmax[id]=max(max(mmax[id<<1],mmax[id<<1|1]),rmax[id<<1]+lmax[id<<1|1]);}int max(int a,int b){    return a>=b?a:b;}