hdu5023 （ 广州网络赛 ） 线段树

题意是给你n个连续的点（1-n） m次操作 开始每个点都为2

两种操作

1：把一段区间的点变为c

2：询问区间有多少种点

很明显的线段树 对每个节点

flash表示该节点是否全为一样的数 若是 则flash=这个数否则 flash=-1；

数组color记录该节点输得状态 1表示有0表示没有（我开成字符型 之前为int超类存了 真是无语）

然后 有更新和查询操作

#include
  
   
#include
   
     #include
     
     using namespace std
     ; #define LL(x) (x<<1) #define RR(x) ((x<<1)|1) 
      struct node
      { char color
     [31
     ]; int flash
     ; }num
     [3
     * 1000000
     ]; int leap
     [31
     ]; int change
     (int mark
     ,int k
     ) { for(int i
     =1
     ;i
     <=30
     ;i
     ++) { num
     [mark
     ].color
     [i
     ]='0'
     ; } num
     [mark
     ].color
     [k
     ]='1'
     ; return 0
     ; } int deal
     (int L
     ,int R
     ,int mark
     ) { num
     [mark
     ].flash
     =2
     ; change
     (mark
     ,2
     ); int mid
     =(L
     +R
     )/2
     ; if(L
     ==R
     ) return 0
     ; deal
     (L
     ,mid
     ,LL
     (mark
     )); deal
     (mid
     +1
     ,R
     ,RR
     (mark
     )); return 0
     ; }//注意题目说开始时每个点都是2 int update
     (int L
     ,int R
     ,int left
     ,int right
     ,int mark
     ,int k
     ) { int mid
     =(L
     +R
     )/2
     ; if(num
     [mark
     ].flash
     ==k
     ) return 0
     ;//一个小优化 if(L
     ==left
     &&R
     ==right
     ) { num
     [mark
     ].flash
     =k
     ; change
     (mark
     ,k
     ); return 0
     ; } if(num
     [mark
     ].flash
     >0
     ) { num
     [LL
     (mark
     )].flash
     =num
     [RR
     (mark
     )].flash
     =num
     [mark
     ].flash
     ; change
     (LL
     (mark
     ),num
     [mark
     ].flash
     ); change
     (RR
     (mark
     ),num
     [mark
     ].flash
     ); } if(right
     <=mid
     ) { update
     (L
     ,mid
     ,left
     ,right
     ,LL
     (mark
     ),k
     ); } else if(left
     >mid
     ) { update
     (mid
     +1
     ,R
     ,left
     ,right
     ,RR
     (mark
     ),k
     ); } else { update
     (L
     ,mid
     ,left
     ,mid
     ,LL
     (mark
     ),k
     ); update
     (mid
     +1
     ,R
     ,mid
     +1
     ,right
     ,RR
     (mark
     ),k
     ); } for(int i
     =1
     ;i
     <=30
     ;i
     ++) { if(num
     [LL
     (mark
     )].color
     [i
     ]=='1'
     ||num
     [RR
     (mark
     )].color
     [i
     ]=='1'
     ) { num
     [mark
     ].color
     [i
     ]='1'
     ; } else num
     [mark
     ].color
     [i
     ]='0'
     ; } if(num
     [LL
     (mark
     )].flash
     ==num
     [RR
     (mark
     )].flash
     &&num
     [LL
     (mark
     )].flash
     >0
     ) num
     [mark
     ].flash
     =num
     [LL
     (mark
     )].flash
     ; else num
     [mark
     ].flash
     =-1
     ; return 0
     ; } int find
     (int L
     ,int R
     ,int left
     ,int right
     ,int mark
     ) { int mid
     =(L
     +R
     )/2
     ; if(num
     [mark
     ].flash
     !=-1
     ) { leap
     [num
     [mark
     ].flash
     ]=1
     ; return 0
     ; } if(L
     ==left
     &&R
     ==right
     ) { for(int i
     =1
     ;i
     <=30
     ;i
     ++) { if(num
     [mark
     ].color
     [i
     ]=='1'
     ) leap
     [i
     ]=1
     ; } } if(right
     <=mid
     ) { find
     (L
     ,mid
     ,left
     ,right
     ,LL
     (mark
     )); } else if(left
     >mid
     ) { find
     (mid
     +1
     ,R
     ,left
     ,right
     ,RR
     (mark
     )); } else { find
     (L
     ,mid
     ,left
     ,mid
     ,LL
     (mark
     )); find
     (mid
     +1
     ,R
     ,mid
     +1
     ,right
     ,RR
     (mark
     )); } return 0
     ; } int main() { int n
     ,m
     ,i
     ,j
     ,a
     ,b
     ,c
     ; char str
     [5
     ]; while(~scanf
     ("%d%d"
     ,&n
     ,&m
     ),n
     +m
     ) { deal
     (1
     ,n
     ,1
     ); for(j
     =1
     ;j
     <=m
     ;j
     ++) { scanf
     ("%s"
     ,str
     ); if(str
     [0
     ]=='P'
     ) { scanf
     ("%d%d%d"
     ,&a
     ,&b
     ,&c
     ); update
     (1
     ,n
     ,a
     ,b
     ,1
     ,c
     ); } else { scanf
     ("%d%d"
     ,&a
     ,&b
     ); memset
     (leap
     ,0
     ,sizeof(leap
     )); find
     (1
     ,n
     ,a
     ,b
     ,1
     ); int d
     =1
     ; for(i
     =1
     ;i
     <=30
     ;i
     ++) { if(leap
     [i
     ]) { if(d
     !=1
     ) printf
     (" "
     ); printf
     ("%d"
     ,i
     ); d
     ++; } } printf
     ("\n"
     ); } } } return 0
     ; }