{"problem":{"name":"C. Intersections","description":{"content":"In this problem, you are given two permutations a and b of n numbers, and you need to play a game with them! In this game, you are required to perform the following steps: For example, let us conside","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10185C"},"statements":[{"statement_type":"Markdown","content":"In this problem, you are given two permutations a and b of n numbers, and you need to play a game with them! In this game, you are required to perform the following steps:\n\nFor example, let us consider two permutations (5, 4, 2, 1, 3) and (2, 5, 4, 1, 3). The following picture shows the permutations after drawing all line segments. In the picture, the number of intersections between the line segments is 2.\n\nGiven the permutations a and b, your task is to play the game and to count number of intersections between the line segments. Can you?\n\nThe first line contains an integer T (1 ≤ T ≤ 100), in which T is the number of test cases.\n\nThe first line of each test case contains an integer n (1 ≤ n ≤ 105), in which n is the size of permutations. \n\nThen a line follow containing n distinct integers a1, a2, ..., an (1 ≤ ai ≤ n), giving the first permutation a. \n\nThen a line follow containing n distinct integers b1, b2, ..., bn (1 ≤ bi ≤ n), giving the second permutation b.\n\nThe sum of n overall test cases does not exceed 7 × 105.\n\nFor each test case, print a single line containing the number of intersections between the line segments.\n\n## Input\n\nThe first line contains an integer T (1 ≤ T ≤ 100), in which T is the number of test cases.The first line of each test case contains an integer n (1 ≤ n ≤ 105), in which n is the size of permutations. Then a line follow containing n distinct integers a1, a2, ..., an (1 ≤ ai ≤ n), giving the first permutation a. Then a line follow containing n distinct integers b1, b2, ..., bn (1 ≤ bi ≤ n), giving the second permutation b.The sum of n overall test cases does not exceed 7 × 105.\n\n## Output\n\nFor each test case, print a single line containing the number of intersections between the line segments.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of regions, with $ 6 \\leq n \\leq 36 $.  \nLet $ V = (v_1, v_2, \\dots, v_n) \\in \\mathbb{Z}^n $ be the target sum for each region, where $ 1 \\leq v_i \\leq 21 $.  \nLet $ R \\in \\{1, \\dots, n\\}^{6 \\times 6} $ be the region assignment matrix, where $ R[i][j] $ denotes the region index of cell $ (i,j) $.  \n\nLet $ S \\in \\{1, \\dots, 6\\}^{6 \\times 6} $ be the solution grid to be determined.\n\n**Constraints**  \n1. **Region Sum Constraint**: For each region $ k \\in \\{1, \\dots, n\\} $,  \n   $$\n   \\sum_{\\substack{(i,j) \\in \\{1,\\dots,6\\}^2 \\\\ R[i][j] = k}} S[i][j] = v_k\n   $$\n\n2. **Row Constraint**: For each row $ i \\in \\{1, \\dots, 6\\} $,  \n   $$\n   \\{ S[i][1], S[i][2], \\dots, S[i][6] \\} = \\{1, 2, 3, 4, 5, 6\\}\n   $$\n\n3. **Column Constraint**: For each column $ j \\in \\{1, \\dots, 6\\} $,  \n   $$\n   \\{ S[1][j], S[2][j], \\dots, S[6][j] \\} = \\{1, 2, 3, 4, 5, 6\\}\n   $$\n\n4. **Block Constraint**: For each of the six $ 2 \\times 3 $ disjoint blocks $ B_\\ell $ ($ \\ell \\in \\{1, \\dots, 6\\} $),  \n   $$\n   \\bigcup_{(i,j) \\in B_\\ell} \\{ S[i][j] \\} = \\{1, 2, 3, 4, 5, 6\\}\n   $$\n\n**Objective**  \nFind any grid $ S \\in \\{1, \\dots, 6\\}^{6 \\times 6} $ satisfying all constraints above.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10185C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}