题目描述

给定一段数字，实现如下两个操作：

1. 区间[l,r]中的数值之和
2. 对区间[l,r]中的每一个值开方

输入样例：

4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4

输出样例：

101
11
11

思路：

对于1和0无论如何开方都为它本身，并且数据的最大值为$10^{9}$，所以最多进行5次开方的操作$10^{9}$就会等于1。
根据这一条件每个数值最多只需要修改5次，而区间长度最大为$10^{5}$所以修改操作最多执行$5 * 10^{5}$次。
可以用线段树维护区间和，单次查询的时间复杂度为$O(logn)$,查询最差时间复杂度为$O(m*logn)$;再维护一个值f表示该区间是否需要进行开方的操作（当区间中的数值都为1和0时，该区间就不需要进行修改），这样修改最差的时间复杂度为$O(nlogn)$。

时间复杂度 $O(mlogn + nlogn)$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

#define lc u<<1
#define rc u<<1|1

using namespace std;
typedef long long LL;
const int N = 100010;
struct Node
{
    int l,r;
    LL sum;
    int f;//优化
}tr[N * 4];
int n,m;
int a[N];
int cnt = 0;

void pushup(int u)
{
    tr[u].sum = tr[lc].sum + tr[rc].sum;
    tr[u].f = (tr[lc].f&&tr[rc].f);
}
void build(int u,int l,int r)
{
    if(l==r)
    {
        tr[u] = {l,l,a[l],(a[l]<=1)};
    }
    else
    {
        tr[u] = {l,r};
        int mid = (l + r)>>1;
        build(lc,l,mid);
        build(rc,mid+1,r);
        pushup(u);
    }
}

void modify(int u,int l,int r)
{
    if(tr[u].f) return;//单点修改的优化
    if(tr[u].l == tr[u].r)
    {
        tr[u].sum = sqrt(tr[u].sum);
        tr[u].f = tr[u].sum <= 1;
    }
    else
    {
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(r <= mid) modify(lc,l,r);
        else if(l > mid) modify(rc,l,r);
        else
        {
            modify(lc,l,mid);
            modify(rc,mid+1,r);
        }
        pushup(u);
    }
}

LL query(int u,int l,int r)
{
    if(tr[u].l>=l && tr[u].r <= r) return tr[u].sum;
    int mid = (tr[u].l + tr[u].r)>>1;
    LL res = 0;
    if(l<=mid) res += query(lc,l,r);
    if(r>mid) res += query(rc,l,r);
    return res;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    scanf("%d",&m);

    build(1,1,n);

    int x,l,r;
    while(m--)
    {
        scanf("%d%d%d",&x,&l,&r);
        if(x==1) printf("%lld\n",query(1,l,r));
        else modify(1,l,r);
    }
    return 0;
}