HDU4027

本以为对线段树还是比较熟悉的，但是这题改变了我的想法。

顺着wk的题解做了这题。

拿到手就知道线段树，写完T，这时候我想起来蓝桥杯的线段树也是这样的吧，只不过那题对区间的操作是log，真可笑，当时还以为是cin写跪了，就这题看来，估计也那题没过几组数据，二等奖也在情理之中。

每次都更新到最底下会超时，每个数sqrt几次之后就会成为1，这时再开方是没有意义的，可以剪枝，如果区间长度等于区间和，说明区间没有必要更新，可以直接return。

此外还有好几个WA点

#include
#include
#include
#include
#include
using namespace std;
#define MAXN 100005
struct node
{int l,r,mid;__int64 sum,len;//32位会WA
}tree[MAXN<<2];
void build(int l,int r,int now)
{tree[now].l=l;tree[now].r=r;tree[now].sum=0;tree[now].len=r+1-l;if(l==r){scanf("%I64d",&tree[now].sum);return ;}tree[now].mid=(l+r)>>1;build(l,tree[now].mid,now<<1);build(tree[now].mid+1,r,now<<1|1);tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;//弱爆了，刚开始这里都忘记写了
}
void update(int l,int r,int now)
{if(tree[now].l==l && tree[now].r==r){if(tree[now].len==tree[now].sum)return ;}if(tree[now].l==tree[now].r){tree[now].sum=(__int64)sqrt(1.0*tree[now].sum);//不知道为什么，这里直接开方不行，可能是64位的原因吧return;}if(l>tree[now].mid)update(l,r,now<<1|1);else{if(r<=tree[now].mid)update(l,r,now<<1);else{update(l,tree[now].mid,now<<1);update(tree[now].mid+1,r,now<<1|1);}}tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;
}
__int64 query(int l,int r,int now)//64君哦
{if(l==tree[now].l && r==tree[now].r)return tree[now].sum;if(l>tree[now].mid)return query(l,r,now<<1|1);else{if(r<=tree[now].mid)return query(l,r,now<<1);elsereturn query(l,tree[now].mid,now<<1)+query(tree[now].mid+1,r,now<<1|1);}
}
int main()
{int n,m,te=0;while(~scanf("%d",&n)){te++;build(1,n,1);scanf("%d",&m);printf("Case #%d:\n",te);while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);int l=min(b,c);//区间左右大小不一定int r=max(b,c);if(a==0)update(l,r,1);else{printf("%I64d\n",query(l,r,1));}}cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！