I Hate It

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

using namespace std;

const int N = 2e5 + 10;

int n, m;
int t[N];
int w[N];

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

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

        t[x] = k;

        for (int i = 1; i < lowbit(x); i <<= 1)

            t[x] = max(t[x], t[x - i]);
    }
}

int ask(int l, int r) {
    int res = 0;

    while (l <= r) {
        res = max(res, w[r]);
        r -- ;

        for ( ; l <= r - lowbit(r); r -= lowbit(r))

            res = max(res, t[r]);
    }

    return res;
}

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

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

            scanf("%d", &w[i]);
            add(i, w[i]);
        }

        while (m -- ) {
            char op[2];
            int a, b;
            scanf("%s%d%d", op, &a, &b);

            if (op[0] == 'Q')
                printf("%d\n", ask(a, b));
            else {
                w[a] = b;
                add(a, b);
            }
        }
    }

    return 0;
}

A Number Puzzle

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

using namespace std;

const int N = 5e6 + 10;

int n, m;
int a[10];
int T[N], pos;

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

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

            scanf("%d", &a[i]);
        sort(a, a + n);

        do {
            if (a[0]) {
                int sum = 0;

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

                    sum = sum * 10 + a[i];
                T[pos ++ ] = sum;
            }
        } while (next_permutation(a, a + n));

        sort(T, T + pos);

        while (m -- ) {
            bool flag = false;
            int x, k;
            scanf("%d%d", &x, &k);

            for (int i = 0; i < pos; i ++ )

                if ((x + T[i]) % k == 0) {
                    printf("%d\n", T[i]);
                    flag = true;
                    break;
                }

            if (!flag)
                puts("None");
        }
    }

    return 0;
}

Billboard

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

using namespace std;

const int N = 2e5 + 10;

int h, w, n;
int a[N];
int t[N * 10];

void build_tree(int id, int l, int r) {
    if (l >= r)
        t[id] = w;
    else {
        int mid = (l + r) / 2;
        int left = id * 2;
        int right = id * 2 + 1;
        build_tree(left, l, mid), build_tree(right, mid + 1, r);
        t[id] = max(t[left], t[right]);
    }
}

int update(int id, int l, int r, int k) {
    if (l >= r) {
        t[id] -= k;
        return l;
    } else {
        int res = 0;
        int mid = (l + r) / 2;
        int left = id * 2;
        int right = id * 2 + 1;

        if (t[left] >= k)
            res = update(left, l, mid, k);
        else
            res = update(right, mid + 1, r, k);
        t[id] = max(t[left], t[right]);
        return res;
    }
}

int main() {
    while (~scanf("%d%d%d", &h, &w, &n)) {
        if (h > n)
            h = n;
        build_tree(1, 1, h);

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

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

            if (a[i] > t[1])
                puts("-1");
            else
                printf("%d\n", update(1, 1, h, a[i]));
        }
    }

    return 0;
}

Minimum Inversion Number

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

using namespace std;

const int N = 5010;

typedef long long LL;

int q[N], a[N];
int tmp[N];
int n;

LL merge_sort(int l, int r) {
    if (l >= r)
        return 0;
    int mid = (l + r) / 2;
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
    int k = 0, i = l, j = mid + 1;

    while (i <= mid && j <= r) {
        if (q[i] <= q[j])
            tmp[k ++ ] = q[i ++ ];
        else {
            tmp[k ++ ] = q[j ++ ];
            res += mid - i + 1;
        }
    }

    while (i <= mid)
        tmp[k ++ ] = q[i ++ ];

    while (j <= r)
        tmp[k ++ ] = q[j ++ ];

    for (int i = l, j = 0; i <= r; i ++, j ++ )

        q[i] = tmp[j];
    return res;
}

int main() {
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i ++ ) {

            scanf("%d", &a[i]);
            q[i] = a[i];
        }

        LL ans = merge_sort(0, n - 1);
        LL res = ans;

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

            ans = ans - a[i] + n - 1 - a[i];
            res = min(res, ans);
        }

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

    return 0;
}