SPOJ 2713. GSS4 – C++ solution

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;
}