1439: 蓝桥杯历届试题-小朋友排队(权值线段树) Java AC代码

解题思路:尝试使用了比树状数组功能更强大的线段树，线段树可以解决所有用树状数组解决的题，唯一缺点就是需要开辟4*n的大小才能保证不溢出。
注意事项:
对于本题来说，即求数组中某数的逆序对，然后求其等差数列的和即可。本代码没有构造权值线段树的过程，而是直接进行update操作，免去了建树的时间。需要注意的是，需要对给定数组进行两次遍历，一次得到前置逆序，一次得到后置逆序，最后拼接结果即可。

看到有佬还是用了lazy标记让我很不解。。为什么对这样单点修改更新的操作还需要延迟呢？

总的来说，本题算是一道树状数组和线段树的模板题
参考代码:

import java.io.*;

// 蓝桥杯历届试题-小朋友排队 - C语言网 (dotcpp.com)
public class Main {
    static StreamTokenizer cin;
    static PrintWriter out;
    static int n; // 小朋友的个数
    static int[] arr;  // 小朋友身高
    static long[] cnt; // 每个小朋友最少需要交换的次数
    static int[] treeArr;
    static int maxN = -1;  // 存储上值域
    public static void main(String[] args) throws IOException {
        cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(new OutputStreamWriter(System.out));
        n = nextInt();
        arr = new int[n+1];
        cnt = new long[n+1];
        for(int i = 1; i < n+1; i++){
            int num = nextInt();
            arr[i] = num;
            maxN = Math.max(maxN, num);
        }
        treeArr = new int[(maxN << 2)+10];
        for(int i = 1; i < n+1; i++){
            update(0, 0, maxN, arr[i]);
            // 存储i左边比arr[i]大的元素
            cnt[i] += query(0, 0, maxN, arr[i]+1, maxN);
        }
        // 重构
        treeArr = new int[4*maxN +10];
        for(int i = n; i > 0; i--){
            update(0, 0, maxN, arr[i]);
            // 存储i右边比arr[i]小的元素
            cnt[i] += query(0, 0, maxN, 0, arr[i]-1);
        }
        long res = 0;
        for(int i = 1; i < n+1; i++){
            res += cnt[i]*(cnt[i] + 1)/2;
        }
        out.println(res);
        out.flush();

    }

    // 单点修改, 不需要lazy标记, L和R为此节点值域范围
    static void update(int node, int L, int R, int value){
        if(L == value && R == value){  // 叶子
            treeArr[node]++;  // 重复值++
            return;
        }
        int mid = (L+R) >> 1;
        int leftNode = (node << 1) + 1;
        int rightNode = leftNode + 1;
        if(value = L)
            update(leftNode, L, mid, value);  // 更新左子树
        if(value = mid+1)
            update(rightNode, mid+1, R, value);  // 更新右子树
        treeArr[node] = treeArr[leftNode] + treeArr[rightNode];
    }

    // 查询[value, maxN]间的元素个数
    static long query(int node, int L, int R, int QL, int QR){
        if(QL > R  || L > QR)
            return 0;
        if(QL = R)  // 完全覆盖
            return treeArr[node];
        int mid = (L + R) >> 1;
        int leftNode = (node << 1) + 1;
        int rightNode = leftNode + 1;
        long result = 0;
        if(!(QL > mid))
            result += query(leftNode, L, mid, QL, QR);
        if(!(QR < mid+1))
            result += query(rightNode, mid+1, R, QL, QR);
        return result;
    }

    static int nextInt() throws IOException{
        cin.nextToken();
        return (int)cin.nval;
    }
}