归并排序求逆序对

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 小朋友排队_归并 {
    static Child[] children;
    static Child[] temp;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        children = new Child[n];
        temp = new Child[n];
        String[] numString = bf.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            children[i] = new Child(Integer.parseInt(numString[i]));
        }
        mergeSort(0,n-1);
        long res = 0;
        for (int i = 0; i < n; i++) {
            res += cal(children[i].k);
        }
        System.out.println(res);
    }

    private static long cal(int k) {
        return (1L* k * (k + 1)) / 2;
    }

    private static void mergeSort(int l, int r) {
        if (l == r) return;
        int mid = (l + r) >> 1;
        mergeSort(l,mid);
        mergeSort(mid+1,r);
        merge(l,mid,r);
    }

    private static void merge(int l, int mid, int r) {
        int i = l;
        int j = mid+1;
        int k = l;
        while (i <= mid && j <= r){
            if (children[i].h <= children[j].h){
                children[i].k += (j - mid - 1);
                temp[k++] = children[i++];
            }else {
                children[j].k += mid - i + 1;
                temp[k++] = children[j++];
            }
        }
        while (i <= mid){
            //此时右边区间的所有的都是小于i所在位置的小朋友的
            children[i].k += r - mid;
            temp[k++] = children[i++];
        }
        while (j <= r) temp[k++] = children[j++];
        for (int m = l; m <=r ; m++) {
            children[m] = temp[m];
        }

    }
    static class Child{
        int h;//小朋友的高度
        int k;//该小朋友所涉及的逆序对的个数,即该小朋友需要交换的次数

        public Child(int h) {
            this.h = h;
        }
    }
}

树状数组

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 小朋友排队_树状数组 {
    /**
     * tree统计的是身高频数分布的区间和
     * 相当于有这样一个数组:count[],count[i]代表的是当前遍历到的元素中，身高为i的元素的个数
     * 对于每一个身高为h的小朋友，它的逆序对就是他前面比他高的小朋友的个数+他后面比他矮的小朋友个数
     * 他前面比他高的小朋友个数=他前面身高在[h+1,max]这个区间内的元素个数,就是h-1的前缀和
     * 他后面比他矮的小朋友的个数=他后面身高在[0,h-1]这区间内的元素个数=sum[h-1]
     */
    static int[] tree;
    static int[] h;
    static int[] cnt;//存储答案
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        h = new int[n];
        cnt = new int[n];
        String[] numString = bf.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            //因为有身高为0的元素,树状数组的索引必须从1开始，所以给每个小朋友的身高加一
            h[i] = Integer.parseInt(numString[i]) + 1;
        }
        bf.close();
        tree = new int[1000002];
        for (int i = 0; i < n; i++) {
            //从前往后遍历，找前面比当前高的,getSum相当于query方法，个人命名爱好
            int count = getSum(1000001) - getSum(h[i]);
            cnt[i] += count;
            add(h[i],1);
        }
        //要重新遍历，所以重置树状数组
        tree = new int[1000002];
        for (int i = n-1; i >= 0 ; i--) {
            //找后面比他小的
            int count = getSum(h[i] - 1);
            cnt[i] += count;
            add(h[i],1);
        }
        long res = 0;
        for (int i = 0; i < n; i++) {
            res += cal(cnt[i]);
        }
        System.out.println(res);
    }

    private static long cal(int k) {
        return (1L * k * (k + 1)) / 2;
    }

    private static void add(int x, int val) {
        for (int i = x; i <= 1000001 ; i+= lowbit(i)) {
            tree[i] += val;
        }
    }

    private static int getSum(int x) {
        //tree[x]的范围为(x -lowbit(x),x]
        int sum = 0;
        for (int i = x; i > 0 ; i-= lowbit(i)) {
            sum += tree[i];
        }
        return sum;
    }
    private static int lowbit(int x){
        return x & -x;
    }
}

线段树

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 小朋友排队_线段树 {
    /**
     * 线段树是通过一个一个的节点维护了整个数组的信息,这个数组依旧是身高频数数组
     */
    static Node[] tree = new Node[4000004];
    static int[] h;
    static int[] cnt;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        init(n,bf);
        build(1,1000001,1);
        for (int i = 0; i < n; i++) {
            //从前往后遍历，找比当前大的,当前为h[i]
            int count = getSum(h[i]+1,1000001,1);
            cnt[i] += count;
            add(h[i],1,1);
        }
        build(1,1000001,1);//重新建树
        for (int i = n-1; i >= 0 ; i--) {
            //从后往前遍历，寻找后面比当前数小的
            int count = getSum(1,h[i]-1,1);
            cnt[i] += count;
            add(h[i],1,1);
        }
        long res = 0;
        for (int i = 0; i < n; i++) {
            res += cal(cnt[i]);
        }
        System.out.println(res);
    }

    private static void add(int x, int val, int treeIndex) {
        Node curNode = tree[treeIndex];
        if (curNode.l == curNode.r && curNode.l == x){
            curNode.sum += val;
            return;
        }
        int mid = (curNode.l + curNode.r) >> 1;
        if (x <= mid){
            add(x,val,treeIndex * 2);
        }else {
            add(x,val,treeIndex * 2 + 1);
        }
        pushUp(treeIndex);
    }

    private static void pushUp(int treeIndex) {
        tree[treeIndex].sum = tree[treeIndex * 2].sum + tree[treeIndex * 2 + 1].sum;
    }

    private static int getSum(int l, int r, int treeIndex) {
        if (l > r) return 0;
        Node curNode = tree[treeIndex];
        if (curNode.l == l && curNode.r == r ){//
            return curNode.sum;
        }
        int mid = (curNode.l + curNode.r) >> 1;
        if(r <= mid){
            return getSum(l,r,treeIndex * 2);
        }else if (l >= mid + 1){
            return getSum(l,r,treeIndex * 2 + 1);
        }else {
            return getSum(l,mid,treeIndex * 2) + getSum(mid + 1 ,r ,treeIndex * 2 + 1);
        }
    }

    private static void build(int l, int r, int treeIndex) {
        tree[treeIndex] = new Node(l,r,0);
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(l,mid,treeIndex * 2);
        build(mid+1,r,treeIndex * 2 + 1);
    }

    private static long cal(int k) {
        return 1L * k * (k + 1) / 2;
    }




    private static void init(int n,BufferedReader bf ) throws IOException {
        h = new int[n];
        cnt = new int[n];
        String[] numString = bf.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            h[i] = Integer.parseInt(numString[i]) + 1;
        }
    }

    static class Node{
        int l;
        int r;
        int sum;

        public Node(int l, int r, int sum) {
            this.l = l;
            this.r = r;
            this.sum = sum;
        }
    }
}