題目鏈接
題意：給定一個數列，兩種操作
0 a b 把[a,b]區間內的數字都開根
1 a b 詢問區間[a,b]和
思路：注意開根最多開到1或0就不在變化，那麼一個數字最多開63次，然後題目保證數列和小於2^63，所以實際上對於每個數字的修改總次數並不多，因此修改操作每次就單點修改，線段樹多開一個標記，表示這個區間是否全部都已經不變了
代碼：
#include#include #include #include using namespace std; typedef long long ll; const int N = 100005; #define lson(x) ((x<<1)+1) #define rson(x) ((x<<1)+2) struct Node { int l, r; ll sum; bool cover; } node[4 * N]; int n; void pushup(int x) { node[x].cover = (node[lson(x)].cover && node[rson(x)].cover); node[x].sum = node[lson(x)].sum + node[rson(x)].sum; } void build(int l, int r, int x = 0) { node[x].l = l; node[x].r = r; node[x].cover = false; if (l == r) { scanf("%I64d", &node[x].sum); if (node[x].sum == 0 || node[x].sum == 1) node[x].cover = true; return; } int mid = (l + r) / 2; build(l, mid, lson(x)); build(mid + 1, r, rson(x)); pushup(x); } void add(int l, int r, int x = 0) { if (node[x].cover) return; if (node[x].l == node[x].r) { node[x].sum = (ll)sqrt(node[x].sum * 1.0); if (node[x].sum == 1) node[x].cover = true; return; } int mid = (node[x].l + node[x].r) / 2; if (l <= mid) add(l, r, lson(x)); if (r > mid) add(l, r, rson(x)); pushup(x); } ll query(int l, int r, int x = 0) { if (node[x].l >= l && node[x].r <= r) return node[x].sum; int mid = (node[x].l + node[x].r) / 2; ll ans = 0; if (l <= mid) ans += query(l, r, lson(x)); if (r > mid) ans += query(l, r, rson(x)); return ans; } int main() { int cas = 0; while (~scanf("%d", &n)) { build(1, n); scanf("%d", &n); int op, a, b; printf("Case #%d:\n", ++cas); while (n--) { scanf("%d%d%d", &op, &a, &b); if (a > b) swap(a, b); if (op == 0) add(a, b); else printf("%I64d\n", query(a, b)); } printf("\n"); } return 0; }
