題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=4027

RT，該題要求每次更新是更新所有節點，分別求平方根，查詢是求和。昨晚思前想后找有沒有一個數學上的開平方的和等于和的開平方之類的規律。但是想了想發現這不就是小的時候，如果你這么想那老師就會罵死你的那個- -!

所以顯然這個題是無法按套路成段更新了，懶惰標記也是沒有用了，我們應該去按照區間更新每一個節點。結果TLE了一發，這說明這題不是這么搞，一定還有規律的。注意到題目給數據規模是2^63以及題目紅字所述：開根號全都取下整，除了考慮用longlong以外，我們其實還可以想一下對一個longlong的數據開平方，最終都會變成1。那么在更新這個節點至1的那次update里，更新結束后一定會從葉子rt向上更新父親，如果rt的兄弟節點也是1，那么說明rt的父親已經不再需要更新了（因為1開平方還是1），這時候rt的父親存的結果是1+1=2。也就是(rt+1-rt+1)。推廣到更高的節點，換成區間來表示就是(r-l+1)。我們遇到這種節點就不需要更新了。

特別需要注意的是題目中x和y的大小…會出現x>y的情況……以及，每個case最后都要有一個額外的\n…………（PE到死WA到死）

?

1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <fstream> 8 #include <cassert> 9 #include <cstdio> 10 #include <bitset> 11 #include <vector> 12 #include <deque> 13 #include <queue> 14 #include <stack> 15 #include <ctime> 16 #include <set> 17 #include <map> 18 #include <cmath> 19 20 using namespace std; 21 22 #define fr first 23 #define sc second 24 #define pb(a) push_back(a) 25 #define Rint(a) scanf("%d", &a) 26 #define Rll(a) scanf("%I64d", &a) 27 #define Rs(a) scanf("%s", a) 28 #define FRead() freopen("in", "r", stdin) 29 #define FWrite() freopen("out", "w", stdout) 30 #define Rep(i, len) for(LL i = 0; i < (len); i++) 31 #define For(i, a, len) for(LL i = (a); i < (len); i++) 32 #define Cls(a) memset((a), 0, sizeof(a)) 33 #define Full(a) memset((a), 0x7f7f, sizeof(a)) 34 35 typedef long long LL; 36 #define lrt rt << 1 37 #define rrt rt << 1 | 1 38 const LL maxn = 100100; 39 LL sum[maxn<<2]; 40 LL n, q; 41 42 void pushUP(LL rt) { 43 sum[rt] = sum[lrt] + sum[rrt]; 44 } 45 46 void build(LL l, LL r, LL rt) { 47 if(l == r) { 48 Rll(sum[rt]); 49 return; 50 } 51 LL m = (l + r) >> 1; 52 build(l, m, lrt); 53 build(m+1, r, rrt); 54 pushUP(rt); 55 } 56 57 void update(LL L, LL R, LL l, LL r, LL rt) { 58 if(sum[rt] == r - l + 1) return; 59 if(l == r) { 60 sum[rt] = LL(double(sqrt(sum[rt]))); 61 return; 62 } 63 LL m = (l + r) >> 1; 64 if(m >= L) update(L, R, l, m, lrt); 65 if(m < R) update(L,R, m+1, r, rrt); 66 pushUP(rt); 67 } 68 69 LL query(LL L, LL R, LL l, LL r, LL rt) { 70 if(l >= L && R >= r) return sum[rt]; 71 LL m = (l + r) >> 1; 72 LL ret = 0; 73 if(m >= L) ret += query(L, R, l, m, lrt); 74 if(m < R) ret += query(L, R, m+1, r, rrt); 75 return ret; 76 } 77 78 int main() { 79 // FRead(); 80 LL orz = 1; 81 LL a, b, c; 82 while(~Rll(n)) { 83 Cls(sum); 84 printf("Case #%I64d:\n", orz++); 85 build(1, n, 1); 86 Rll(q); 87 while(q--) { 88 Rll(a); Rll(b); Rll(c); 89 if(b > c) swap(b, c); 90 if(a == 0) update(b, c, 1, n, 1); 91 if(a == 1) cout << query(b, c, 1, n, 1) << endl; 92 } 93 printf("\n"); 94 } 95 return 0; 96 }

?

轉載于:https://www.cnblogs.com/kirai/p/5497216.html

總結

以上是生活随笔為你收集整理的[HDOJ4027]Can you answer these queries?（线段树，特殊成段更新，成段查询）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。