codevs2492 上帝造題的七分鐘 2【線段樹】

題目大意：

維護一個序列，支援區間開方（下取整）和求和操作。n<=100000,ai<=1e12.

解題思路：

一個數最多卡5、6次方就變為了1.

是以如果目前全為1，就不修改，否則暴力修改到底。

查詢同普通線段樹。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N=;
int n,m;
ll a[N],sum[N<<];

void build(int k,int l,int r)
{
    if(l==r){sum[k]=a[l];return;}
    int mid=l+r>>;
    build(k<<,l,mid),build(k<<|,mid+,r);
    sum[k]=sum[k<<]+sum[k<<|];
}

void modify(int k,int l,int r,int x,int y)
{
    if(sum[k]==r-l+)return;
    if(l==r){sum[k]=sqrt(sum[k]);return;}
    int mid=l+r>>;
    if(y<=mid)modify(k<<,l,mid,x,y);
    else if(x>mid)modify(k<<|,mid+,r,x,y);
    else modify(k<<,l,mid,x,mid),modify(k<<|,mid+,r,mid+,y);
    sum[k]=sum[k<<]+sum[k<<|];
}

ll query(int k,int l,int r,int x,int y)
{
    if(l==x&&r==y)return sum[k];
    int mid=l+r>>;
    if(y<=mid)return query(k<<,l,mid,x,y);
    else if(x>mid)return query(k<<|,mid+,r,x,y);
    else return query(k<<,l,mid,x,mid)+query(k<<|,mid+,r,mid+,y);
}

int main()
{
    scanf("%d",&n);
    for(int i=;i<=n;i++)scanf("%lld",&a[i]);
    build(,,n);
    scanf("%d",&m);
    while(m--)
    {
        int op,l,r;scanf("%d%d%d",&op,&l,&r);
        if(l>r)swap(l,r);
        if(!op)modify(,,n,l,r);
        else cout<<query(,,n,l,r)<<'\n';
    }
    return ;
 }