树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.util.*;
public class ttree {
    static int n,s;
    static int []a;
    static long res=0;
    static List<Integer>[]g;
    static int[]tr;
    static void modify(int i,int val) {
        while(i<=n) {
            tr[i]+=val;
            i+=i&-i;
        }
    }
    static int query(int i) {
        int sum=0;
        while(i>0) {
            sum+=tr[i];
            i-=i&-i;
        }
        return sum;
    }
    static int sum(int i) {
        return query(n)-query(i);
    }
    static void dfs(int u,int fa) {
        modify(a[u],1);
        for(int v:g[u]) {
            if(v!=fa) {
                dfs(v,u);
            }
        }
        for(int k=2;k*a[u]<=n;k++) {
            int t=k*a[u];
            res-=query(t)-query(t-1);
        }
        res+=sum(a[u]);
        modify(a[u], -1);
    }
//  static void dfs(int u, int p) {
//      int before = t0.query(a[u] - 1); // 进入 u 前，<a[u] 的节点数
//      t0.add(a[u], 1); // 记录 u
//      for (int v : g[u]) {
//          if (v != p) {
//              dfs(v, u); // 递归处理子节点
//          }
//      }
//      int after = t0.query(a[u] - 1); // 当前 <a[u] 的节点数（包括子树）
//      res += (after - before); // 新增的 <a[u] 的节点（即 u 的子节点中满足条件的）
//      t0.add(a[u], -1); // 回溯
//  }
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        n=scan.nextInt();
        s=scan.nextInt();
        a=new int[n+1];
        g=new ArrayList[n+1];
        tr=new int[n+1];
        Arrays.fill(tr,0);
        for(int i=1;i<=n;i++) {
            a[i]=scan.nextInt();
            g[i]=new ArrayList<>();
        }
        for(int i=0;i<n-1;i++) {
            int u=scan.nextInt();
            int v=scan.nextInt();
            g[u].add(v);
            g[v].add(u);
        }
        dfs(s,-1);
        System.out.println(res);
    }
}

楼兰壁画

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
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);
    }
}

一个树状数组问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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);
            }
        }
    } 
}