题意：给一个数组序列， 数组长度为100000
两种操作： 一种操作是将某一个固定区间所有数开方（向下取整）
另一种操作是询问某个区间的所有数字之和。
由于数不超过2^63,因此开个七八次就变成1，由于只有开方，没有修改操作，直接暴力开方，对于sum[i]==r-l+1的区间不作处理（再开也没意义了） #include <cstdio> #include <cmath> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <queue> #include <map> #include <set> #include <vector> using namespace std; typedef long long ll; const int N = 100000+50 ; ll sum[4*N], add[4*N] ; void build(int l, int r, int i) { sum[i] = 0; if(l == r) { scanf("%lld", &sum[i]); return ; } int mid = (l+r)>>1; build(l,mid,i<<1); build(mid+1,r,i<<1|1); sum[i] = sum[i << 1] + sum[i << 1 | 1]; } void update_sqrt(int i, int l, int r, int ql, int qr ) //更新区间为qlqr,当前区间为l,r,代表当前区间和的节点为i，更新值为val, { if(l > qr || ql > r) return ; if (l>=ql&&r<=qr&&sum[i]<=r-l+1) return ; if(l==r) { sum[i]=sqrt(1.0*sum[i]); return ; } int mid = (l + r) >> 1; update_sqrt(i << 1, l, mid, ql, qr ); update_sqrt(i << 1 | 1, mid + 1, r, ql, qr); sum[i] = sum[i << 1] + sum[i << 1 | 1]; } ll query(int i, int l, int r, int ql, int qr) //查询区间为qlqr,当前区间为l,r,代表当前区间和的节点为i { if(l > qr || ql > r) return 0; if(l >= ql && r <= qr) return sum[i]; int mid =( l + r) >> 1; return query(i << 1, l, mid, ql, qr) + query(i << 1 | 1, mid + 1, r, ql, qr); } int main() { int n,m; int cnt=1; while(scanf("%d", &n)!=EOF) { printf("Case #%d:\n",cnt++); build(1,n,1); int m; cin>>m; int op; int a,b,c; for( int i = 1; i <= m; i++) { scanf("%d",&op); if (op==1) { scanf("%d%d",&a,&b); if (a>b)swap(a,b); printf("%lld\n",query(1, 1,n,a,b) ); } else if (op==0) { scanf("%d%d",&a,&b); if (a>b)swap(a,b); update_sqrt(1,1,n,a,b); } } printf("\n"); } return 0; }