本文主要是介绍NEFU 1317 神奇的开方运算（线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
神奇的开方运算
Problem:1317
Time Limit:1000ms
Memory Limit:65535K
Description
给出一个数组，现有两种操作 1.将某一个区间所有数开方（向下取整） 2.询问某一个区间的区间和
Input
多组样例，对于每组样例 第一行输入一个数 N(1<=N<=1e5) 表示数组的长度 第二行输入 N 个数 A1,A2....An （1<=Ai<=2^63）表示数组每一位的值 第三行输入一个数 M(1<=M<=1e5)表示操作的个数 接下来 M 行，每行为 0 x y 或 1 x y 0 x y 代表对区间 [x，y] 所有数开方 1 x y 代表求区间 [x，y] 所有数的和
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
Case #1: 19 7 6
Hint
Source
DT2131
题意：
中文题。
思路：
当时想这道题没有往开方次数上想，想了单点修改，区间查询但是T了。还是姿势不够，秀逗了QAQ。
一个2^64的数，也只要7次开方就能变成1了。
所以最后数组的值变成1就不用更新了。也就是在更新的时候，如果碰到了更新区间的值都为1了。那么就不用再继续往下更新了，直接返回就行了。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=100005;
long long tr[4*maxn];
int add[4*maxn];
void pushup(int i)
{tr[i]=tr[i*2]+tr[i*2+1];
}
void build(int i,int l,int r)
{add[i]=0;if(l==r){scanf("%lld",&tr[i]);return;}int mid=(l+r)/2;build(2*i,l,mid);build(2*i+1,mid+1,r);pushup(i);
}
void update(int i,int l,int r,int x,int y)
{if(tr[i]==(r-l+1)) return;if(l==r){tr[i]=(long long)sqrt(tr[i]);return;}int mid=(l+r)/2;if(x<=mid) update(i*2,l,mid,x,y);if(y>mid) update(2*i+1,mid+1,r,x,y);pushup(i);return;
}
long long query(int i,int l,int r,int x,int y)
{long long sum=0;if(x<=l&&r<=y){return tr[i];}int mid=(l+r)/2;if(x<=mid) sum+=query(2*i,l,mid,x,y);if(y>mid) sum+=query(2*i+1,mid+1,r,x,y);return sum;
}
int main()
{int n,m,o,x,y,cas=1;while(~scanf("%d",&n)){build(1,1,n);scanf("%d",&m);printf("Case #%d:\n",cas++);for(int i=1;i<=m;i++){scanf("%d%d%d",&o,&x,&y);if(o==0){update(1,1,n,x,y);}else{printf("%lld\n",query(1,1,n,x,y));}}}return 0;
}
这篇关于NEFU 1317 神奇的开方运算（线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
