HDU 3308 线段树+区间合并-白红宇

HDU 3308 线段树+区间合并

阅读量：2439 次

发布时间：2019-05-10

本文共 3913 字，大约阅读时间需要 13 分钟。

/****************************************************************************************************    尼玛。。。一句话没加能WA一个礼拜。。。线段树+区间合并，主要是区间合并的细节问题。。。****************************************************************************************************/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         #include 
                         #include 
                          
                           using namespace std;#define LOWBIT(x) ( (x) & ( (x) ^ ( (x) - 1 ) ) )#define CLR(x, k) memset((x), (k), sizeof(x))#define CPY(t, s) memcpy((t), (s), sizeof(s))#define SC(t, s) static_cast
                           
                            (s)#define LEN(s) static_cast
                            
                             ( strlen((s)) )#define SZ(s) static_cast
                             
                              ( (s).size() )typedef double LF;//typedef long long LL; //GNU C++//typedef unsigned long long ULL;typedef __int64 LL; //Visual C++ 2010typedef unsigned __int64 ULL;typedef pair
                              
                                PII;typedef pair
                               
                                 PLL;typedef pair
                                
                                  PDD;typedef map
                                 
                                  ::iterator MI;typedef vector
                                  
                                   ::iterator VI;typedef list
                                   
                                    ::iterator LI;typedef set
                                    
                                     ::iterator SI;template 
                                     
                                      T sqa(const T &x){ return x * x;}template 
                                      
                                       T gcd(T a, T b){ if (!a || !b) { return max(a, b); } T t; while (t = a % b) { a = b; b = t; } return b;}template 
                                       
                                        T ext_gcd(T a, T b, T &x, T &y){ if (!b) { x = 1; y = 0; return a; } T d = ext_gcd(b, a % b, x, y); T t = x; x = y; y = t - a / b * y; return d;}template 
                                        
                                         T invmod(T a, T p){ LL inv, y; ext_gcd(a, p, inv, y); inv < 0 ? inv += p : 0; return inv;}const int INF_INT = 0x3f3f3f3f;const LL INF_LL = 0x7fffffffffffffffLL; //15fconst double oo = 10e9;const double eps = 10e-7;const double PI = acos(-1.0);#define ONLINE_JUDGEconst int MAXN = 200004;int test, n, m, arr[MAXN];struct Node{ int left, right; int lmx, rmx, mmx; int len() { return right - left + 1; }}st[MAXN << 2];int inline ll(const int &x){ return x << 1;}int inline rr(const int &x){ return x << 1 | 1;}void initST(){ CLR(st, 0); return ;}void updateMX(int t){ st[t].lmx = st[ ll(t) ].lmx; st[t].rmx = st[ rr(t )].rmx; int &mx = st[t].mmx; mx = 0; //就TMD这句话没加。。。 if (arr[ st[ ll(t) ].right ] < arr[ st[ ll(t) ].right + 1 ]) //左右节点的衔接处，细节 { if (st[ ll(t) ].len() == st[ ll(t) ].lmx) { st[t].lmx += st[ rr(t) ].lmx; } if (st[ rr(t) ].len() == st[ rr(t) ].rmx) { st[t].rmx += st[ ll(t) ].rmx; } mx = st[ ll(t) ].rmx + st[ rr(t) ].lmx; } mx = max( mx, max( st[t].lmx, st[t].rmx ) ); //显然st[t].mmx必然是这几个量中最大的值 mx = max( mx, max( st[ ll(t) ].mmx, st[ rr(t) ].mmx ) ); return ;}void buildST(int l, int r, int t){ st[t].left = l; st[t].right = r; if (l == r) { st[t].lmx = st[t].rmx = st[t].mmx = 1; return ; } int mid = (l + r) >> 1; buildST(l, mid, ll(t)); buildST(mid + 1, r, rr(t)); updateMX(t); //更新节点 return ;}void updateST(int l, int r, int t){ if (l <= st[t].left && st[t].right <= r) { return ; } int mid = st[ ll(t) ].right; if (r <= mid) { updateST(l, r, ll(t)); } else if (l > mid) { updateST(l, r, rr(t)); } else { updateST(l, mid, ll(t)); updateST(mid + 1, r, rr(t)); } updateMX(t); //更新节点 return ;}int queryST(int l, int r, int t){ if (l <= st[t].left && st[t].right <= r) { return st[t].mmx; } int mid = st[ ll(t) ].right; if (r <= mid) { return queryST(l, r, ll(t)); } else if (l > mid) { return queryST(l, r, rr(t)); } int mx = max( queryST(l, mid, ll(t)), queryST(mid + 1, r, rr(t)) ); if (arr[mid] < arr[mid + 1]) //这个地方有trick。。。要当心左右子节点可以衔接的情况 { mx = max( mx, min( st[ ll(t) ].rmx, mid - l + 1 ) + min( st[ rr(t) ].lmx, r - mid ) ); } return mx;}void ace(){ char op[2]; int a, b; for (scanf("%d", &test); test--; ) { scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) { scanf("%d", arr + i); } initST(); buildST(0, n - 1, 1); while (m--) { scanf("%s %d %d", op, &a, &b); if ('U' == op[0]) { arr[a] = b; updateST(a, a, 1); } else { printf("%d\n", queryST(a, b, 1)); } } } return ;}int main(){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);#endif ace(); return 0;}