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

OpenGL Simple Fractal tree

I wanted to draw a simple 2d fractal tree. This is the result.
fractal

#include <iostream>
#include <string>
#include <GL/glew.h>
#include <GL/freeglut.h>
#include <GL/glut.h>
#include <GL/gl.h>

#include "../common/Shader.hpp"
#include "../common/ShaderProgram.hpp"

#include <vector>
#include <cmath>

using namespace std;

struct Vector {
    float x;
    float y;
    Vector(float _x, float _y) : x(_x), y(_y) {};
    Vector operator + (const Vector & rht) const {
        return Vector(x + rht.x, y + rht.y);
    };
    Vector operator * (float v) const {
        return Vector(x*v, y*v);
    };
};

struct Branch {
    Vector direction;
    Vector position;
    float length;
    Branch(float _x, float _y, float _posX, float _posY, float _length) :
        direction(Vector(_x, _y)), position(Vector(_posX, _posY)), length(_length) {};
    Branch(Vector _direction, Vector _position, float _length) :
        direction(_direction), position(_position), length(_length) {};
};

vector<Branch> branches;
vector<Vector> triangles;

float m_BranchingAngle;
float m_LengthFactor;
size_t m_MaxDepth;


/*
    Since branches have a starting position, length and direction, we will need the end position of the branch.
    This is the start of the next branch.
*/
Vector getEndOfBranch(const Branch & branch) {
    Vector pos = branch.position + branch.direction * branch.length;
    return pos;
}

/*
    Just transforms the angle from degrees to radians
*/
inline float toRad(float angle) {
    return angle * M_PI / 180.0f;
}

/*
    rotates a vector given an angle in degrees
    it just multiplies the vector by the matrix
    cos(x) -sin(x)
    sin(x) cos(x)
*/
Vector rotateVector(const Vector & vec, float angle) {
    angle = toRad(angle);
    float aSin = sin(angle);
    float aCos = cos(angle);
    float newX = aCos * vec.x - aSin * vec.y;
    float newY = aSin * vec.x + aCos * vec.y;
    return Vector(newX, newY);
}

/*
    Recursive step to generate the branches
*/
void generateTreeRec(const Branch & parent, size_t currentDepth) {
    if (currentDepth == m_MaxDepth) return;
    branches.push_back(parent);
    Vector endPos = getEndOfBranch(parent);
    float newLength = parent.length * m_LengthFactor;
    static float halfAngle = m_BranchingAngle / 2.0f;
    Vector leftDirection = rotateVector(parent.direction, halfAngle);
    Vector rightDirection = rotateVector(parent.direction, -halfAngle);
    Branch leftBranch = Branch(leftDirection, endPos, newLength);
    Branch rightBranch = Branch(rightDirection, endPos, newLength);
    generateTreeRec(leftBranch, currentDepth+1);
    generateTreeRec(rightBranch, currentDepth+1);
}

/*
    Creates the tree and starts the recursive call
*/
void generateTree(float branchingAngle, float lengthFactor, size_t maxDepth) {
    m_BranchingAngle = branchingAngle;
    m_LengthFactor = lengthFactor;
    m_MaxDepth = maxDepth;

    Branch trunk = Branch(0.0f, 1.0f, 0.0f, -1.0f, 0.8f);

    generateTreeRec(trunk, 0);
}

/*
    Branches are already created but they cannot be drawn directly.
    We can simple create triangles to draw the brances like:
    --------
    |     /|
    |    / |
    |   /  |
    |  /   |
    | /    |
    |/     |
    --------
    Basically, we have the direction of the branch and we take the vector
    which is perpendicular to the direction. Then we create a vertex for the rectangle with a distance
    DELTA from the initial vertex. That's all.
    In this way, we have a rectangle and we can very easily triangulate.
*/
void transformBranchesToTriangles() {
    for (Branch branch : branches) {
        Vector start = branch.position;
        Vector end = getEndOfBranch(branch);
        Vector perpendicular = rotateVector(branch.direction, -90.0f);
        static float DELTA = 0.005f;
        Vector rStart = start + perpendicular * DELTA;
        Vector rEnd = end + perpendicular * DELTA;
        triangles.push_back(start);
        triangles.push_back(rStart);
        triangles.push_back(rEnd);
        triangles.push_back(end);
        triangles.push_back(start);
        triangles.push_back(rEnd);
    }
}

GLuint VAO;
GLuint VBA;

/*
    Everything else is standard. Just init the VAO and the VBA and load the shaders.
    The vertex shader is just a pass shader and the fragment shader just sets some color.
    Nothing special.
*/

void init() {
    generateTree(120.0f, 1.0f / 1.8f, 8);
    transformBranchesToTriangles();

    glGenVertexArrays(1, &VAO);
    glBindVertexArray(VAO);

    glGenBuffers(1, &VBA);
    glBindBuffer(GL_ARRAY_BUFFER, VBA);

    glBufferData(GL_ARRAY_BUFFER, triangles.size() * sizeof(Vector), &triangles[0], GL_STATIC_DRAW);


    ShaderProgram program = ShaderProgram(Shader("shader.vert", GL_VERTEX_SHADER),
     Shader("shader.frag", GL_FRAGMENT_SHADER) );

     glUseProgram(program.getProgram());

    glVertexAttribPointer(0, 2, GL_FLOAT, GL_FALSE, 0, 0);

    glEnableVertexAttribArray(0);

}

void display() {

    glClear(GL_COLOR_BUFFER_BIT);

    glBindVertexArray(VAO);
    glDrawArrays(GL_TRIANGLES,0, triangles.size());

    glFlush();

}


int main(int argc, char ** argv)
{
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_RGBA);
    glutInitWindowSize(512, 512);
    glutInitContextVersion(4,3); // freeglut required
    glutInitContextProfile(GLUT_CORE_PROFILE);
    glutCreateWindow("");
    glewExperimental=GL_TRUE;
    if (glewInit()) {
        cerr << "Problem initializing glew" << endl;
        exit(EXIT_FAILURE);
    }

    init();

    glutDisplayFunc(display);

    glutMainLoop();

    return 0;
}

Note that instead of making the rectangles using 2 triangles, we could have drawn the GL_LINES primitive and also set the width of the line by changing the state with glLineWidth(float)

Error compiling opengl code under Linux

If you have a NVidia card, you are using Linux and trying to compile something using Opengl, then you might have run into the following error:

Inconsistency detected by ld.so: dl-version.c: 224: _dl_check_map_versions: Assertion `needed != ((void *)0)' failed!

This most probably happen to incosistency between NVidia and Mesa drivers for your card. It would be best to choose to use the NVidia drivers in most cases.
Go to directory usr/lib/nvidia-***
It could be nvidia-***-update or something like that. There should be a libGL.so file there. You have to link it to your code. Remove -lGL from the other linker options.

CodeForces B. The least round way – CPP solution

Link to problem:
Almost classic dynamic programming problem. Key is that you have to minimize the number of 2s and 5s and also consider the case when there could be a 0 in the input meaning that the upper bound for the answer becomes 1. However, the best answer could be still 0. Consider the input case:
3
1 1 1
1 0 1
1 1 1
There is a 0, but if you walk on the border, then the answer is 0, not 1.

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

#define MAX 1001

struct Pair {
    long fives;
    long twos;
};

long twos[MAX][MAX];
long fives[MAX][MAX];
long t[MAX][MAX];
int n;
char path[3*MAX];
char path_matrix_twos[MAX][MAX];
char path_matrix_fives[MAX][MAX];

Pair makePair(long twos, long fives) {
    Pair p;
    p.twos = twos;
    p.fives = fives;
    return p;
}

Pair compPair(int i, int j) {
    long twos=0, fives=0;
    int cpy = t[i][j];
    do {
        if (cpy%2 == 0) {
            ++twos;
            cpy /= 2;
        } else if (cpy%5 == 0) {
            ++fives;
            cpy /=5;
        } else {
            break;
        }
    }
    while(cpy!=0);
    return makePair(twos,fives);
}

void comp() {
    for (int i = 1; i < n; ++i) {
        twos[0][i] += twos[0][i-1];
        twos[i][0] += twos[i-1][0];
        path_matrix_twos[0][i] = 'L';
        path_matrix_twos[i][0] = 'T';
        fives[0][i] += fives[0][i-1];
        fives[i][0] += fives[i-1][0];
        path_matrix_fives[0][i] = 'L';
        path_matrix_fives[i][0] = 'T';
    }
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < n; ++j) {
            if (twos[i-1][j] < twos[i][j-1]) {
                twos[i][j] += twos[i-1][j];
                path_matrix_twos[i][j] = 'T';
            } else {
                twos[i][j] += twos[i][j-1];
                path_matrix_twos[i][j] = 'L';
            }
            if (fives[i-1][j] < fives[i][j-1]) {
                fives[i][j] += fives[i-1][j];
                path_matrix_fives[i][j] = 'T';
            } else {
                fives[i][j] += fives[i][j-1];
                path_matrix_fives[i][j] = 'L';
            }
        }
    }
}

int main() {
    scanf("%d",&n);
    int zero = 0;
    int zeroPosI, zeroPosJ;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%ld", &t[i][j]);
            Pair p = compPair(i,j);
            twos[i][j] = p.twos;
            fives[i][j] = p.fives;
            if (t[i][j]==0) {
                zero = 1;
                zeroPosI = i;
                zeroPosJ = j;
            }
        }
    }
    comp();
    long ans = min(twos[n-1][n-1], fives[n-1][n-1]);
    if (ans > 1 && zero==1) {
        ans = 1;
        int idx=0;
        for (int i = 0; i < zeroPosI; ++i) {
            path[idx++] = 'D';
        }
        for (int j = 0; j < zeroPosJ; ++j) {
            path[idx++] = 'R';
        }
        for (int i = zeroPosI; i < n-1; ++i) {
            path[idx++] = 'D';
        }
        for (int j = zeroPosJ; j < n-1; ++j) {
            path[idx++] = 'R';
        }
    } else {
        if (twos[n-1][n-1] < fives[n-1][n-1]) {
            int x = n-1, y = n-1;
            for (int i = 2*(n-1) -1; i>=0; --i) {
                if (path_matrix_twos[y][x] == 'L') {
                    --x;
                    path[i] = 'R';
                } else {
                    --y;
                    path[i] = 'D';
                }
            }
        } else {
            int x = n-1, y = n-1;
            for (int i = 2*(n-1) -1; i>=0; --i) {
                if (path_matrix_fives[y][x] == 'L') {
                    --x;
                    path[i] = 'R';
                } else {
                    --y;
                    path[i] = 'D';
                }
            }
        }
    }




    printf("%ldn", ans);
    printf("%sn", path);
    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;
}

SPOJ 18963. Bhagat The Bit Man – cpp solution

It was a nice problem. I think this should count as one of my first bitmask problems.

#include <cstdio>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    long long number =0;
    long long mask=0;
    long long val;
    mask = ~(0LL);
    for (int i =0; i < n; ++i) {
        scanf("%lld", &val);
        number |= val;
        mask = mask&val;
    }
    number ^= mask;
    printf("%lldn", number);
    return 0;
}

SPOJ 3878. Rectangles Perimeter – CPP solution

Another nice dp problem though quite easy.

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

long dp[1001][2];

 long max(long a, long b) {
    if (a < b) return b;
    return a;
}

long abs(long a) {
    return a > 0 ? a : -a;
}

int main() {
    int n;
    scanf("%d", &n);
    int a,b;
    int preva,prevb;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d",&a,&b);
        if (i == 0) {
            dp[i][0]=a;
            dp[i][1]=b;
        } else {
            dp[i][0]=max(dp[i-1][1]+abs(b-preva),dp[i-1][0]+abs(b-prevb))+a;
            dp[i][1]=max(dp[i-1][1]+abs(a-preva),dp[i-1][0]+abs(a-prevb))+b;

        }
        preva=a;
        prevb=b;
    }
    printf("%ldn", max(dp[n-1][0],dp[n-1][1]));
    return 0;
}