hdu1540 线段树区间合并

先说下题意：

有连续的n个村庄编号1--n 开始相邻的能连续上 现在执行m次操作

1：毁坏村庄a

2：询问与a能连续的村庄的个数

3：修好最后被毁坏的村庄（此处用到栈 注意多次毁坏同一村庄的情况）

整天还是线段树做 对每个节点存3个值

pre ：左端点连续个数

after ：右端点连续个数

Max：整个区间连续个数

跟新操作分为毁坏和维修 用-1和1区别

这道题与别的不同在于他的点询问 可以根据Max来判断

#include
  
   
#include
   
     #include
    
      #include
     
       #include
       
       using namespace std
       ; #define LL(x) (x<<1) #define RR(x) ((x<<1)|1) 
        struct node
        { int pre
       ,after
       ,Max
       ; }num
       [4
       *50000
       ]; int max
       (int a
       ,int b
       ) { return a
       >b
       ?a
       :b
       ; } int deal
       (int L
       ,int R
       ,int mark
       ) { int mid
       =(L
       +R
       )/2
       ; num
       [mark
       ].pre
       =num
       [mark
       ].after
       =num
       [mark
       ].Max
       =R
       -L
       +1
       ; if(L
       ==R
       ) return 0
       ; deal
       (L
       ,mid
       ,LL
       (mark
       )); deal
       (mid
       +1
       ,R
       ,RR
       (mark
       )); return 0
       ; } int update
       (int L
       ,int R
       ,int pos
       ,int mark
       ,int k
       ) { if(L
       ==R
       &&L
       ==pos
       ) { if(k
       ==-1
       ) num
       [mark
       ].pre
       =num
       [mark
       ].after
       =num
       [mark
       ].Max
       =0
       ; else num
       [mark
       ].pre
       =num
       [mark
       ].after
       =num
       [mark
       ].Max
       =1
       ; return 0
       ; } int mid
       =(L
       +R
       )/2
       ; if(pos
       <=mid
       ) update
       (L
       ,mid
       ,pos
       ,LL
       (mark
       ),k
       ); else update
       (mid
       +1
       ,R
       ,pos
       ,RR
       (mark
       ),k
       ); num
       [mark
       ].pre
       =num
       [LL
       (mark
       )].pre
       ; if(num
       [LL
       (mark
       )].pre
       ==mid
       -L
       +1
       ) num
       [mark
       ].pre
       +=num
       [RR
       (mark
       )].pre
       ; num
       [mark
       ].after
       =num
       [RR
       (mark
       )].after
       ; if(num
       [RR
       (mark
       )].after
       ==R
       -mid
       ) num
       [mark
       ].after
       +=num
       [LL
       (mark
       )].after
       ; num
       [mark
       ].Max
       =max
       (num
       [LL
       (mark
       )].Max
       ,num
       [RR
       (mark
       )].Max
       ); num
       [mark
       ].Max
       =max
       (num
       [mark
       ].Max
       ,num
       [LL
       (mark
       )].after
       +num
       [RR
       (mark
       )].pre
       ); return 0
       ; } int find
       (int L
       ,int R
       ,int pos
       ,int mark
       ) { if(num
       [mark
       ].Max
       ==R
       -L
       +1
       ||num
       [mark
       ].Max
       ==0
       ||L
       ==R
       ) { return num
       [mark
       ].Max
       ; } int mid
       =(L
       +R
       )/2
       ; if(pos
       <=mid
       ) { if(pos
       >=mid
       -num
       [LL
       (mark
       )].after
       ) return find
       (L
       ,mid
       ,pos
       ,LL
       (mark
       ))+num
       [RR
       (mark
       )].pre
       ; else return find
       (L
       ,mid
       ,pos
       ,LL
       (mark
       )); } else { if(pos
       <=num
       [RR
       (mark
       )].pre
       +mid
       +1
       ) return find
       (mid
       +1
       ,R
       ,pos
       ,RR
       (mark
       ))+num
       [LL
       (mark
       )].after
       ; else return find
       (mid
       +1
       ,R
       ,pos
       ,RR
       (mark
       )); } } int main() { int n
       ,m
       ,i
       ,j
       ,a
       ; int leap
       [50010
       ]; char str
       [5
       ]; while(~scanf
       ("%d%d"
       ,&n
       ,&m
       )) { deal
       (1
       ,n
       ,1
       ); stack
       
        q
       ; memset
       (leap
       ,0
       ,sizeof(leap
       )); for(i
       =1
       ;i
       <=m
       ;i
       ++) { scanf
       ("%s"
       ,str
       ); if(str
       [0
       ]=='D'
       ) { scanf
       ("%d"
       ,&a
       ); q
       .push
       (a
       ); if(leap
       [a
       ]==0
       ) { leap
       [a
       ]=1
       ; update
       (1
       ,n
       ,a
       ,1
       ,-1
       ); } } else if(str
       [0
       ]=='R'
       ) { int b
       ; while(!q
       .empty
       ()) { b
       =q
       .top
       (); q
       .pop
       (); if(leap
       [b
       ]==1
       ) { leap
       [b
       ]=0
       ; update
       (1
       ,n
       ,b
       ,1
       ,1
       ); break; } } } else { scanf
       ("%d"
       ,&a
       ); if(leap
       [a
       ]==1
       ) printf
       ("0\n"
       ); else printf
       ("%d\n"
       ,find
       (1
       ,n
       ,a
       ,1
       )); } } } return 0
       ; }