I Hate It

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;

int tree[N * 4], arr[N * 4];
int n, m;

void build_tree(int node, int l, int r) {
    if (l >= r) {
        tree[node] = arr[l];
        return;
    }

    int mid = (l + r) / 2;
    int left_node = 2 * node;
    int right_node = 2 * node + 1;
    build_tree(left_node, l, mid), build_tree(right_node, mid + 1, r);
    tree[node] = max(tree[left_node], tree[right_node]);
}

void update_tree(int node, int l, int r, int idx, int val) {
    if (l >= r) {
        arr[idx] = val;
        tree[node] = val;
        return;
    }

    int mid = (l + r) / 2;
    int left_node = 2 * node;
    int right_node = 2 * node + 1;

    if (idx <= mid)
        update_tree(left_node, l, mid, idx, val);
    else
        update_tree(right_node, mid + 1, r, idx, val);
    tree[node] = max(tree[left_node], tree[right_node]);
}

int query_tree(int node, int l, int r, int start, int end) {
    int res = 0;

    if (l >= start && r <= end) {
        return tree[node];
    }

    int mid = (l + r) / 2;
    int left_node = 2 * node;
    int right_node = 2 * node + 1;

    if (start <= mid)
        res = max(res, query_tree(left_node, l, mid, start, end));

    if (mid < end)
        res = max(res, query_tree(right_node, mid + 1, r, start, end));
    return res;
}

int main() {
    while (~scanf("%d%d", &n, &m)) {
        memset(tree, 0, sizeof tree);

        for (int i = 1; i <= n; i ++ )

            scanf("%d", &arr[i]);
        build_tree(1, 1, n);
        char op[2];
        int a, b;

        while (m -- ) {
            scanf("%s%d%d", op, &a, &b);

            if (op[0] == 'Q')
                printf("%d\n", query_tree(1, 1, n, a, b));
            else
                update_tree(1, 1, n, a, b);
        }
    }

    return 0;
}

Minimum Inversion Number

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5010, INF = 0x3f3f3f3f;

typedef long long LL;

int tree[N * 4], arr[N * 4];
int n;

void build_tree(int node, int l, int r) {
    if (l >= r) {
        tree[node] = 0;
        return;
    }

    int mid = (l + r) / 2;
    int left_node = 2 * node;
    int right_node = 2 * node + 1;
    build_tree(left_node, l, mid), build_tree(right_node, mid + 1, r);
    tree[node] = tree[left_node] + tree[right_node];
}

void update_tree(int node, int l, int r, int val) {
    if (l >= r) {
        tree[node] ++ ;
        return;
    }

    int mid = (l + r) / 2;
    int left_node = 2 * node;
    int right_node = 2 * node + 1;

    if (val <= mid)
        update_tree(left_node, l, mid, val);
    else
        update_tree(right_node, mid + 1, r, val);
    tree[node] = tree[left_node] + tree[right_node];
}

int query_tree(int node, int l, int r, int start, int end) {
    int res = 0;

    if (l >= start && r <= end) {
        return tree[node];
    }

    int mid = (l + r) / 2;
    int left_node = 2 * node;
    int right_node = 2 * node + 1;

    if (start <= mid)
        res += query_tree(left_node, l, mid, start, end);

    if (mid < end)
        res += query_tree(right_node, mid + 1, r, start, end);
    return res;
}

int main() {
    while (~scanf("%d", &n)) {
        memset(tree, 0, sizeof tree);

        for (int i = 1; i <= n; i ++ )

            scanf("%d", &arr[i]);
        build_tree(1, 1, n);
        LL ans = INF;
        LL cnt = 0;

        for (int i = 1; i <= n; i ++ ) {

            cnt += query_tree(1, 1, n, arr[i] + 1, n);
            update_tree(1, 1, n, arr[i] + 1);
        }

        ans = cnt;

        for (int i = 1; i <= n; i ++ ) {

            cnt = cnt - arr[i] + n - 1 - arr[i];
            ans = min(ans, cnt);
        }

        printf("%lld\n", ans);
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5010, INF = 0x3f3f3f3f;

typedef long long LL;

int tree[N], arr[N];
int n;

int lowbit(int x) {
    return x & -x;
}

void add(int x) {
    for ( ; x <= n; x += lowbit(x))

        tree[x] ++ ;
}

int ask(int x) {
    int res = 0;

    for ( ; x; x -= lowbit(x))

        res += tree[x];
    return res;
}

int main() {
    while (~scanf("%d", &n)) {
        memset(tree, 0, sizeof tree);

        for (int i = 1; i <= n; i ++ )

            scanf("%d", &arr[i]);

        LL ans = INF;
        LL cnt = 0;

        for (int i = 1; i <= n; i ++ ) {

            add(arr[i] + 1);
            cnt += i - ask(arr[i] + 1);
        }

        ans = cnt;

        for (int i = 1; i <= n; i ++ ) {

            cnt = cnt - arr[i] + n - 1 - arr[i];
            ans = min(ans, cnt);
        }

        printf("%lld\n", ans);
    }

    return 0;
}

Atlantis

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210;

struct edge {
    double x, y1, y2;
    int state;
    edge() {
    }
    edge(double a, double b, double c, int d) : x(a), y1(b), y2(c), state(d) {
    }
    bool operator < (const edge &t) const {
        return x < t.x;
    }
} line[N];

double v[N];
double len[N * 4];
int add[N * 4];
int n;
int casei;

void pushup(int k, int l, int r) {
    if (add[k])
        len[k] = v[r] - v[l];
    else if (r - l == 1)
        len[k] = 0;
    else {
        int ls = k * 2 + 1;
        int rs = k * 2 + 2;
        len[k] = len[ls] + len[rs];
    }
}

void update_tree(int start, int end, int val, int k, int l, int r) {
    if (end <= l || r <= start)
        return;

    if (start <= l && r <= end) {
        add[k] += val;
        pushup(k, l, r);
        return;
    }

    int mid = (l + r) / 2;
    int ls = k * 2 + 1;
    int rs = k * 2 + 2;
    update_tree(start, end, val, ls, l, mid);
    update_tree(start, end, val, rs, mid, r);
    pushup(k, l, r);
}

int main() {
    while (~scanf("%d", &n)) {
        if (n == 0)
            break;
        double a, b, c, d;

        for (int i = 0; i < n; i ++ ) {

            scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
            line[i] = edge(a, b, d, 1);
            line[i + n] = edge(c, b, d, -1);
            v[i] = b;
            v[i + n] = d;
        }

        n *= 2;
        sort(line, line + n);
        sort(v, v + n);
        int vn = unique(v, v + n) - v;
        double ans = 0;

        for (int i = 0; i < n; i ++ ) {

            if (i)
                ans += (line[i].x - line[i - 1].x) * len[0];
            int L = lower_bound(v, v + vn, line[i].y1) - v;
            int R = lower_bound(v, v + vn, line[i].y2) - v;
            update_tree(L, R, line[i].state, 0, 0, n);
        }

        printf("Test case #%d\n", ++ casei);
        printf("Total explored area: %.2lf\n\n", ans);
    }

    return 0;
}

Buy Tickets

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;

struct node {
    int pos, val;
} person[N];

int tree[N * 4];
int n;
int ans[N];

void build_tree(int k, int l, int r) {
    if (l >= r) {
        tree[k] = 1;
        return;
    }

    int mid = (l + r) / 2;
    int ls = k * 2;
    int rs = k * 2 + 1;
    build_tree(ls, l, mid), build_tree(rs, mid + 1, r);
    tree[k] = tree[ls] + tree[rs];
}

void update_tree(int k, int l, int r, int idx, int val) {
    if (l >= r) {
        tree[k] = 0;
        ans[l] = val;
        return;
    }

    int mid = (l + r) / 2;
    int ls = k * 2;
    int rs = k * 2 + 1;

    if (tree[ls] >= idx)
        update_tree(ls, l, mid, idx, val);
    else
        update_tree(rs, mid + 1, r, idx - tree[ls], val);
    tree[k] = tree[ls] + tree[rs];
}

int main() {
    while (~scanf("%d", &n)) {
        memset(tree, 0, sizeof tree);

        for (int i = 1; i <= n; i ++ )

            scanf("%d%d", &person[i].pos, &person[i].val);
        build_tree(1, 1, n);

        for (int i = n; i; i -- )

            update_tree(1, 1, n, person[i].pos + 1, person[i].val);

        for (int i = 1; i <= n; i ++ ) {

            if (i != n)
                printf("%d ", ans[i]);
            else
                printf("%d\n", ans[i]);
        }
    }

    return 0;
}