题解 P4145 【上帝造题的七分钟2】
SuperJvRuo
2018-01-23 16:12:37
这道题的关键在于,sqrt(1)==1
也就是说,如果一个区间的最大值为1,我们就可以直接跳过这段区间的修改。只有最大值大于1时才有修改的必要。
而题中的数值大小范围在(0,1e12)之间。
我们可以用计算器得知:
![](https://cdn.luogu.com.cn/upload/pic/13485.png)
每个数至多六次开平方便可得到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;
}
```