Spoj QTREE – CPP solution

Problem: http://www.spoj.com/problems/QTREE/

The keys to solving this problem are:
– some basic graph theory (traversing graphs) (easy)
– LCA on a tree (medium)
– Heavy-light decomposition (medium-hard)
– Segment tree (medium)

In general, I had some bugs in my code and it took some time to debug. You can see some asserts and generating tests to see what’s going wrong with my solution. :)

Note that this is the O(nlogn + Qlogn * logn) where Q is the number of queries.
I could not get the O(nlogn + Q * logn) to work.

If you are willing to try, note that we are using the segment tree to check the maximum over a given chain. From one node to a given parent node somewhere in the tree, there are at most O(logn) chains. The thing is that possibly for expect the first and last chain, we are querying over the whole interval which means that for each chain we can just keep a maximum value so that we are able to retrieve it in O(1) and update it O(1) time. This will lead to a
O(logn) per query.

#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <iostream>
#include <cassert>
using namespace std;

struct Edge {
    int u;
    int v;
    int cost;
    Edge() {};
    Edge(int _u, int _v, int _cost) : u(_u), v(_v), cost(_cost) {};
    int getNb(int V) {
        return V == v ? u : v;
    }
};
int n;
vector<int> nb[10001];
int childSz[10001];
int parent[10001][32];
int depth[10001];
Edge edges[10001];
int LOG;
int numChains;
char isSpecial[10001];
int generatedArrayIDX;
int generatedArray[10001];
int chainHead[10001];
int chainSize[10001];
int vertexChain[10001];
int vertexPos[10001];
int tree[80001];

int slow(int u, int c, int p, int r) {
    if (u == r) {
        return c;
    }
    int res = 0;
    for (int i = 0; i < nb[u].size();i++) {
        int v = edges[nb[u][i]].getNb(u);
        if (p == v) continue;
        int q = slow(v, edges[nb[u][i]].cost, u, r);
        if (q) q = max(q, edges[nb[u][i]].cost);
        res = max(res, q);
    }
    return res;
}

void reset() {
    numChains = 0;
    generatedArrayIDX = 0;
    for (int i = 0; i<=n; i++) {
        nb[i].clear();
        childSz[0];
        parent[i][0] = 0;
        depth[i] = 0;
        isSpecial[i] = 0;
        chainHead[i] = 0;
        generatedArray[i] = 0;
        chainSize[i] = 0;
        vertexChain[i] = 0;
        vertexPos[i] = 0;
    }
}

void dfs(int u, int p) {
    childSz[u] = 1;
    parent[u][0] = p;
    depth[u] = depth[p]+1;
    for (int i = 0; i < nb[u].size(); i++) {
        int v = edges[nb[u][i]].getNb(u);
        if (v == p) continue;
        dfs(v,u);
        childSz[u] += childSz[v];
    }
}

void hld(int u,int e) {
    if (chainHead[numChains] == 0) {
        // create new chain
        chainHead[numChains] = u;
    }
    vertexChain[u] = numChains;
    vertexPos[u] = generatedArrayIDX;
    chainSize[numChains]+=1;
    if (u != 0) {
        generatedArray[generatedArrayIDX++] = e;
    }

    int special = 0;
    int edge;
    for (int i = 0; i < nb[u].size(); i++) {
        int v =edges[nb[u][i]].getNb(u);
        if (v == parent[u][0]) continue;
        if (childSz[special] < childSz[v]) {
            special = v;
            edge = edges[nb[u][i]].cost;
        }
    }
    if (special == 0) return;
    isSpecial[special] = 1;
    hld(special, edge);
    for (int i = 0; i < nb[u].size(); i++) {
        int v = edges[nb[u][i]].getNb(u);
        if (v == parent[u][0] || v == special) continue;
        ++numChains;
        hld(v,edges[nb[u][i]].cost);
    }
}


void build(int idx, int sfrom, int sto) {
    if (sfrom == sto) {
        tree[idx] = generatedArray[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] = max(tree[left], tree[right]);
}

void init() {
    dfs(1,0);
    LOG = 0;
    while ((1<<LOG) <= n) ++LOG;
    for (int i = 1; i<=LOG; i++) {
        for (int u = 1; u<=n; u++) {
            parent[u][i] = parent[parent[u][i-1]][i-1];
        }
    }
    hld(1, 0);
    build(1, 0, generatedArrayIDX-1);
}

int lca(int u, int v) {
    int L = LOG;
    if (depth[u] < depth[v]) swap(u,v);
    while (depth[u] != depth[v]) {
        if (depth[u] - (1<<L) >= depth[v]) u = parent[u][L];
        --L;
        if (L < 0) L=0;
    }
    L = LOG;
    while (u != v) {
        if (parent[u][L] != parent[v][L] || L == 0) {
            u = parent[u][L];
            v = parent[v][L];
        }
        --L;
        if (L < 0) L = 0;
    }
    return u;
}

int query(int idx, int sfrom, int sto, int qfrom, int qto) {
    if (sfrom == qfrom && sto == qto) {
        return tree[idx];
    }
    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 max(query(left, sfrom, mid, qfrom, mid),
            query(right, mid+1, sto, mid+1, qto));
    }
}

void update(int idx, int sfrom, int sto, int pos) {
    if (sfrom == sto) {
        tree[idx] = generatedArray[pos];
        return;
    }
    int mid = (sfrom+sto)>>1;
    int left = idx<<1;
    int right = left+1;
    if (pos <= mid) {
        update(left, sfrom, mid, pos);
    } else {
        update(right, mid+1, sto, pos);
    }
    tree[idx] = max(tree[left], tree[right]);
}

int subquery(int TOP, int BOTTOM) {
    int ans = -1;
    if (TOP == BOTTOM) return 0;
    while (true) {
        if (vertexChain[TOP] == vertexChain[BOTTOM]) {
            int topPos = vertexPos[TOP];
            int botPos = vertexPos[BOTTOM];
            if (topPos == botPos) return ans;
            topPos += 1;
            return max(
                ans,
                query(1, 0, generatedArrayIDX-1, topPos, botPos)
            );
        } else {
            int botPos = vertexPos[BOTTOM];
            int topPos = vertexPos[chainHead[vertexChain[BOTTOM]]];

            ans = max(ans, query(1, 0, generatedArrayIDX-1, topPos, botPos));

            BOTTOM = parent[chainHead[vertexChain[BOTTOM]]][0];
        }
    }
}

int query(int u, int v) {
    int w = lca(u,v);
    return max(subquery(w, u), subquery(w,v));
}

int update(int u, int c) {
    Edge & e = edges[u-1];
    e.cost = c;
    int CHILD;
    if (e.u == parent[e.v][0]) {
        CHILD = e.v;
    } else {
        CHILD = e.u;
    }
    generatedArray[vertexPos[CHILD]] = c;
    update(1,0,generatedArrayIDX-1, vertexPos[CHILD]);
}

void genRandom() {
    int t = 1;
    ofstream out("qtree.in");
    out << t << endl;
    srand(time(NULL));
    int FROM = 4000, TO = 4001;
    for (int i = 0; i <t; i++) {
        int v = rand()%(TO-FROM) + FROM;
        out << v << endl;
        vector<int> used;
        used.reserve(v);
        used.push_back(1);
        for (int j = 2; j<=v; j++) {
            int cost = rand()%100 + 5;
            int u = used[rand()%used.size()];
            used.push_back(j);
            out << u << " " << j << " " << cost << endl;
        }
        int op = 2000;
        for (int j = 0; j < op; j++) {
            int M = rand()%2;
            if (M == 0) {
                // query
                int A = rand()%v + 1;
                int B = rand()%v + 1;
                out << "QUERY " << A << " " << B << endl;
            } else {
                // update
                int A = rand()%(v-1) + 1;
                int B = rand()%10000 + 5;
                out << "CHANGE " << A << " " << B << endl;
            }
        }
        out << "DONE" << endl;
    }
    out.close();
}

//#define DEBUG2

int main() {
    #ifdef DEBUG
        genRandom();
        return 0;
    #endif
    int t;
    scanf("%d",&t);
    while (t--) {
        scanf("%d",&n);
        for (int i = 1; i < n; i++) {
            int a,b;
            long c;
            scanf("%d%d%ld", &a,&b,&c);
            edges[i-1] = Edge(a,b,c);
            nb[a].push_back(i-1);
            nb[b].push_back(i-1);
        }
        init();
        int a,b,c;
        char buf[7];
        while (1) {
            scanf("%s",buf);
            if (buf[0] == 'D') break;
            if (buf[0] == 'Q') {
                scanf("%d%d",&a,&b);
                printf("%dn", query(a,b));
                #ifdef DEBUG2
                    assert(query(a,b) == slow(a,0,0,b));
                #endif
            } else if (buf[0] == 'C') {
                scanf("%d%d",&a,&c);
                update(a,c);
            }
        }
        reset();
    }
    return 0;
}

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

Spoj 7299. Multiples of 3 – Cpp solution

The idea is to build a segment tree and use lazy updates.
What is a lazy update? Say, that you have to update an interval [A;B]. It will be time consuming to update it if you are not going to query it later. So, when you find such an interval, don’t go further down the tree, but rather update what should be the value for this interval and memorize that the two children nodes have to be updated later. If you later go down that branch for either an update or for a query, just update (fix) the value for that node.
That’s all. For the segment tree, just keep all values of zeros, ones and twos. You do not need to keep what is the actual value, but rather the value mod 3.

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

struct Node {
    int zeros, ones, twos;
    Node() {
        zeros = ones = twos = 0;
    }
    Node(const Node & left, const Node & right) {
        zeros = left.zeros + right.zeros;
        ones = left.ones + right.ones;
        twos = left.twos + right.twos;
    }
};

Node tree[800016];
int lazy[800016];

void build(int idx, int sfrom, int sto) {
    if (sfrom == sto) {
        tree[idx].zeros = 1;
        return;
    }
    int left = idx<<1;
    int right = left+1;
    int mid = (sfrom + sto)>>1;
    build(left, sfrom, mid);
    build(right, mid+1, sto);
    tree[idx] = Node(tree[left], tree[right]);
}

void fix(int idx) {
    lazy[idx] %= 3;
    if (lazy[idx] == 1) {
        swap(tree[idx].zeros, tree[idx].twos);
        swap(tree[idx].ones, tree[idx].twos);
    } else if (lazy[idx] == 2) {
        swap(tree[idx].zeros, tree[idx].ones);
        swap(tree[idx].ones, tree[idx].twos);
    }
    lazy[idx<<1] += lazy[idx];
    lazy[(idx<<1)+1] += lazy[idx];
    lazy[idx] = 0;
}

void update(int idx, int sfrom, int sto, int qfrom, int qto) {
    if (sfrom == qfrom && sto == qto) {
        lazy[idx]+=1;
        fix(idx);
        return;
    }
    int left = idx<<1;
    int right = left+1;
    int mid = (sfrom+sto)>>1;
    if (lazy[idx]) fix(idx);
    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);
    }
    fix(left);
    fix(right);
    tree[idx] = Node(tree[left], tree[right]);
}

int query(int idx, int sfrom, int sto, int qfrom, int qto) {
    if (sfrom == qfrom && sto == qto) {
        fix(idx);
        return tree[idx].zeros;
    }
    int left = idx<<1;
    int right = left+1;
    int mid = (sfrom+sto)>>1;
    if (lazy[idx]) fix(idx);
    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);
    }
}

int main() {
    cin.sync_with_stdio(0);
    int n,q;
    scanf("%d%d", &n, &q);
    build(1,1,n);
    int a,b,c;
    while (q--) {
        scanf("%d%d%d",&a,&b,&c);
        b+=1, c+=1;
        if (a == 0) {
            update(1,1,n,b,c);
        } else {
            printf("%dn", query(1,1,n,b,c));
        }
        //cout << "! " << lazy[1] << endl;
    }
    return 0;
}

6294. Yodaness Level C++ solution

The idea is to find the number of inverses which means
that given an array A. We have an inverse if
i < j, but A[i] > A[j]
In our case, we want to sort the words and we are interested in the minimum number of swaps using say insertion sort to accomplish this task.
We can use a segment tree.
We will two kinds of queries:
query(from, to) -> number of elements smaller than to
update(pos) -> number of elements smaller than pos incremented by 1

go over each element in the array and count the number of inverse of it. Say, that we are index I and we have added B elements which are smaller than A[I]. Then, we have I-B elements which are bigger => number of inverses is I-B. Then we also have to update the tree to node that we have added element A[I].
Code:

#include <iostream>
#include <string>
#include <cstring>
#include <unordered_map>
using namespace std;

typedef long long ll;

int n;
ll tree[200001];
int arr[30001];
unordered_map<string,size_t> mp;

ll query(int idx, int sfrom, int sto, int qfrom, int qto) {
    if (sfrom == qfrom && sto == qto) {
        return tree[idx];
    }
    int left = idx<<1;
    int right = left+1;
    int mid = (sfrom+sto)>>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 update(int idx, int sfrom, int sto, int pos) {
    if (sfrom == sto) {
        tree[idx]+=1;
        return;
    }
    int left = idx<<1;
    int right = left+1;
    int mid = (sfrom+sto)>>1;
    if ( pos <= mid) {
        update(left, sfrom, mid, pos);
    } else {
        update(right, mid+1, sto, pos);
    }
    tree[idx] = tree[left] + tree[right];
}

int main() {
    cin.sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        string s;
        for (int i = 1;i<=n;++i) {
            cin >> s;
            mp.insert(make_pair(s, i));
        }
        for (int i = 1; i<=n;++i) {
            cin >> s;
            pair<string, size_t> found = *mp.find(s);
            arr[found.second] = i;
        }
        ll ans = 0;
        for (int i = 1; i<= n; ++i) {
            ans += (i - query(1,1,n,1,arr[i])-1);
            update(1,1,n,arr[i]);
        }
        cout << ans << endl;
        memset(tree,0,sizeof(tree));
        mp.clear();
    }
    return 0;
}

Spoj GSS3 – CPP solution

The problem is the same as GSS1. The only difference is the modify (update) operation.

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

struct node {
    long sum;
    long best;
    long left;
    long right;
};

int n;
long q[50003];
node tree[200003];

node makeNode(long sum, long best, long left, long right) {
    node tmp;
    tmp.sum = sum;
    tmp.best = best;
    tmp.left = left;
    tmp.right = right;
    return tmp;
}

node combine (node l, node r) {
    long left = l.left;
    if (l.sum + r.left>left) left =l.sum + r.left;
    long right = r.right;
    if (r.sum + l.right > right) right = r.sum + l.right;
    long best = max(l.right + r.left, max(l.best, r.best));
    return makeNode(l.sum+r.sum,best, left, right);
}

node build(int from, int to, int index) {
    if (from == to) {
        tree[index] = makeNode(q[from], q[from], q[from], q[from]);
        return tree[index];
    }
    int mid = (from+to)/2;
    node l = build(from,mid, (index<<1));
    node r = build(mid+1,to, (index<<1)+1);

    tree[index] = combine(l,r);
    return tree[index];
}

node ans(int index, int from, int to, int a, int b) {
    if (from == a && to == b) {
        return tree[index];
    }
    int mid = (from+to)/2;
    if (b <= mid) {
        return ans((index<<1), from, mid, a, b);
    }
    if (a > mid) {
        return ans((index<<1) + 1, mid+1,to,a,b);
    }
    node l = ans((index<<1), from, mid, a, mid);
    node r = ans((index<<1) + 1, mid+1,to,mid+1,b);
    return combine(l,r);
}

void modify(int from, int to, int index, int indexMod) {
    if (from == to && from == indexMod) {
        tree[index] = makeNode(q[from], q[from], q[from], q[from]);
        return;
    }
    int mid = (from+to)/2;
    if (indexMod <= mid) {
        modify(from, mid, (index<<1), indexMod);
    } else {
        modify(mid+1, to, (index<<1)+1, indexMod);
    }
    tree[index] = combine(tree[index<<1],tree[(index<<1)+1]);
}


int main() {
    scanf("%d",&n);
    for (int i = 1; i <= n; ++i) scanf("%d",&q[i]);
    build(1,n,1);
    int t;
    scanf("%d",&t);
    int a,b,c;
    for (int i = 0; i < t; ++i) {
        scanf("%d%d%d",&a,&b,&c);
        if (a == 0) {
            q[b] = c;
            modify(1,n,1,b);
        } else {
            printf("%ldn", ans(1,1,n,b,c).best);
        }

    }
    return 0;
}

Spoj GSS1 – CPP solution

Link to problem: http://www.spoj.com/problems/GSS1/
The solution is standard: a segment tree where information about the total sum, the maximum left possible, right possible and best sum.

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

struct node {
    long sum;
    long best;
    long left;
    long right;
};

int n;
long q[50003];
node tree[200003];

node makeNode(long sum, long best, long left, long right) {
    node tmp;
    tmp.sum = sum;
    tmp.best = best;
    tmp.left = left;
    tmp.right = right;
    return tmp;
}

node combine (node l, node r) {
    long left = l.left;
    if (l.sum + r.left>left) left =l.sum + r.left;
    long right = r.right;
    if (r.sum + l.right > right) right = r.sum + l.right;
    long best = max(l.right + r.left, max(l.best, r.best));
    return makeNode(l.sum+r.sum,best, left, right);
}

node build(int from, int to, int index) {
    if (from == to) {
        tree[index] = makeNode(q[from], q[from], q[from], q[from]);
        return tree[index];
    }
    int mid = (from+to)/2;
    node l = build(from,mid, (index<<1));
    node r = build(mid+1,to, (index<<1)+1);

    tree[index] = combine(l,r);
    return tree[index];
}

node ans(int index, int from, int to, int a, int b) {
    if (from == a && to == b) {
        return tree[index];
    }
    int mid = (from+to)/2;
    if (b <= mid) {
        return ans((index<<1), from, mid, a, b);
    }
    if (a > mid) {
        return ans((index<<1) + 1, mid+1,to,a,b);
    }
    node l = ans((index<<1), from, mid, a, mid);
    node r = ans((index<<1) + 1, mid+1,to,mid+1,b);
    return combine(l,r);
}


int main() {
    scanf("%d",&n);
    for (int i = 1; i <= n; ++i) scanf("%d",&q[i]);
    build(1,n,1);
    int t;
    scanf("%d",&t);
    int a,b;
    for (int i = 0; i < t; ++i) {
        scanf("%d%d",&a,&b);
        printf("%ldn", ans(1,1,n,a,b).best);
    }
    return 0;
}