萌萌哒的传送门
因为一个long long 范围内的数开方不会超过10次,所以题目就转化为线段树的单点更新问题.
#include#include #include #include #include #include #include #include #include #define ls u << 1 #define rs u << 1 | 1 #define lson l, mid, u << 1 #define rson mid + 1, r, u << 1 | 1 #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int M = 1e5 + 100; const int N = 1e7 + 100; ll sum[M << 2]; void pushup(int u){ sum[u] = sum[ls] + sum[rs]; } void build(int l,int r,int u){ if(l == r){ scanf("%I64d",sum + u); } else { int mid = (l + r) >> 1; build(lson); build(rson); pushup(u); } } void update(int L,int R,int l,int r,int u){ if(sum[u] == (r - l + 1)){ return; } if(l == r){ sum[u] = floor(sqrt((double)sum[u])); } else { int mid = (l + r) >> 1; if(L <= mid) update(L,R,lson); if(R > mid) update(L,R,rson); pushup(u); } } ll query(int L,int R,int l,int r,int u){ if(L <= l && R >= r){ return sum[u]; } else { int mid = (l + r) >> 1; ll res = 0; if(L <= mid) res += query(L,R,lson); if(R > mid) res += query(L,R,rson); return res; } } int main(){ //freopen("in","r",stdin); int n,m,cnt = 0; while(~scanf("%d",&n)){ build(1,n,1); scanf("%d",&m); printf("Case #%d:\n",++cnt); while(m--){ int t,l,r; scanf("%d %d %d",&t,&l,&r); if(l > r) swap(l,r); if(!t) update(l,r,1,n,1); else { printf("%I64d\n",query(l,r,1,n,1)); } } puts(""); } return 0; }