codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1676H2.md (2046B)


      1 Source: https://codeforces.com/problemset/problem/1676/H2
      2 
      3 H2. Maximum Crossings (Hard Version)
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 The only difference between the two versions is that in this version $n \leq 2 \cdot 10^5$ and the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     22 
     23 A terminal is a row of $n$ equal segments numbered $1$ to $n$ in order. There are two terminals, one above the other.
     24 
     25 You are given an array $a$ of length $n$. For all $i = 1, 2, \dots, n$, there should be a straight wire from some point on segment $i$ of the top terminal to some point on segment $a_i$ of the bottom terminal. You can't select the endpoints of a segment. For example, the following pictures show two possible wirings if $n=7$ and $a=[4,1,4,6,7,7,5]$.
     26 
     27  ![](https://espresso.codeforces.com/106861ba6bbf2f527977f2f200aebab49cae6da6.png) 
     28 
     29 A crossing occurs when two wires share a point in common. In the picture above, crossings are circled in red.
     30 
     31 What is the maximum number of crossings there can be if you place the wires optimally?
     32 
     33 Input
     34 
     35 The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.
     36 
     37 The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of the array.
     38 
     39 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq n$) — the elements of the array.
     40 
     41 The sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, output a single integer — the maximum number of crossings there can be if you place the wires optimally.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 4
     53 
     54 7
     55 
     56 4 1 4 6 7 7 5
     57 
     58 2
     59 
     60 2 1
     61 
     62 1
     63 
     64 1
     65 
     66 3
     67 
     68 2 2 2
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 6
     75 1
     76 0
     77 3
     78 ```
     79 
     80 Note
     81 
     82 The first test case is shown in the second picture in the statement.
     83 
     84 In the second test case, the only wiring possible has the two wires cross, so the answer is $1$.
     85 
     86 In the third test case, the only wiring possible has one wire, so the answer is $0$.