HDU 4027 Can you answer these queries?——其实是点更新的区间更新线段树

HDU 4027 Can you answer these queries?——其实是点更新的区间更新线段树

题意：给定一个序列，每次操作可以把一个区间内的所有数变成原来数字的开方，求序列和

思路：表面上是区间更新，但是每个数开方这种操作区间更新的慵懒标记难以做到，所以这个题不用慵懒标记，而是直接采用 单节点更新的思想，但是单节点更新一定会超时，所以做一个剪枝：当当前区间的值全为1时直接return，不进行任何更新，这是显然的，1开方还是1，更新的话只会徒增复杂度，其他的按照一般的模板写就可以了

#include #include #include #include #include using namespace std;const int maxn = 1e5 + 10;typedef long long ll;ll kase, n, q, date[maxn], segTree[maxn<<2];void pushup(int root) { segTree[root] = segTree[root<<1] + segTree[root<<1|1];}void build(int L, int R, int root) { if (L == R) { segTree[root] = date[L]; return; } int mid = (L + R)>>1; build(L, mid, root<<1); build(mid + 1, R, root<<1|1); pushup(root);}void update_interval(int L, int R, int root, int uL, int uR) { if (uL <= L && R <= uR && R - L + 1 == segTree[root]) return; if (L == R) { segTree[root] = (int)(sqrt(segTree[root])); return; } int mid = (L + R)>>1; if (uL <= mid) { update_interval(L, mid, root<<1, uL, uR); } if (uR > mid) { update_interval(mid + 1, R, root<<1|1, uL, uR); } pushup(root);}ll query(int L, int R, int root, int qL, int qR) { if (qL <= L && R <= qR) { return segTree[root]; } int mid = (L + R)>>1; ll sum = 0; if (qL <= mid) { sum += query(L, mid, root<<1, qL, qR); } if (qR > mid) { sum += query(mid + 1, R, root<<1|1, qL, qR); } return sum;}int main(){ kase = 0; while (scanf("%lld", &n) == 1) { printf("Case #%d:\n", ++kase); for (int i = 1; i <= n; i++) { scanf("%lld", &date[i]); } build(1, n, 1); scanf("%lld", &q); while (q--) { int a, b, c; scanf("%d %d %d", &a, &b, &c); if (b > c) swap(b, c); if (a == 0) { update_interval(1, n, 1, b, c); } else { printf("%lld\n", query(1, n, 1, b, c)); } } printf("\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。