哈尔滨工程大学 ACM online contest 1008 how many

题目链接   http://acm.hrbeu.edu.cn/index.php?act=status&cid=115
保留      最大值  最小值 和 区间个数的线段树； 

#include<iostream>
#include<cstring>
#include<stdio.h>
#include<cstring>
using namespace std;

int N,M,arr[2512345],res;
struct date
{
    int Max,Min,Num,sum,lt,rt;
}node[11234567];
inline int max( int a,int b ){return a>b?a:b;}
inline int min( int a,int b ){return a>b?b:a;}

void build_node( int lt,int rt,int t )
{
    node[t].lt = lt;
    node[t].rt = rt;
    node[t].sum = 0;
    node[t].Num = rt - lt + 1;
    if( lt == rt )
    {
        node[t].Max = arr[lt];
        node[t].Min = arr[lt];
        return ;
    }
    int mid = ( lt+rt )>>1;
    build_node( lt,mid,t<<1 );
    build_node( mid+1,rt,t<<1|1 );
    node[t].Max = max( node[t<<1].Max,node[t<<1|1].Max );
    node[t].Min = min( node[t<<1].Min,node[t<<1|1].Min );
}
void push_down( int t )
{
      node[t<<1].sum += node[t].sum;
      node[t<<1].Max += node[t].sum;
      node[t<<1].Min += node[t].sum;
      node[t<<1|1].sum += node[t].sum;
      node[t<<1|1].Max += node[t].sum;
      node[t<<1|1].Min += node[t].sum;
      node[t].sum = 0;
}
void update( int lt,int rt,int val,int t )
{
      if( node[t].lt == lt && node[t].rt == rt )
      {
          node[t].Max += val;
          node[t].Min += val;
          node[t].sum += val; return ;
      }
      if( node[t].sum != 0 ) push_down( t );
      if( node[t<<1].rt >= rt ) update( lt,rt,val,t<<1 );
      else if( node[t<<1|1].lt <= lt ) update( lt,rt,val,t<<1|1 );
           else
           {
               update( lt,node[t<<1].rt,val,t<<1 );
               update( node[t<<1|1].lt,rt,val,t<<1|1 );
           }
    node[t].Max = max( node[t<<1].Max,node[t<<1|1].Max );
    node[t].Min = min( node[t<<1].Min,node[t<<1|1].Min );
}
void query( int lt,int rt,int ll,int rr,int t )
{
    if( ll > node[t].Max ) return;
    if( rr < node[t].Min ) return;
    if( node[t].Max <= rr && node[t].Min >= ll )
    if( node[t].lt == lt && node[t].rt == rt ){
        res += node[t].Num; return;
    }
    if( node[t].sum != 0 ) push_down( t );
    if( node[t<<1].rt >= rt ) query( lt,rt,ll,rr,t<<1 );
    else if( node[t<<1|1].lt <= lt )query( lt,rt,ll,rr,t<<1|1 );
         else
         {
             query( lt,node[t<<1].rt,ll,rr,t<<1 );
             query( node[t<<1|1].lt,rt,ll,rr,t<<1|1 );
         }
}
int main( )
{
    char str[2];
    int lt,rt,L,R,val;
    while( scanf("%d%d",&N,&M) != EOF )
    {
        for( int i = 1; i <= N; i++ )
           scanf("%d",&arr[i]);
        build_node( 1,N,1 );
        for( int i = 1; i <= M; i++ )
        {
           scanf("%s",&str);
           if( str[0] == 'Q' )
           {
               scanf("%d%d%d%d",&lt,&rt,&L,&R);
               res = 0; query( lt,rt,L,R,1 );
               printf("%d\n",res);
           }
           else
           {
               scanf("%d%d%d",&lt,&rt,&val);
               update( lt,rt,val,1 );
           }
        }
    }
    return 0;
}
/*

9 4
1 2 3 4 5 6 7 8 9
Q 1 9 1 9
C 1 4 10
C 6 9 -10
Q 1 9 1 9

9 3
1 2 3 4 5 6 7 8 9
C 1 9 -8
Q 1 9 1 9
Q 1 1 1 9


*/