题解 | 数组单调和

class MonoSum {
private:
    static const int MAXN = 505;
    int tree[MAXN];
    int count[MAXN];
    
    int lowbit(int x) {
        return x & (-x);
    }
    
    void update(int pos, int val, int n) {
        while (pos <= n) {
            tree[pos] += val;
            count[pos]++;
            pos += lowbit(pos);
        }
    }
    
    pair<int,int> query(int pos) {
        int sum = 0, cnt = 0;
        while (pos > 0) {
            sum += tree[pos];
            cnt += count[pos];
            pos -= lowbit(pos);
        }
        return {sum, cnt};
    }
    
public:
    int calcMonoSum(vector<int>& A, int n) {
        // 离散化
        vector<int> sorted = A;
        sort(sorted.begin(), sorted.end());
        sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
        
        memset(tree, 0, sizeof(tree));
        memset(count, 0, sizeof(count));
        
        int result = 0;
        for (int i = 0; i < n; i++) {
            int pos = lower_bound(sorted.begin(), sorted.end(), A[i]) - sorted.begin() + 1;
            auto [sum, cnt] = query(pos);
            if (cnt > 0) {
                result += sum;
            }
            update(pos, A[i], sorted.size());
        }
        
        return result;
    }
};

import java.util.*;

public class MonoSum {
    private static final int MAXN = 505;
    private int[] tree;
    private int[] count;
    
    private int lowbit(int x) {
        return x & (-x);
    }
    
    private void update(int pos, int val, int n) {
        while (pos <= n) {
            tree[pos] += val;
            count[pos]++;
            pos += lowbit(pos);
        }
    }
    
    private int[] query(int pos) {
        int sum = 0, cnt = 0;
        while (pos > 0) {
            sum += tree[pos];
            cnt += count[pos];
            pos -= lowbit(pos);
        }
        return new int[]{sum, cnt};
    }
    
    public int calcMonoSum(int[] A, int n) {
        tree = new int[MAXN];
        count = new int[MAXN];
        
        // 离散化
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            set.add(A[i]);
        }
        
        ArrayList<Integer> sorted = new ArrayList<>(set);
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            int pos = Collections.binarySearch(sorted, A[i]) + 1;
            int[] query = query(pos);
            if (query[1] > 0) {
                result += query[0];
            }
            update(pos, A[i], sorted.size());
        }
        
        return result;
    }
}

class MonoSum:
    def __init__(self):
        self.MAXN = 505
        self.tree = [0] * self.MAXN
        self.count = [0] * self.MAXN
        
    def lowbit(self, x):
        return x & (-x)
        
    def update(self, pos, val, n):
        while pos <= n:
            self.tree[pos] += val
            self.count[pos] += 1
            pos += self.lowbit(pos)
            
    def query(self, pos):
        sum_val = cnt = 0
        while pos > 0:
            sum_val += self.tree[pos]
            cnt += self.count[pos]
            pos -= self.lowbit(pos)
        return sum_val, cnt
        
    def calcMonoSum(self, A, n):
        sorted_nums = sorted(list(set(A)))
        num_map = {num: i+1 for i, num in enumerate(sorted_nums)}
        
        result = 0
        self.tree = [0] * self.MAXN
        self.count = [0] * self.MAXN
        
        for i in range(n):
            pos = num_map[A[i]]
            sum_val, cnt = self.query(pos)
            if cnt > 0:
                result += sum_val
            self.update(pos, A[i], len(sorted_nums))
            
        return result