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

SuperJvRuo · 2018-01-23 16:12:37 · 题解

这道题的关键在于，sqrt(1)==1

也就是说，如果一个区间的最大值为1，我们就可以直接跳过这段区间的修改。只有最大值大于1时才有修改的必要。

而题中的数值大小范围在(0,1e12)之间。

我们可以用计算器得知：

每个数至多六次开平方便可得到1

每次暴力修改复杂度为logn，总复杂度nlogn。数据范围只有1e5，因此不用在意常数的影响。

#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;
}