题解 P4145 【上帝造题的七分钟2】

这道题的关键在于，sqrt(1)==1 也就是说，如果一个区间的最大值为1，我们就可以直接跳过这段区间的修改。只有最大值大于1时才有修改的必要。 而题中的数值大小范围在(0,1e12)之间。 我们可以用计算器得知：  每个数至多六次开平方便可得到1 每次暴力修改复杂度为logn，总复杂度nlogn。数据范围只有1e5，因此不用在意常数的影响。 ```cpp #include<cstdio> #include<cctype> #include<cstring> #include<cmath> #define LL long long const int INF = 1000000010; LL int Read()//快读 { LL x = 0;char c = getchar(); while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = (x << 3) + (x << 1) + c -'0'; c = getchar(); } return x; } struct Node { int l, r; LL sum, maxn; }seg_tree[400000]; void Update(int p)//向上修改 { seg_tree[p].sum = seg_tree[p << 1].sum + seg_tree[p << 1 | 1].sum; seg_tree[p].maxn = seg_tree[p << 1].maxn > seg_tree[p << 1 | 1].maxn ? seg_tree[p << 1].maxn : seg_tree[p << 1 | 1].maxn; } LL num[100005]; void Build(int p, int l, int r) { seg_tree[p].l = l; seg_tree[p].r = r; if(l == r) { seg_tree[p].sum = seg_tree[p].maxn = num[l]; return; } int mid = l + r >> 1; Build(p << 1, l, mid); Build(p << 1 | 1, mid + 1, r); Update(p); } void Change(int p, int l, int r) { if(seg_tree[p].l == seg_tree[p].r) { seg_tree[p].sum = sqrt(seg_tree[p].sum); seg_tree[p].maxn = sqrt(seg_tree[p].maxn); return; } int mid = seg_tree[p].l + seg_tree[p].r >> 1; if(l <= mid && seg_tree[p << 1].maxn > 1) Change(p << 1, l, r); if(mid < r && seg_tree[p << 1 | 1].maxn > 1) Change(p << 1 | 1, l, r); //当maxn > 1时暴力修改 Update(p); } LL Query(int p, int l, int r) { if(l <= seg_tree[p].l && seg_tree[p].r <= r) return seg_tree[p].sum; int mid = seg_tree[p].l + seg_tree[p].r >> 1; LL ans = 0; if(l <= mid) ans += Query(p << 1,l,r); if(mid < r) ans += Query(p << 1 | 1,l,r); return ans; } int main() { int n = Read(); for(int i = 1; i <= n; ++i) num[i] = Read(); Build(1, 1, n); int m = Read(), opt, l, r; while(m--) { opt = Read(), l = Read(), r = Read(); if(l > r) { int swap = l; l = r; r = swap; } if(opt == 0) Change(1,l,r); else printf("%lld\n",Query(1,l,r)); } return 0; } ```