Competitive programming template

olymp_template.cpp

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <cmath>
#include <utility>
#include <time.h>
#include <stack>

using namespace std;

#define ll long long
#define pr(v) cout << #v << " = " << v << "\n";

int leftBinSearch(vector<int> & arr, int val) {
    int left = 0, right = arr.size();
    // инвариант:
    // arr[>=r] >= val
    // arr[< l] <  val
    // поэтому когда left = right, left == левая граница

    while (right != left) {
        int mid = (left + right) / 2;

        if (arr[mid] < val) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    if (left == arr.size() or arr[left] != val) {
        return -1;
    } else {
        return left;
    }
}

int rightBinSearch(vector<int> & arr, int val) {
    int left = -1, right = arr.size() - 1;
    // инвариант:
    // arr[> r] >  val
    // arr[<=l] <= val
    // поэтому когда left = right, left == правая граница

    while (right != left) {
        int mid = (left + right + 1) / 2;

        if (arr[mid] > val) {
            right = mid - 1;
        } else {
            left = mid;
        }
    }

    if (left == -1 or arr[left] != val) {
        return -1;
    } else {
        return left;
    }
}

// дерево отрезков для суммы
// http://informatics.mccme.ru//mod/statements/view.php?chapterid=1364
template <typename T>
class SegmentTree {

private:
    // в arr[0] хранится "сумма" на всём отрезке
    vector<T> arr;
    vector<T> difference;
    
    unsigned originIndex;
    unsigned queryL, queryR;
    T updateValue;

    void push(unsigned node, unsigned left, unsigned right) {
        difference[2 * node + 1] += difference[node];
        difference[2 * node + 2] += difference[node];
        difference[node] = 0;
    }

    T _query(unsigned node, unsigned left, unsigned right) {

        if (left > queryR or right < queryL) {
            return 0;
        }

        if (left >= queryL and right <= queryR) {
            return arr[node] + (right - left + 1) * difference[node];
        }

        push(node, left, right);
        unsigned leftSonLeft = left, leftSonRight = left + (right - left) / 2;
        unsigned rightSonLeft = leftSonRight + 1, rightSonRight = right;

        T returnValue =
            _query(2 * node + 1, leftSonLeft, leftSonRight) +
            _query(2 * node + 2, rightSonLeft, rightSonRight);

        arr[node] = arr[2 * node + 1] + difference[2 * node + 1] * (leftSonRight - leftSonLeft + 1) +
                    arr[2 * node + 2] + difference[2 * node + 2] * (rightSonRight - rightSonLeft + 1);

        return returnValue;
    }

    void _update(unsigned node, unsigned left, unsigned right) {

        if (left > queryR or right < queryL) {
            return;
        }

        if (left >= queryL and right <= queryR) {
            difference[node] += updateValue;
            return;
        }

        push(node, left, right);
        unsigned leftSonLeft = left, leftSonRight = left + (right - left) / 2;
        unsigned rightSonLeft = leftSonRight + 1, rightSonRight = right;

        _update(2 * node + 1, leftSonLeft, leftSonRight);
        _update(2 * node + 2, rightSonLeft, rightSonRight);

        arr[node] = arr[2 * node + 1] + difference[2 * node + 1] * (leftSonRight - leftSonLeft + 1) +
                    arr[2 * node + 2] + difference[2 * node + 2] * (rightSonRight - rightSonLeft + 1);
    }

public:
    SegmentTree(unsigned n) {
        unsigned newSize = 1;
        while (newSize < n) {
            newSize *= 2;
        }
        newSize *= 2;

        arr.resize(newSize);
        difference.resize(newSize);
        originIndex = (newSize / 2) - 1;
    }

    SegmentTree(vector<T> &  origin): SegmentTree(origin.size()) {
        std::copy(origin.begin(), origin.end(), arr.begin() + originIndex);

        for (int i = originIndex - 1; i >= 0; --i) {
            arr[i] = arr[2 * i + 1] + arr[2 * i + 2];
        }
    }

    T query(unsigned left, unsigned right) {
        queryL = left;
        queryR = right;
        return _query(0, 0, originIndex);
    }

    void update(unsigned left, unsigned right, T value) {
        queryL = left;
        queryR = right;
        updateValue = value;
        _update(0, 0, originIndex);
    }
};

int main()
{
    //clock_t tStart = clock();

    //freopen("/home/shrubb/Projects/ClionProjects/Olymp/input.txt", "r", stdin);
    //freopen("/home/shrubb/Projects/ClionProjects/Olymp/input.txt", "w", stdout);
    ios_base::sync_with_stdio(false);

    //cout.precision(10);
    //cout << fixed;

}