Segment Tree Code

 

void update(int node, int start, int end, int index, int val) {

    if (index <start || index > end) return;

    if (start == end) {

        tree[node] = val; return;

    }

    update(tree, node * 2, start, (start + end) / 2, index, val);

    update(tree, node * 2 + 1, (start + end) / 2 + 1, end, index, val);

    tree[node] = tree[node * 2] + tree[node * 2 + 1];

}

 

int query(int node, int start, int end, int i, int j) {

    if (j<start || i>end) return 0;

    if (i <= start && end <= j) return tree[node];

    return query(tree, node * 2, start, (start + end) / 2, i, j) + query(tree, node * 2 + 1, (start + end) / 2 + 1, end, i, j);

}

 

 

int[] Tree = new int[N*2];

static void update(int x) {
		x = x + Size - 1;
		while(x > 1) {
			Tree[x] += 1;
			x /= 2;
		}
	}
	
	static int sum(int x, int y, int l, int r, int node) {
		int mid = (l+r)/2;
		if(x > r || y < l) return 0;
		if(x <= l && y >= r) return Tree[node];
		else return sum(x, y, l, mid, node*2) + sum(x, y, mid+1, r, node*2+1);
	}

 

적용 코드

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static int N, Size;
	static long Answer;
	static BufferedReader br;
	static StringTokenizer st;
	static int [] A;
	static int [] B;
	static int [] Tree;

	public static void main(String[] args) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		A = new int[1000001];
		st = new StringTokenizer(br.readLine());
		for(int input = 1; input <= N; input++) {
			A[Integer.parseInt(st.nextToken())] = input; 
		}
		Size = 1;
		while(Size < 1000001) {
			Size *= 2;
		}
		B = new int[1000001];
		Tree = new int[Size*2];
		int idxA;
		st = new StringTokenizer(br.readLine());
		for(int input = 1; input <= N; input++) {
			 B[input] = A[Integer.parseInt(st.nextToken())];
		}
		for(int i = 1; i <= N; i++) {
			int tmp = B[i];
			Answer += sum(tmp, N, 1, Size, 1);
			update(tmp);
		}
		System.out.println(Answer);
	}
	
	static void update(int x) {
		x = x + Size - 1;
		while(x > 1) {
			Tree[x] += 1;
			x /= 2;
		}
	}
	
	static int sum(int x, int y, int l, int r, int node) {
		int mid = (l+r)/2;
		if(x > r || y < l) return 0;
		if(x <= l && y >= r) return Tree[node];
		else return sum(x, y, l, mid, node*2) + sum(x, y, mid+1, r, node*2+1);
	}

}