楼兰壁画

树状数组

import java.util.*;
import java.io.*;

class Tree {
    int[] tree;
    int N;

    public Tree(int N) {
        this.N = N;
        tree = new int[N + 1];
    }

    public int lowBit(int i) {
        return i & -i;
    }

    public void add(int i, int val) {
        while (i <= N) {
            tree[i] += val;
            i += lowBit(i);
        }
    }

    public int query(int i) {
        int res = 0;
        while (i > 0) {
            res += tree[i];
            i -= lowBit(i);
        }
        return res;
    }

    public int sum(int i) {
        return query(N) - query(i);
    }
}

public class Main {
    static int N = (int) 2e5 + 10;
    static int n;
    static int[] a = new int[N];
    static int[] up = new int[N];
    static int[] down = new int[N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }

        Tree tree0 = new Tree(N);
        for (int i = 1; i <= n; i++) {
            int y = a[i];
            up[i] = tree0.sum(y); // 右边比当前元素大的数的个数
            down[i] = tree0.query(y - 1); // 左边比当前元素小的数的个数
            tree0.add(y, 1);
        }

        Arrays.fill(tree0.tree, 0); // 清空树状数组

        long res1 = 0, res2 = 0;
        for (int i = n; i >= 1; i--) {
            int y = a[i];
            res1 += up[i] * (long) tree0.sum(y); // 右边比当前元素大的数的个数乘以左边比当前元素大的数的个数
            res2 += down[i] * (long) tree0.query(y - 1); // 左边比当前元素小的数的个数乘以右边比当前元素小的数的个数
            tree0.add(y, 1);
        }

        System.out.println(res1 + " " + res2);
    }
}

一个树状数组问题

import java.io.*;
import java.util.*;
class Tree{
    long[]tree;
    int N;
    public Tree(int N){
        this.N=N;
        tree=new long[N+1];
    }
    public int lowBit(int i){
        return i&-i;
    }
    public void add(int i,int v){
        while(i<=N){
        tree[i]+=v;
        i+=lowBit(i);
        }
    }
    public long query(int i){
        long res=0;
        while(i>0){
        res+=tree[i];
        i-=lowBit(i);
        }
        return res;
    }
    public long sum(int i){
        return query(N)-query(i);
    }
}
public class Main{
    static int N=(int)1e5+10;
    static int []a=new int[N];
    static int n,m;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        Tree tree0 = new Tree(N);
        n=sc.nextInt();
        m=sc.nextInt();
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
            tree0.add(i,a[i]-a[i-1]);
        }
        for(int i=0;i<m;i++){
            String s=sc.next();
            if(s.equals("Q")){
                int x=sc.nextInt();
                System.out.println(tree0.query(x));
            }else{
                int l=sc.nextInt();
                int r=sc.nextInt();
                int d=sc.nextInt();
                tree0.add(l,d);
                tree0.add(r+1,-d);
            }
        }
    } 
}