https://loj.ac/problem/10128

题目描述

??给出一个序列\(A\)，要求维护两个操作：\(①\)询问\([l,r]\)中所有数的和；\(②\)将\([l,r]\)中的每个数\(a\)改为\(\sqrt{a}\)

思路

??个人表示这道题虽然看起来很难维护，不过暴力修改好像可以过。我们只要维护区间和即可，对于每个\([l,r]\)中的修改，我们暴力枚举到每个叶节点修改即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
struct Segment
{
    int l,r;
    ll sum,maxx;
}T[N<<2];
ll a[N];
void pushup(int k)
{
    T[k].sum=T[k<<1].sum+T[k<<1|1].sum;
    T[k].maxx=max(T[k<<1].maxx,T[k<<1|1].maxx);
}
void build(int k,int l,int r)
{
    T[k].l=l;T[k].r=r;
    if(l==r)
    {
        T[k].sum=T[k].maxx=a[l];
        return ;
    }
    int mid=l+r>>1;
    build(k<<1,l,mid);build(k<<1|1,mid+1,r);
    pushup(k);
}
void add(int k,int l,int r)
{
    if(T[k].l==T[k].r)
    {
        T[k].maxx=floor(sqrt(T[k].maxx));
        T[k].sum=floor(sqrt(T[k].sum));
        return ;
    }
    if(T[k].maxx<=1)return ;
    int mid=T[k].l+T[k].r>>1;
    if(r<=mid)add(k<<1,l,r);
    else if(l>mid)add(k<<1|1,l,r);
    else
    {
        add(k<<1,l,mid);
        add(k<<1|1,mid+1,r);
    }
    pushup(k);
}
ll query(int k,int l,int r)
{
    if(T[k].l==l&&T[k].r==r)
        return T[k].sum;
    int mid=T[k].l+T[k].r>>1;
    if(r<=mid)return query(k<<1,l,r);
    else if(l>mid)return query(k<<1|1,l,r);
    else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
}

int read()
{
    int res=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
    return res*w;
}
void write(ll x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
void writeln(ll x)
{
    write(x);
    putchar('\n');
}

int main() 
{
    int n=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    build(1,1,n);
    int m=read();
    while(m--)
    {
        int x=read(),l=read(),r=read();
        if(x==1)
            writeln(query(1,l,r));
        else
            add(1,l,r);
    }
    return 0;
}

花神游历各国

原文：https://www.cnblogs.com/fangbozhen/p/11767111.html