Obviously one has to use a segment tree to solve the problem, but the problem is that the update operations are over a given interval [a;b]. Let us consider that we have some number in the array K = 1<<64 = 18446744073709551616. This is quite big in fact and there might not be any numbers so big.

sqrt(1<<64) = 1<<32

sqrt(1<<32) = 1<<16

sqrt(1<<16) = 1<<8

sqrt(1<<8) = 1<<4

sqrt(1<<4) = 1<<2

sqrt(1<<2) = 1<<1

sqrt(1<<1) = 1<<0 = 1

sqrt(1<<1) = 1 Just after 7 operations we reached the bottom. So what can happen in the worst case if we do update operations over each element. We will just do 7 * n*log(n) updates and then we won’t to do any at all. => we can approach the updates naively, but if we have only 1s in a given segment, then we shouldn’t do any updates since this won’t change anything because sqrt(1) = 1.

This is the solution. Of course the tests are pretty bad and the output is defined pretty bad as well. For example, I missed : at the end of Case %d.

#include <iostream> #include <cmath> #include <cstdio> #include <fstream> #include <cstdlib> #include <ctime> using namespace std; typedef long long ull; struct Node { ull sum; Node() {}; Node(ull num) { sum = num; } Node(const Node & left, const Node & right) { sum = left.sum + right.sum; } }; ull arr[100001]; Node tree[900108]; void build(int idx, int sfrom, int sto) { if (sfrom == sto) { tree[idx] = Node(arr[sfrom]); return; } int mid = (sfrom+sto)>>1; int left = idx<<1; int right = left+1; build(left, sfrom, mid); build(right, mid+1, sto); tree[idx] = Node(tree[left], tree[right]); } void update(int idx, int sfrom, int sto, int qfrom, int qto) { ull ss = (ull)sto - (ull)sfrom + 1LL; if (tree[idx].sum == ss) return; if (sfrom == sto) { tree[idx].sum = sqrt(tree[idx].sum); return; } int mid = (sfrom+sto)>>1; int left = idx<<1; int right = left+1; if (qto <= mid) { update(left, sfrom, mid, qfrom, qto); } else if (qfrom > mid) { update(right, mid+1, sto, qfrom, qto); } else { update(left, sfrom, mid, qfrom, mid); update(right, mid+1, sto, mid+1, qto); } tree[idx] = Node(tree[left], tree[right]); } ull query(int idx, int sfrom, int sto, int qfrom, int qto) { if (sfrom == qfrom && sto == qto) { return tree[idx].sum; } int mid = (sfrom+sto)>>1; int left = idx<<1; int right = left+1; if (qto <= mid) { return query(left, sfrom, mid, qfrom, qto); } else if (qfrom > mid) { return query(right, mid+1, sto, qfrom, qto); } else { return query(left, sfrom, mid, qfrom, mid) + query(right, mid+1, sto, mid+1, qto); } } void gen() { srand(time(NULL)); ofstream out("test.in"); int n = 100000; out << n << endl; for (int i = 1; i <= n; ++i) { out << i*2 << endl; } out << n << endl; for (int i = 1; i<= n; ++i) { int op = rand()%2; int from = rand()%n + 1; int to = rand()%n + 1; out << op << " " << from << " " << to << endl; } out.close(); } int main() { //gen(); int t=1; int n,q; while ((scanf("%d", &n)) != EOF) { for (int i = 1; i<=n; ++i) scanf("%lld", &arr[i]); build(1,1,n); scanf("%d",&q); int a,b,c; printf("Case #%d:n", t); while (q--) { scanf("%d%d%d",&a,&b,&c); if (b > c) swap(b,c); if (a == 0) { update(1,1,n,b,c); } else { printf("%lldn",query(1,1,n,b,c)); } } ++t; printf("n"); } return 0; }