题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=4027
题目
A lot of battleships of evil are arranged in a line before the battle. Our commander decides to use our secret weapon to eliminate the battleships. Each of the battleships can be marked a value of endurance. For every attack of our secret weapon, it could decrease the endurance of a consecutive part of battleships by make their endurance to the square root of it original value of endurance. During the series of attack of our secret weapon, the commander wants to evaluate the effect of the weapon, so he asks you for help.
You are asked to answer the queries that the sum of the endurance of a consecutive part of the battleship line.
Notice that the square root operation should be rounded down to integer.
Input
The input contains several test cases, terminated by EOF.
For each test case, the first line contains a single integer N, denoting there are N battleships of evil in a line. (1 <= N <= 100000)
The second line contains N integers Ei, indicating the endurance value of each battleship from the beginning of the line to the end. You can assume that the sum of all endurance value is less than 263.
The next line contains an integer M, denoting the number of actions and queries. (1 <= M <= 100000)
For the following M lines, each line contains three integers T, X and Y. The T=0 denoting the action of the secret weapon, which will decrease the endurance value of the battleships between the X-th and Y-th battleship, inclusive. The T=1 denoting the query of the commander which ask for the sum of the endurance value of the battleship between X-th and Y-th, inclusive.
Output
For each test case, print the case number at the first line. Then print one line for each query. And remember follow a blank line after each test case.
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
题意
区间修改[l,r]中的战舰的耐久度为原来的平方根。区间查询[l,r]的战舰耐久度之和。
分析
区间修改平方根？想一想发现很难实现。注意到2^64次方开根号也不过7次。所以暴力单点修改是可行的。
如果区间的值都为1时，无需修改，判断条件为sum等于区间长度。
否则暴力修改到叶子结点。
注意坑点，给定区间[x,y]，x不一定小于y。
AC代码
//514ms 6.6MB
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#define inf 0x3f3f3f3f
#define lson p<<1
#define rson p<<1|1
using namespace std;
typedef long long ll;
const int maxn=1e5+100;
struct node
{int l,r;//结点所维护的区间ll sum;//区间信息,耐力值之和
}T[maxn<<2];//线段树要开四倍空间
ll a[maxn];void up(int p)
{//区间信息的维护，将左子树所表示的区间与右子树所表示的区间合并T[p].sum=T[lson].sum+T[rson].sum;
}void build(int p,int l,int r)//p表示结点编号，l、r表示结点p所表示的区间
{T[p].l=l,T[p].r=r;//确定结点p所表示的区间[l,r]if(l==r) //确定叶子结点所表示的信息{T[p].sum=a[l];return ;}int mid=(l+r)>>1;build(lson,l,mid); //递归创建左子树build(rson,mid+1,r); //递归创建右子树up(p); //由下向上传递信息，即由两个小区间合并成一个大区间}
void update(int p,int x,int y) //需要修改的修改到叶子结点为止，没有延迟标记，伪区间修改、实单点修改
{if(T[p].sum==T[p].r-T[p].l+1)//区间内元素都是1，不需要修改{return ;}if(T[p].l==T[p].r) //找到叶子结点{ll ans=(ll)floor(sqrt(T[p].sum)); //修改叶子结点信息T[p].sum=ans;return ;}int mid=(T[p].l+T[p].r)>>1;if(y<=mid) update(lson,x,y);else if(x>mid) update(rson,x,y);else{update(lson,x,mid);update(rson,mid+1,y);}up(p);//注意不要忘了
}
ll query(int p,int x,int y)
{if(x==T[p].l && y==T[p].r) //区间[x,y]恰好与结点p所表示的区间重合return T[p].sum;//这个结点所表示的区间信息是所需要的int mid=(T[p].l+T[p].r)>>1;ll ans=0;if(y<=mid) //区间[x,y]一定在p的左子树上return query(lson,x,y);else if(x>mid) //区间[x,y]一定在p的右子树上return query(rson,x,y);else //没有与区间[x,y]恰好重合的结点{//将区间[x,y]分成两个小区间[x,mid]和[mid+1,y]//[x,mid]一定在p的左子树上//[mid+1,y]一定在p的右子树上ans+=query(lson,x,mid);ans+=query(rson,mid+1,y);return ans;}
}
int main()
{int n,m,kase=1;while(~scanf("%d",&n)){for(int i=1;i<=n;i++)scanf("%lld",&a[i]);build(1,1,n);scanf("%d",&m);printf("Case #%d:\n",kase++);while(m--){int op,x,y;scanf("%d%d%d",&op,&x,&y);if(x>y) swap(x,y);///注意这个，RTE多次if(op==0) update(1,x,y);else printf("%lld\n",query(1,x,y));}putchar(10);}return 0;
}