Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class Main implements Runnable {
- private void solution() throws IOException {
- while (true) {
- int n = in.nextInt();
- if (n == 0) {
- break;
- }
- int[] p1 = new int[n];
- int[] p2 = new int[n];
- int[] p3 = new int[n];
- for (int i = 0; i < n; ++i) {
- p1[i] = in.nextInt() - 1;
- }
- for (int i = 0; i < n; ++i) {
- p2[i] = in.nextInt() - 1;
- }
- for (int i = 0; i < n; ++i) {
- p3[i] = in.nextInt() - 1;
- }
- int[] q = new int[n];
- for (int i = 0; i < n; ++i) {
- q[p1[i]] = i;
- }
- int[] a = new int[n];
- int[] b = new int[n];
- for (int i = 0; i < n; ++i) {
- a[i] = q[p2[i]];
- b[i] = q[p3[i]];
- }
- out.println(f(a, b));
- }
- }
- static class Tree {
- static class Node {
- int key;
- int prior;
- int count;
- Node left;
- Node right;
- public Node(int key, int prior) {
- this.key = key;
- this.prior = prior;
- this.left = new Node();
- this.right = new Node();
- }
- public Node() {
- }
- public boolean isNull() {
- return left == null;
- }
- public void setNull() {
- left = right = null;
- }
- public void take(Node other) {
- key = other.key;
- left =other.left;
- right = other.right;
- count = other.count;
- prior = other.prior;
- }
- }
- Random rm = new Random(31);
- Node head = new Node();
- public void add(int key) {
- add(head, new Node(key, rm.nextInt()));
- }
- private void add(Node head, Node node) {
- if (head.isNull()) {
- head.take(node);
- } else if (head.prior >= node.prior) {
- add(node.key < head.key ? head.left : head.right, node);
- } else {
- split(head, node.left, node.right, node.key);
- head.take(node);
- }
- update(head);
- }
- private void split(Node head, Node left, Node right, int key) {
- if (head.isNull()) {
- left.setNull();
- right.setNull();
- } else if (key < head.key) {
- right.take(head);
- split(right.left, left, right.left, key);
- } else {
- left.take(head);
- split(left.right, left.right, right, key);
- }
- update(left);
- update(right);
- }
- private void update(Node head) {
- if (!head.isNull()) {
- head.count = 1 + count(head.left) + count(head.right);
- }
- }
- private int count(Node head) {
- if (head.isNull()) {
- return 0;
- } else {
- return head.count;
- }
- }
- public int lower(int value) {
- return lower(head, value);
- }
- private int lower(Node head, int value) {
- if (!head.isNull()) {
- if (value < head.key) {
- return lower(head.left, value);
- } else if (value == head.key) {
- return 1 + count(head.left);
- } else {
- return 1 + count(head.left) + lower(head.right, value);
- }
- } else {
- return 0;
- }
- }
- }
- private long f(int[] a, int[] b) {
- int[] where = new int[b.length + 1];
- for (int i = 0 ; i < b.length; ++i) {
- where[b[i]] = i;
- }
- int size = Integer.highestOneBit(b.length) * 2;
- Tree[] tree = new Tree[2 * size];
- for (int i = 0; i < 2 * size; ++i) {
- tree[i] = new Tree();
- }
- long res = 0;
- for (int i = 0; i < a.length; ++i) {
- res += count(0, where[a[i]] - 1, tree, a[i]);
- add(tree, where[a[i]], a[i]);
- }
- return res;
- }
- private void add(Tree[] tree, int i, int value) {
- i += tree.length >> 1;
- while (i > 0) {
- tree[i].add(value);
- i >>= 1;
- }
- }
- private int count(int i, int j, Tree[] tree, int value) {
- int res = 0;
- i += tree.length >> 1;
- j += tree.length >> 1;
- while (i <= j) {
- if ((i & 1) != 0) {
- res += count(tree[i++], value);
- }
- if ((j & 1) == 0) {
- res += count(tree[j--], value);
- }
- i >>= 1;
- j >>= 1;
- }
- return res;
- }
- private int count(Tree tree, int value) {
- return tree.lower(value);
- }
- public void run() {
- try {
- solution();
- in.reader.close();
- out.close();
- } catch (IOException e) {
- e.printStackTrace();
- System.exit(1);
- }
- }
- public static void main(String[] args) {
- new Thread(null, new Main(), "", 1 << 28).start();
- }
- private class Scanner {
- BufferedReader reader;
- StringTokenizer tokenizer;
- public Scanner(Reader reader) {
- this.reader = new BufferedReader(reader);
- this.tokenizer = new StringTokenizer("");
- }
- public String nextLine() throws IOException {
- tokenizer = new StringTokenizer("");
- return reader.readLine();
- }
- public boolean hasNext() throws IOException {
- while (!tokenizer.hasMoreTokens()) {
- String line = reader.readLine();
- if (line == null) {
- return false;
- }
- tokenizer = new StringTokenizer(line);
- }
- return true;
- }
- public String next() throws IOException {
- hasNext();
- return tokenizer.nextToken();
- }
- public int nextInt() throws IOException {
- return Integer.parseInt(next());
- }
- }
- Scanner in = new Scanner(new InputStreamReader(System.in));
- PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement