HDU 4027 线段树-白红宇

HDU 4027 线段树

阅读量：2439 次

发布时间：2019-05-10

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

/*******************************************************************************   去年上海赛区网络赛线段树水题，首先虽然数据比较吓人，是64位int，但是开方不了几次，所以只要记录那段区间的数时候都小于等于1就行了，0和1都不能再往下开方了，所以更新到底了～注意有x>y的情况。。。*******************************************************************************/#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 __int64 LL; //VCtypedef unsigned __int64 ULL;typedef pair
                              
                                PII;typedef pair
                               
                                 PLL;typedef pair
                                
                                  PDD;typedef vector
                                 
                                   VI;typedef vector
                                  
                                    VC;typedef vector
                                   
                                     VF;typedef vector
                                    
                                      VS;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;};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 = 100004;int n, m;LL arr[MAXN];struct Node{ int left, right; LL sum; bool cover; int mid() { return (left + right) >> 1; } 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 updateST(int t){ if (st[ ll(t) ].cover && st[ rr(t) ].cover) { st[t].cover = true; st[t].sum = st[ ll(t) ].sum + st[ rr(t) ].sum; } if (st[t].sum <= st[t].len()) { st[t].cover = true; } return ;}void buildST(int l, int r, int t){ st[t].left = l; st[t].right = r; st[t].cover = false; if (l == r) { st[t].sum = arr[l]; st[t].cover = true; return ; } buildST(l, st[t].mid(), ll(t)); buildST(st[t].mid() + 1, r, rr(t)); updateST(t); return ;}void modifyST(int l, int r, int t){ if (st[t].left == st[t].right) { st[t].sum = SC(int, floor(sqrt(st[t].sum + 0.0))); return ; } if (l <= st[t].left && st[t].right <= r) { if (st[t].sum <= st[t].len()) { st[t].cover = true; return ; } } int mid = st[t].mid(); if (r <= mid) { modifyST(l, r, ll(t)); } else if (l > mid) { modifyST(l, r, rr(t)); } else { modifyST(l, mid, ll(t)); modifyST(mid + 1, r, rr(t)); } updateST(t); return ;}LL queryST(int l, int r, int t){ if (l <= st[t].left && st[t].right <= r) { if (st[t].cover) { return st[t].sum; } } int mid = st[t].mid(); if (r <= mid) { return queryST(l, r, ll(t)); } else if (l > mid) { return queryST(l, r, rr(t)); } return queryST(l, mid, ll(t)) + queryST(mid + 1, r, rr(t));}void ace(){ int cas = 1; int op, low, high; while (scanf("%d", &n) != EOF) { for (int i = 1; i <= n; ++i) { scanf("%I64d", arr + i); } scanf("%d", &m); buildST(1, n, 1); printf("Case #%d:\n", cas++); while (m--) { scanf("%d %d %d", &op, &low, &high); if (low > high) { swap(low, high); } if (0 == op) { modifyST(low, high, 1); } else { printf("%I64d\n", queryST(low, high, 1)); } } puts(""); } return ;}int main(){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);#endif ace(); return 0;}/*******************************************************************************Test Data...101 2 3 4 5 6 7 8 9 1050 1 101 1 101 1 50 5 81 4 8*******************************************************************************/