SPOJ2713GSS4 - Can you answer these queries IV(线段树)
程序员文章站
2022-12-24 11:10:45
题意 Sol 讲过无数次了。。很显然,一个$10^12$的数开方不超过$8$次后就会变为$1$ 因此直接暴力更改即可,维护一下这段区间是否被全改为了$1$ 双倍经验:https://www.luogu.org/problemnew/show/P4145 ......
题意
sol
讲过无数次了。。很显然,一个$10^12$的数开方不超过$8$次后就会变为$1$
因此直接暴力更改即可,维护一下这段区间是否被全改为了$1$
双倍经验:https://www.luogu.org/problemnew/show/p4145
#include<cstdio> #include<algorithm> #include<stack> #include<queue> #include<cmath> #define int long long #define pair pair<int, int> #define fi first #define se second #define mp(x, y) make_pair(x, y) using namespace std; const int maxn = 1e6 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m; int a[maxn]; #define ls k << 1 #define rs k << 1 | 1 struct node { int l, r, w, f; }t[maxn]; void update(int k) { if(t[ls].f && t[rs].f) t[k].f = 1; t[k].w = t[ls].w + t[rs].w; } void build(int k, int ll, int rr) { t[k] = (node) {ll, rr}; if(ll == rr) { t[k].w = a[ll]; return ; } int mid = ll + rr >> 1; build(ls, ll, mid); build(rs, mid + 1, rr); update(k); } void push(int k) { if(t[k].f) return ; if(t[k].l == t[k].r) { t[k].w = sqrt(t[k].w); if(t[k].w == 1) t[k].f = 1; return ; } push(ls); push(rs); update(k); } void intsqrt(int k, int ll, int rr) { if(ll <= t[k].l && t[k].r <= rr) { if(t[k].f) return ; push(k); return ; } int mid = t[k].l + t[k].r >> 1; if(ll <= mid) intsqrt(ls, ll, rr); if(rr > mid) intsqrt(rs, ll, rr); update(k); } int intsum(int k, int ll, int rr) { if(ll <= t[k].l && t[k].r <= rr) return t[k].w; int mid = t[k].l + t[k].r >> 1; if(ll > mid) return intsum(rs, ll, rr); else if(rr <= mid) return intsum(ls, ll, rr); else return intsum(ls, ll, rr) + intsum(rs, ll, rr); } main() { int tot = 0; while(scanf("%d", &n) != eof) { printf("case #%d:\n", ++tot); for(int i = 1; i <= n; i++) a[i] = read(); build(1, 1, n); m = read(); while(m--) { int k = read(), l = read(), r = read(); if(l > r) swap(l, r); if(k == 0) intsqrt(1, l, r); else printf("%lld\n", intsum(1, l, r)); } puts(""); } return 0; } /* */