本文共 1933 字，大约阅读时间需要 6 分钟。
/*** 题意：给你n个数，对这些数进行操作，有m组操作* q == 0 [x,y]区间内的每个数开方* q == 1 输出[x,y]区间内的数的和* 题解：线段树（简单的插线问线）注：当数更新到1后不再往下更新，即node[x].sum == r - l + 1,* 不再往下更新了；* 坑爹的c++输入输出，以后再也不能因为方便用了(无尽超时)**/code：#include#include #include #include #include using namespace std;typedef long long LL;#define lson(x) (x<<1)#define rson(x) ((x<<1)|1)#define M 5000100struct Node{ int l,r; LL sum;}node[M*3];void pushup(int x){ node[x].sum = node[lson(x)].sum + node[rson(x)].sum;}void build(int l,int r,int x){ node[x].l = l; node[x].r = r; if(l == r){ scanf("%I64d",&node[x].sum); return ; } int mid = (l + r) >> 1; build(l,mid,lson(x)); build(mid+1,r,rson(x)); pushup(x);}void update(int l,int r,int x){ if(node[x].r == r && node[x].l == l&&node[x].sum == r - l +1) return ; if(node[x].l == node[x].r) { node[x].sum = sqrt(node[x].sum*1.0); return ; } int mid = (node[x].l + node[x].r) >> 1; if(r <= mid) update(l,r,lson(x)); else if(l > mid) update(l,r,rson(x)); else { update(l,mid,lson(x)); update(mid+1,r,rson(x)); } pushup(x);}LL Query(int l,int r,int x){ if(node[x].r == r && node[x].l == l) return node[x].sum; LL ans = 0; int mid = (node[x].l + node[x].r) >> 1; if(r <= mid) ans = Query(l,r,lson(x)); else if(l > mid) ans = Query(l,r,rson(x)); else { ans += Query(l,mid,lson(x)); ans += Query(mid+1,r,rson(x)); } return ans;}int main(){ int n,m,q,x,y,ca = 1; while(scanf("%d",&n)!=EOF){ build(1,n,1); scanf("%d",&m); printf("Case #%d:\n",ca++); for(int i = 0;i < m;i++){ scanf("%d%d%d",&q,&x,&y); if(x > y) swap(x,y); if(q == 0) update(x,y,1); else printf("%I64d\n",Query(x,y,1)); } printf("\n"); } return 0;}
转载地址：http://bcsgi.baihongyu.com/