Algorithm24 数据结构 线段树

#include <iostream>
using namespace std;
const int maxn = 1e6+9;
int n, a[maxn<<1], sum[maxn<<1]; // a原数组 sum区间求和数组

void pushup(int k) {
    sum[k] = sum[k<<1]+sum[k<<1|1];
}

void build(int k, int l, int r) {
    if (l == r) {
        scanf("%d", a+k);
        sum[k] = a[k];
        return;
    }
    int mid = (l+r)>>1;
    build(k<<1, l, mid);
    build(k<<1|1, mid+1, r);
    pushup(k);
}

int query(int k, int l, int r, int ll, int rr) {
    int mid = (l+r)>>1;
    if (ll <= l && r <= rr) return sum[k];
    if (rr <= mid) return query(k<<1, l, mid, ll, rr);
    else if (ll >= mid+1) return query(k<<1|1, mid+1, r, ll, rr);
    else return query(k<<1, l, mid, ll, mid)+query(k<<1|1, mid+1, r, mid+1, rr);
}

int main() {
    scanf("%d", &n);
    build(1, 1, n);
    while (m--) {
        scanf("%d%d", &tl, &tr);
        printf("%d\n", query(1, 1, n, tl, tr));
    }
    return 0;
}

//5
//5 4 3 2 1
//4
//1 5
//1 2
//3 5
//2 4

#include <iostream>
using namespace std;
const int maxn = 5e5 + 9;
long long a[maxn], b[maxn];
int n, rev[maxn << 2];
#include <algorithm>

void pushup(int k) {
    rev[k] = rev[k << 1] + rev[k << 1 | 1];
}

void build(int k, int l, int r) {
    rev[k] = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    pushup(k);
}

void update(int k, int l, int r, int pos) {
    if (l == r && pos == l) {
        rev[k]++;
        return;
    }
    int mid = (l+r)>>1;
    if (pos <= mid) update(k<<1, l, mid, pos);
    else update(k<<1|1, mid+1, r, pos);
    pushup(k);
}

int query(int k, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) return rev[k];
    int mid = (l + r) >> 1, total_rev = 0;
    if (ll <= mid) total_rev += query(k << 1, l, mid, ll, rr);
    if (rr >= mid+1) total_rev += query(k << 1|1, mid + 1, r, ll, rr);
    return total_rev;
}

int main() {
    while (scanf("%d", &n) && n) {
        build(1, 1, n);
        for (int i = 0; i < n; ++i) {
            scanf("%lld", a + i);
            b[i] = a[i];
        }
        sort(b, b + n);
        int len = unique(b, b+n)-b;
        for (int i = 0; i < n; ++i) a[i] = lower_bound(b, b + len, a[i]) - b + 1;
        long long total = 0;
        for (int i = 0; i < n; ++i) {
            total += query(1, 1, n, a[i], n);
            update(1, 1, n, a[i]);
        }
        printf("%lld\n", total);
    }
    return 0;
}