题目内容

P4145

大意:维护一个序列,支持两种操作:

  • [l,r] 的每个数开方并向下取整
  • 查询 [l,r] 的区间和

所有数据小于 10^{12} 且都大于 0

解题思路

拿到这道题的时候发现:貌似区间开根没有那么简单,并没有 \sum\sqrt{a_i}=\sqrt{\sum a_i} 这种说法,所以只能很无奈的每次开根都暴力修改。

但是注意所有的数据都大于 0,且有一条很重要的性质是 \sqrt 1=1,所以如果某个区间的和等于这个区间的长度的话,就无需继续往下修改下去了。

注意有一半的点会出现 l>r 的情况,要进行交换!

#include <cstdio>
#include <cmath>
#include <cctype>
#define L (k<<1)
#define R (L|1)
typedef long long ll;

const int maxn=100005;
int n,m;
ll f[maxn<<2];

inline ll read()
{
    bool w=0;
    ll x=0;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            w=1;
        c=getchar();
    }
    while(isdigit(c))
        x=x*10+c-'0',c=getchar();
    return w?-x:x;
}

inline void swap(int &a,int &b)
{
    int t=a;
    a=b;
    b=t;
}

void build(int i,int j,int k)
{
    if(i==j)
    {
        f[k]=read();
        return;
    }
    int m=i+j>>1;
    build(i,m,L);
    build(m+1,j,R);
    f[k]=f[L]+f[R];
    return;
}

void modify(int i,int j,int x,int y,int k)//区间开根
{
    if(i==j && i>=x && j<=y)//如果已经到达叶子节点
    {
        f[k]=sqrt(f[k]);//直接开根
        return;
    }
    if(f[k]==j-i+1)//如果这段区间和等于区间长度
        return;//不管了那就
    int m=i+j>>1;
    if(x<=m)//否则就要继续往下递归修改
        modify(i,m,x,y,L);
    if(y>m)
        modify(m+1,j,x,y,R);
    f[k]=f[L]+f[R];
    return;
}

ll ask(int i,int j,int x,int y,int k)//常规查询操作
{
    if(x<=i && y>=j)
        return f[k];
    ll ans=0;
    int m=i+j>>1;
    if(x<=m)
        ans+=ask(i,m,x,y,L);
    if(y>m)
        ans+=ask(m+1,j,x,y,R);
    return ans;
}

int main()
{
    n=read();
    build(1,n,1);
    m=read();
    int k,l,r;
    while(m--)
    {
        k=read(),l=read(),r=read();
        if(l>r)
            swap(l,r);//交换操作
        if(k)
            printf("%lld\n",ask(1,n,l,r,1));
        else
            modify(1,n,l,r,1);
    }
    return 0;
}
最后修改日期:2020年3月10日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。