Advertisement
Guest User

Untitled

a guest
Jun 28th, 2017
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.02 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Main implements Runnable {
  5. private void solution() throws IOException {
  6. while (true) {
  7. int n = in.nextInt();
  8. if (n == 0) {
  9. break;
  10. }
  11. int[] p1 = new int[n];
  12. int[] p2 = new int[n];
  13. int[] p3 = new int[n];
  14. for (int i = 0; i < n; ++i) {
  15. p1[i] = in.nextInt() - 1;
  16. }
  17. for (int i = 0; i < n; ++i) {
  18. p2[i] = in.nextInt() - 1;
  19. }
  20. for (int i = 0; i < n; ++i) {
  21. p3[i] = in.nextInt() - 1;
  22. }
  23. int[] q = new int[n];
  24. for (int i = 0; i < n; ++i) {
  25. q[p1[i]] = i;
  26. }
  27. int[] a = new int[n];
  28. int[] b = new int[n];
  29. for (int i = 0; i < n; ++i) {
  30. a[i] = q[p2[i]];
  31. b[i] = q[p3[i]];
  32. }
  33. out.println(f(a, b));
  34. }
  35. }
  36. static class Tree {
  37. static class Node {
  38. int key;
  39. int prior;
  40. int count;
  41. Node left;
  42. Node right;
  43.  
  44. public Node(int key, int prior) {
  45. this.key = key;
  46. this.prior = prior;
  47. this.left = new Node();
  48. this.right = new Node();
  49. }
  50.  
  51. public Node() {
  52.  
  53. }
  54.  
  55. public boolean isNull() {
  56. return left == null;
  57. }
  58.  
  59. public void setNull() {
  60. left = right = null;
  61. }
  62. public void take(Node other) {
  63. key = other.key;
  64. left =other.left;
  65. right = other.right;
  66. count = other.count;
  67. prior = other.prior;
  68. }
  69. }
  70. Random rm = new Random(31);
  71. Node head = new Node();
  72.  
  73. public void add(int key) {
  74. add(head, new Node(key, rm.nextInt()));
  75. }
  76.  
  77. private void add(Node head, Node node) {
  78. if (head.isNull()) {
  79. head.take(node);
  80. } else if (head.prior >= node.prior) {
  81. add(node.key < head.key ? head.left : head.right, node);
  82. } else {
  83. split(head, node.left, node.right, node.key);
  84. head.take(node);
  85. }
  86. update(head);
  87.  
  88. }
  89.  
  90. private void split(Node head, Node left, Node right, int key) {
  91. if (head.isNull()) {
  92. left.setNull();
  93. right.setNull();
  94. } else if (key < head.key) {
  95. right.take(head);
  96. split(right.left, left, right.left, key);
  97. } else {
  98. left.take(head);
  99. split(left.right, left.right, right, key);
  100. }
  101. update(left);
  102. update(right);
  103. }
  104.  
  105. private void update(Node head) {
  106. if (!head.isNull()) {
  107. head.count = 1 + count(head.left) + count(head.right);
  108. }
  109.  
  110. }
  111.  
  112. private int count(Node head) {
  113. if (head.isNull()) {
  114. return 0;
  115. } else {
  116. return head.count;
  117. }
  118. }
  119.  
  120. public int lower(int value) {
  121. return lower(head, value);
  122. }
  123.  
  124. private int lower(Node head, int value) {
  125. if (!head.isNull()) {
  126. if (value < head.key) {
  127. return lower(head.left, value);
  128. } else if (value == head.key) {
  129. return 1 + count(head.left);
  130. } else {
  131. return 1 + count(head.left) + lower(head.right, value);
  132. }
  133. } else {
  134. return 0;
  135. }
  136. }
  137. }
  138.  
  139. private long f(int[] a, int[] b) {
  140. int[] where = new int[b.length + 1];
  141. for (int i = 0 ; i < b.length; ++i) {
  142. where[b[i]] = i;
  143. }
  144.  
  145. int size = Integer.highestOneBit(b.length) * 2;
  146. Tree[] tree = new Tree[2 * size];
  147. for (int i = 0; i < 2 * size; ++i) {
  148. tree[i] = new Tree();
  149. }
  150. long res = 0;
  151. for (int i = 0; i < a.length; ++i) {
  152. res += count(0, where[a[i]] - 1, tree, a[i]);
  153. add(tree, where[a[i]], a[i]);
  154. }
  155. return res;
  156. }
  157.  
  158. private void add(Tree[] tree, int i, int value) {
  159. i += tree.length >> 1;
  160. while (i > 0) {
  161. tree[i].add(value);
  162. i >>= 1;
  163. }
  164. }
  165.  
  166. private int count(int i, int j, Tree[] tree, int value) {
  167. int res = 0;
  168. i += tree.length >> 1;
  169. j += tree.length >> 1;
  170. while (i <= j) {
  171. if ((i & 1) != 0) {
  172. res += count(tree[i++], value);
  173. }
  174. if ((j & 1) == 0) {
  175. res += count(tree[j--], value);
  176. }
  177. i >>= 1;
  178. j >>= 1;
  179. }
  180. return res;
  181. }
  182.  
  183. private int count(Tree tree, int value) {
  184. return tree.lower(value);
  185. }
  186.  
  187. public void run() {
  188. try {
  189. solution();
  190. in.reader.close();
  191. out.close();
  192. } catch (IOException e) {
  193. e.printStackTrace();
  194. System.exit(1);
  195. }
  196. }
  197.  
  198. public static void main(String[] args) {
  199. new Thread(null, new Main(), "", 1 << 28).start();
  200. }
  201.  
  202. private class Scanner {
  203. BufferedReader reader;
  204. StringTokenizer tokenizer;
  205.  
  206. public Scanner(Reader reader) {
  207. this.reader = new BufferedReader(reader);
  208. this.tokenizer = new StringTokenizer("");
  209. }
  210.  
  211. public String nextLine() throws IOException {
  212. tokenizer = new StringTokenizer("");
  213. return reader.readLine();
  214. }
  215.  
  216. public boolean hasNext() throws IOException {
  217. while (!tokenizer.hasMoreTokens()) {
  218. String line = reader.readLine();
  219. if (line == null) {
  220. return false;
  221. }
  222. tokenizer = new StringTokenizer(line);
  223. }
  224. return true;
  225. }
  226.  
  227. public String next() throws IOException {
  228. hasNext();
  229. return tokenizer.nextToken();
  230. }
  231.  
  232. public int nextInt() throws IOException {
  233. return Integer.parseInt(next());
  234. }
  235. }
  236.  
  237. Scanner in = new Scanner(new InputStreamReader(System.in));
  238. PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
  239. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement