hdu4973 線段樹（題目不錯，用了點，段，更新查找還有DFS）

題意：

      給你一個初始序列，初始序列長度n,分别為1 2 3 4 5 ....n,有兩種操作

（1）D l r 把l_r之間的資料都複制一遍 1 2 3 4 5 6 D 2 4 = 1 2 2 3 3 4 4 5 6

（2）Q l r 詢問lr之間的數字出現的最大次數 1 2 2 3 3 4 4 4 5 Q 1 3 = 2

思路：

      這個題目可以用線段樹來解決，我們可以建一棵樹1--n的，這個題目要注意一點就是無論怎麼複制，所有的數字依然是連續的，對于線段樹的每一個節點，我們有兩個權值，區間元素個數，區間元素出現次數最大值，這樣每次遇到一個區間，我們就把這個區間拆成三部分，左邊的點，中間部分，右邊的一個點，兩邊的用點更新，中間部分用段更新，每次給一個範圍我們就可以根據這個範圍找到範圍所涉及到的數字範圍（1--n），比如

11223344445555 現在給出範圍3 13 =則找到的範圍是2-5，這樣點2,5單獨處理，3-4用段更新處理，找的過程中我用的是深搜找的，對于每個點的資訊，其實可以再深搜裡直接一起找出來，但是我自己當初沒想到，直接又多寫了一個斷詢問，雖然麻煩點，但也AC了，具體的看代碼吧！

#include<stdio.h>
#include<string.h>

#define lson l ,mid ,t << 1
#define rson mid + 1 ,r ,t << 1 | 1
#define N_node 200000

__int64 sum[N_node] ,max[N_node] ,mark[N_node];

__int64 maxx(__int64 x ,__int64 y)
{
   return x > y ? x : y;
}

void Pushup(__int64 t)
{
   sum[t] = sum[t<<1] + sum[t<<1|1];
   max[t] = maxx(max[t<<1] ,max[t<<1|1]);
}

void Pushdown(__int64 t)
{
   if(mark[t])
   {
      mark[t<<1] += mark[t];
      mark[t<<1|1] += mark[t];
      sum[t<<1] <<= mark[t];
      sum[t<<1|1] <<= mark[t];
      max[t<<1] <<= mark[t];
      max[t<<1|1] <<= mark[t];    
      mark[t] = 0;
   }  
   
}

void BuidTree(__int64 l ,__int64 r ,__int64 t)
{
   max[t] = sum[t] = mark[t] = 0;
   if(l == r)
   {
      max[t] = sum[t] = 1;
      return;
   }
   __int64 mid = (l + r) >> 1;
   BuidTree(lson);
   BuidTree(rson);
   Pushup(t);
}

void Update_1(__int64 l ,__int64 r ,__int64 t ,__int64 a ,__int64 b)
{//點更新 
   if(l == r)
   {
      max[t] += b;
      sum[t] += b;
      return;
   }
   Pushdown(t);
   __int64 mid = (l + r) >> 1;
   if(a <= mid) Update_1(lson ,a ,b);
   else Update_1(rson ,a ,b);
   Pushup(t);
}


void Update_2(__int64 l ,__int64 r ,__int64 t ,__int64 a ,__int64 b)
{//段更新
   if(a <= l && b >= r)
   {
      sum[t] *= 2;
      max[t] *= 2;
      mark[t] ++;
      return;
   }
   Pushdown(t);
   __int64 mid = (l + r) >> 1;
   if(a <= mid) Update_2(lson ,a ,b);
   if(b > mid)  Update_2(rson ,a ,b);
   Pushup(t);
}

__int64 Query_1(__int64 l ,__int64 r ,__int64 t ,__int64 a ,__int64 b)
{//段查找，區間最大值
    if(a <= l && b >= r)
    return max[t];
    Pushdown(t);
    __int64 mid = (l + r) >> 1;
    __int64 now = 0;
    if(a <= mid) now = Query_1(lson ,a ,b);
    if(b > mid)  now = maxx(now ,Query_1(rson ,a ,b));
    return now;
}

__int64 Query_2(__int64 l ,__int64 r ,__int64 t ,__int64 a ,__int64 b)
{//段查找，區間和
    if(a <= l && b >= r) 
    return sum[t];
    Pushdown(t);
    __int64 mid = (l + r) >> 1;
    __int64 now = 0;
    if(a <= mid) now = Query_2(lson ,a ,b);
    if(b > mid) now += Query_2(rson ,a ,b);
    return now;
}

__int64 DFS_Find(__int64 l ,__int64 r ,__int64 t ,__int64 now ,__int64 ss)
{//深搜查找範圍所在的點
   if(l == r) return l;
   Pushdown(t);
   __int64 mid = (l + r) >> 1;
   if(now <= sum[t<<1] + ss)return  DFS_Find(lson ,now ,ss);
   else return DFS_Find(rson ,now ,ss + sum[t<<1]);
}

int main ()
{
   int t ,cas = 1 ,n ,m ,i;
   __int64 a ,b;
   char str[5];
   scanf("%d" ,&t);
   while(t--)
   {
      scanf("%d %d" ,&n ,&m);
      BuidTree(1 ,n ,1);
      printf("Case #%d:\n" ,cas ++);
      for(i = 1 ;i <= m ;i ++)
      {
         scanf("%s %I64d %I64d" ,str ,&a ,&b);
         __int64 l = DFS_Find(1 ,n ,1 ,a ,0);
         __int64 r = DFS_Find(1 ,n ,1 ,b ,0);
         if(str[0] == 'D')
         {
            if(l == r)
            {
               Update_1(1 ,n ,1 ,l ,b - a + 1);
               continue;
            }
            __int64 ls = Query_2(1 ,n ,1 ,1 ,l) - a + 1;
            __int64 rs = b - Query_2(1 ,n ,1 ,1 ,r - 1);
            Update_1(1 ,n ,1 ,l ,ls);
            Update_1(1 ,n ,1 ,r ,rs);
            if(r - l > 1)
            Update_2(1 ,n ,1 ,l + 1 ,r - 1);
         }
         else
         {
            if(l == r)
            {
               printf("%I64d\n" ,b - a + 1);
               continue;
            }
            __int64 now = 0;
            __int64 ls = Query_2(1 ,n ,1 ,1 ,l) - a + 1;
            __int64 rs = b - Query_2(1 ,n ,1 ,1 ,r - 1);         
            if(r - l > 1) now = Query_1(1 ,n ,1 ,l + 1 ,r - 1);
            if(now < ls) now = ls;
            if(now < rs) now = rs;
            printf("%I64d\n" ,now);
         }
      }
   }
   return 0;
}