您的位置: 首页  >  IT文章  >  洛谷P4145 上帝造题的七分钟2 / 花神游历各国（重题：洛谷SP2713 GSS4

洛谷P4145 上帝造题的七分钟2 / 花神游历各国（重题：洛谷SP2713 GSS4

分类: IT文章 • 2022-05-26 19:52:52

题目背景

XLk觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。

题目描述

"第一分钟，X说，要有数列，于是便给定了一个正整数数列。

第二分钟，L说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。

第三分钟，k说，要能查询，于是便有了求一段数的和的操作。

第四分钟，彩虹喵说，要是noip难度，于是便有了数据范围。

第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。

第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。

第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。"

——《上帝造题的七分钟·第二部》

所以这个神圣的任务就交给你了。

输入输出格式

输入格式：

第一行一个整数nn，代表数列中数的个数。

第二行nn个正整数，表示初始状态下数列中的数。

第三行一个整数mm，表示有mm次操作。

接下来mm行每行三个整数k,l,r，

  • k=0表示给[l,r][l,r]中的每个数开平方(下取整)
  • k=1表示询问[l,r][l,r]中各个数的和。

数据中有可能l>rl>r，所以遇到这种情况请交换l和r。

输出格式：

对于询问操作，每行输出一个回答。

输入输出样例

输入样例#1：

10
1 2 3 4 5 6 7 8 9 10
5
0 1 10
1 1 10
1 1 5
0 5 8
1 4 8

输出样例#1：

19
7
6

说明

对于30%的数据，1≤n,m≤1000，数列中的数不超过3276732767。

对于100%的数据，1≤n,m≤100000，1≤l,r≤n，数列中的数大于00，且不超过10^12。

注意l有可能大于r，遇到这种情况请交换l,r。

题解

LOJ数列分块入门5
我们发现2^31的数最多开方5次，所以对一段区间暴力开方，当一个块中所有元素变为1时，就打个标记，下次遇到这个块就不用处理了。然后就是基本的求和操作。

#include<bits/stdc++.h>
using namespace std;
long long n,m,num,a[500010],sum[500010],block,posi[500010];
long long l[500010],r[500010];
bool v[500010];
void build()
{
    block=sqrt(n);num=n/block;
    if(n%block!=0) num++;
    for(int i=1;i<=num;i++) 
    l[i]=(i-1)*block+1,r[i]=i*block;
    r[num]=n;
    for(int i=1;i<=n;i++) 
    posi[i]=(i-1)/block+1,sum[posi[i]]+=a[i];
}
void update(long long ll,long long rr)
{
    if(!v[posi[ll]])
    {
        for(int i=ll;i<=min(r[posi[ll]],rr);i++)
        {
            sum[posi[ll]]-=a[i];
            a[i]=sqrt(a[i]);
            sum[posi[ll]]+=a[i];
        }
        v[posi[ll]]=1;
        for(int i=l[posi[ll]];i<=r[posi[ll]];i++)
            if(a[i]>1) {v[posi[ll]]=0;break;}
    }
    if(posi[ll]!=posi[rr])
    {
        if(!v[posi[rr]])
        {
            for(int i=l[posi[rr]];i<=rr;i++)
            {		
                sum[posi[rr]]-=a[i];
                a[i]=sqrt(a[i]);
                sum[posi[rr]]+=a[i];
            }
            v[posi[rr]]=1;
            for(int i=l[posi[rr]];i<=r[posi[rr]];i++)		
                if(a[i]>1) {v[posi[rr]]=0;break;}
        }
    }
    for(int i=posi[ll]+1;i<=posi[rr]-1;i++) 
    {
        if(v[i]) continue;
        v[i]=1;sum[i]=0;
        for(int j=l[i];j<=r[i];j++)
        {
            a[j]=sqrt(a[j]);sum[i]+=a[j];
            if(a[j]>1) v[i]=0;
        }
    }
}
void query(long long ll,long long rr)
{
    long long ans=0;
    for(int i=ll;i<=min(r[posi[ll]],rr);i++) ans+=a[i];
    if(posi[ll]!=posi[rr]) 
        for(int i=l[posi[rr]];i<=rr;i++) ans+=a[i];
    for(int i=posi[ll]+1;i<=posi[rr]-1;i++) ans+=sum[i];
    printf("%lld
",ans);
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build();
    scanf("%lld",&m);
    for(int i=1;i<=m;i++) 
    {
        int opt;long long x,y;
        scanf("%d%lld%lld",&opt,&x,&y);
        if(x>y) swap(x,y);
        if(!opt) update(x,y);
        else query(x,y);
    }	
    return 0;
}

相关推荐