http://acm.hdu.edu.cn/showproblem.php?pid=4027

题目

给出一串数字，表示一排战舰的耐久度= =

有两种操作

使用武器，把从x到y的每一个战舰的耐久度开平方，向下取整查询从x到y的战舰的耐久度的和，保证和不会超过$2^{63}$

100000个战舰，100000操作，2s时限

题解

开根号没有什么好的区间性质，看不到什么好的线段树的特点……

不过开根号开到几次再开就不会变了，可以用这个性质设定一个区间开关之类的东西，到不会变的区间就不再修改

这样最多执行6*100000次开方，可以卡进时限= =

 

另外线段树在递归的时候是数学归纳，递归的区间一定是与操作的区间相交的，于是要保证下一层也相交，只用考虑递归的区间的中点与查询区间中点的关系

因为相交，所以不存在红框的情况，所以判断左子区间是否与黄框相交就可以了，还要注意右区间是[m+1,r]

 

由于是从x到y，所以不能把l，r直接和x，y对应，还需要考虑大小

 

AC代码

#include<bits/stdc++.h> using namespace std; #define REP(r,x,y) for(int r=(x); r<y; r++) #define REPE(r,x,y) for(int r=(x); r<=y; r++) #define PERE(r,x,y) for(int r=(x); r>=y; r++) typedef long long LL; #define MAXN 100007 struct node { int l,r; LL v; int d; }t[MAXN<<2]; int n,m; LL e[MAXN]; void build(int p, int l, int r) { node &now = t[p]; now.l=l, now.r=r; now.d=1; if(l==r) { now.v=e[l]; return; } int m=l+r>>1; build(p*2,l,m); build(p*2+1,m+1,r); now.v=t[p*2].v+t[p*2+1].v; } void ope(int p, int l, int r) { node &now = t[p]; if(now.l==now.r) { now.v=(int)floor(sqrt(now.v)); if(now.v<=1) now.d=0; return; } int m=now.l+now.r>>1; if(m>=l && t[p*2].d) ope(p*2, l, r); if(m+1<=r && t[p*2+1].d) ope(p*2+1, l, r); now.d= t[p*2].d || t[p*2+1].d; now.v=t[p*2].v+t[p*2+1].v; } LL opq(int p, int l, int r) { node &now = t[p]; if(now.l>=l && now.r<=r) { return now.v; } int m=(now.l+now.r)>>1; LL ans=0; if(m>=l) ans+=opq(p*2, l, r); if(m+1<=r) ans+=opq(p*2+1,l,r); return ans; } int main() { #ifdef sahdsg freopen("in.txt", "r", stdin); #endif // sahdsg int kase=0; while(~scanf("%d", &n)) { printf("Case #%d:\n", ++kase); REPE(i,1,n) { scanf("%lld", &e[i]); } build(1,1,n); scanf("%d", &m); REP(i,0,m) { int T,x,y; scanf("%d%d%d", &T, &x, &y); if(x>y) swap(x,y); if(T==0) ope(1,x,y); else { printf("%lld\n", opq(1,x,y)); } } putchar('\n'); } return 0; }

 

转载于:https://www.cnblogs.com/sahdsg/p/10985179.html

相关资源：JAVA上百实例源码以及开源项目