敌兵布阵

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

using namespace std;

const int N = 50010;

int t[N];
int c, n;
int casei;

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

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

        t[x] += k;
}

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

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

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

int main() {
    int T;
    scanf("%d", &T);

    while (T -- ) {
        memset(t, 0, sizeof t);
        scanf("%d", &n);

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

            scanf("%d", &c);
            add(i, c);
        }

        printf("Case %d:\n", ++ casei);
        char op[6];

        while (~scanf("%s", op)) {
            if (op[0] == 'E')
                break;
            int a, b;
            scanf("%d%d", &a, &b);

            if (op[0] == 'A')
                add(a, b);
            else if (op[0] == 'S')
                add(a, -b);
            else
                printf("%d\n", ask(b) - ask(a - 1));
        }
    }

    return 0;
}

See you~

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

using namespace std;

const int N = 1010;
int t[N][N];
int casei;

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

void add(int x, int y, int c) {
    for (int i = x ; i < N ; i += lowbit(i))

        for (int j = y ; j < N ; j += lowbit(j))

            t[i][j] += c;
}

void init() {
    memset(t, 0, sizeof t);

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

        for (int j = 1 ; j < N ; j ++ )

            add(i, j, 1);
}

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

    for (int i = x ; i > 0 ; i -= lowbit(i))

        for (int j = y ; j > 0 ; j -= lowbit(j))

            res += t[i][j];
    return res;
}

int getsum(int x, int y) {
    return ask(x + 1, y + 1) - ask(x, y + 1) - ask(x + 1, y) + ask(x, y);
}

int main() {
    int T;
    scanf("%d", &T);
    int x1, y1, x2, y2, n1;

    while (T -- ) {
        printf("Case %d:\n", ++ casei);
        init();
        int m;
        scanf("%d", &m);
        char op[2];

        while (m -- ) {
            scanf("%s", op);

            if (op[0] == 'S') {
                scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

                if (x1 > x2)
                    swap(x1, x2);

                if (y1 > y2)
                    swap(y1, y2);
                printf("%d\n", ask(x2 + 1, y2 + 1) - ask(x1, y2 + 1) - ask(x2 + 1, y1) + ask(x1, y1));
            } else if (op[0] == 'A') {
                scanf("%d%d%d", &x1, &y1, &n1);
                add(x1 + 1, y1 + 1, n1);
            } else if (op[0] == 'D') {
                scanf("%d%d%d", &x1, &y1, &n1);
                int k = getsum(x1, y1);
                n1 = min(n1, k);

                add(x1 + 1, y1 + 1, -n1);
            } else {
                scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &n1);
                int k = getsum(x1, y1);
                n1 = min(n1, k);

                add(x1 + 1, y1 + 1, -n1);
                add(x2 + 1, y2 + 1, n1);
            }
        }
    }

    return 0;
}

MooFest

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

using namespace std;

const int N = 20010;

typedef long long LL;

LL t1[N];
LL t2[N];
int max_x;
LL s_x[N];

struct node {
    int v, x;
    bool operator<(const node &t) const {
        return v < t.v;
    }
} cow[N];

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

void add(LL arr[], int x, int k) {
    for ( ; x <= max_x; x += lowbit(x))

        arr[x] += k;
}

LL get_sum(LL arr[], int x) {
    LL res = 0;

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

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

int main() {
    int n;
    scanf("%d", &n);

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

        scanf("%d%d", &cow[i].v, &cow[i].x);
        max_x = max(max_x, cow[i].x);
    }

    sort(cow + 1, cow + 1 + n);

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

        s_x[i] = s_x[i - 1] + cow[i].x;
    LL ans = 0;

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

        LL min_s = get_sum(t1, cow[i].x);
        LL max_s = i - 1 - min_s;
        LL min_dis = get_sum(t2, cow[i].x);
        LL max_dis = s_x[i - 1] - min_dis;
        ans += cow[i].v * (min_s * cow[i].x - min_dis);
        ans += cow[i].v * (max_dis - max_s * cow[i].x);
        add(t1, cow[i].x, 1), add(t2, cow[i].x, cow[i].x);
    }

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