注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3038/3211]上帝造题的七分钟2  

2014-12-26 13:35:40|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3038: 上帝造题的七分钟2

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 647  Solved: 289
[Submit][Status]

Description

XLk觉得《上帝造题的七分钟》不太过瘾,于是有了第二部。
"第一分钟,X说,要有数列,于是便给定了一个正整数数列。
第二分钟,L说,要能修改,于是便有了对一段数中每个数都开平方(下取整)的操作。
第三分钟,k说,要能查询,于是便有了求一段数的和的操作。
第四分钟,彩虹喵说,要是noip难度,于是便有了数据范围。
第五分钟,诗人说,要有韵律,于是便有了时间限制和内存限制。
第六分钟,和雪说,要省点事,于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。
第七分钟,这道题终于造完了,然而,造题的神牛们再也不想写这道题的程序了。"
——《上帝造题的七分钟·第二部》
所以这个神圣的任务就交给你了。

Input

第一行一个整数n,代表数列中数的个数。
第二行n个正整数,表示初始状态下数列中的数。
第三行一个整数m,表示有m次操作。
接下来m行每行三个整数k,l,r,k=0表示给[l,r]中的每个数开平方(下取整),k=1表示询问[l,r]中各个数的和。

Output

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

Sample Input

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

Sample Output

19
7
6

HINT

1:对于100%的数据,1<=n<=100000,1<=l<=r<=n,数列中的数大于0,且不超过1e12。

2:数据不保证L<=R 若L>R,请自行交换L,R,谢谢!

Solution

如果一个数是0,开完根还是0

如果一个数是1,开完根还是1

1e12开不到10次根就变成1了

于是维护两个标记sum[]和flag[]

sum[o]=sum[o<<1]+sum[o<<1|1]

flag[o]=flag[o<<1]&flag[o<<1|1]

flag[o]=(sum[o]==0||sum[o]==1)

修改的时候,flag[o]==0就暴力修改,flag[o]==1就不要修改

Code

/**************************************************************
    Problem: 3038
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:924 ms
    Memory:3192 kb
****************************************************************/
 
#include<cstdio>
#include<cmath>
typedef long long ll;
int i32;char ch;int F32(){
    while(ch=getchar(),ch<'0'||ch>'9');i32=ch-'0';
    while(ch=getchar(),ch>='0'&&ch<='9')i32=i32*10+ch-'0';return i32;
}
ll i64;ll F64(){
    while(ch=getchar(),ch<'0'||ch>'9');i64=ch-'0';
    while(ch=getchar(),ch>='0'&&ch<='9')i64=i64*10+ch-'0';return i64;
}
int n,x,y,k,m,tt;ll sum[270000],ans;bool flag[270000];
void bt(int o,int l,int r){
    if(l==r)sum[o]=F64();
    else{
        int mid=l+r>>1;
        bt(o<<1,l,mid);
        bt(o<<1|1,mid+1,r);
        sum[o]=sum[o<<1]+sum[o<<1|1];
    }
}
void update(int o,int l,int r){
    if(flag[o]||sum[o]==0||sum[o]==1){
        flag[o]=1;
        return;
    }
    if(l==r){
        sum[o]=sqrt(sum[o]);
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)update(o<<1,l,mid);
    if(mid<y)update(o<<1|1,mid+1,r);
    sum[o]=sum[o<<1]+sum[o<<1|1];
    flag[o]=flag[o<<1]&flag[o<<1|1];
}
void query(int o,int l,int r){
    if(x<=l&&r<=y)ans+=sum[o];
    else{
        int mid=l+r>>1;
        if(x<=mid)query(o<<1,l,mid);
        if(mid<y)query(o<<1|1,mid+1,r);
    }
}
int main(){
    for(n=F32(),bt(1,1,n),m=F32();m--;){
        k=F32(),x=F32(),y=F32();
        if(x>y)tt=x,x=y,y=tt;
        if(k==0)update(1,1,n);
        else ans=0,query(1,1,n),printf("%lld\n",ans);
    }
}
  评论这张
 
阅读(13)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018