Comparison of Bubble sort / PKU 3468: Simple Problem with Integers

セグメント木とBITの練習～.

BIT, 実装が楽ですね. これくらいなら覚えられそうです！

Comparison of Bubble sort

O(n log n)に落ちるんですねー. ぱない.
i < j, a_i > a_jとなる数の組を効率良く数えるために, Binary Indexed Treeを使います.
j - (a_j番目までの場所の数の和)が, 比較に必要な回数になります.
(実際に紙に書き表すと分かります)

#include <stdio.h>

#define N (1 << 17)
typedef __int64 ll;

int bit[N + 1], n;

int sum(int i){
    int s;
    s = 0;
    while (i > 0){
        s += bit[i];
        i -= i & -i;
    }
    return (s);
}

void add(int i, int x)
{
    while (i <= n){
        bit[i] += x;
        i += i & -i;
    }
}

int main(void)
{
    ll ans;
    int i;
    int data[100001];
    
    ans = 0;
    scanf("%d", &n);
    
    for (i = 0; i < n; i++){
        scanf("%d", &data[i]);
    }
    
    for (i = 0; i < n; i++){
        ans += i - sum(data[i]);
        add(data[i], 1);
    }
    
    printf("%I64d\n", ans);
    
    return (0);
}

PKU 3468 : A Simple Problem with Integers
r - lをr - 1と間違えなければ解けます.
一様加算を、非一様加算で分けたセグメント木を２つ用意すると, O(q log n) で解けます.
(蟻本を見ながら書いたので, もう一度自分で書き直します.)

#include <stdio.h>

#define MAX_SIZE  (1 << 18)

typedef long long ll;

ll data[MAX_SIZE - 1], datb[MAX_SIZE - 1]; // segment tree

int min(int a, int b)
{
    return (b > a ? a : b);
}

int max(int a, int b)
{
    return (a > b ? a : b);
}

void add(int a, int b, int x, int k, int l, int r)
{
    if (a <= l && r <= b){ //comletely inclusive.
        data[k] += x; //add to all segmets corresponds to [l, r).
    }
    else if (l < b && a < r){ //some of the segments are inclusive.
        datb[k] += (min(b, r) - max(a, l)) * x;  //add the x to the segments that belongs to [max(a, l), min(r, b)).
        add(a, b, x, k * 2 + 1, l, (l + r) / 2); //go to the left vertex.
        add(a, b, x, k * 2 + 2, (l + r) / 2, r); //go to the right vertex.
    }
}

ll sum(int a, int b, int k, int l, int r)
{
    if (b <= l || r <= a){ //looking segment[l, r) cross with the segment [a, b).
        return (0);
    }
    else if (a <= l && r <= b){ //completely inclusive.
        return (data[k] * (r - l) + datb[k]);
    }
    else { //some of the segments are inclusive.
        ll res;
        res = (min(b, r) - max(a, l)) * data[k];
        res += sum(a, b, k * 2 + 1, l, (l + r) / 2);
        res += sum(a, b, k * 2 + 2, (l + r) / 2, r);
        return (res);
    }
}

int main(void)
{
    int n, q;
    int i;
    int temp;
    char query[2];
    int l, r, x;
    
    scanf("%d%d", &n, &q);
    
    for (i = 0; i < n; i++){
        scanf("%d", &temp);
        add(i, i + 1, temp, 0, 0, n);
    }
    for (i = 0; i < q; i++){
        scanf("%s", query);
        if (query[0] == 'C'){
            scanf("%d%d%d", &l, &r, &x);
            add(l - 1, r, x, 0, 0, n);
        }
        else {
            scanf("%d%d", &l, &r);
            printf("%lld\n", sum(l - 1, r, 0, 0, n));
        }
    }
    
    return (0);
}