P3657 [USACO17FEB] Why Did the Cow Cross the Road II P

This problem shares the same statement as the problem with the same name in the Gold division ([金组同名题目](/problem/P6119)); the only difference lies in the constraints.

Farmer John raises $N$ breeds of cows, numbered from $1$ to $N$. Some breeds get along well with others; it turns out that if two breeds are numbered $a, b$, then when $|a - b| \leq 4$, these two breeds can get along, otherwise they cannot. A long road runs through the farm. There are $N$ pastures on the left side of the road (each occupied by exactly one breed), and $N$ pastures on the right side of the road (each occupied by exactly one breed). To help the cows safely cross the road, Farmer John wants to paint some crosswalks (cow-walks?) on the road, subject to the following conditions: 1. Each crosswalk connects a pasture on the left to a pasture on the right. 2. The breeds of the two connected pastures must get along. 3. No two crosswalks may intersect in the middle of the road. 4. Each pasture can be connected to at most one crosswalk. You need to help FJ determine the maximum possible number of crosswalks.

The first line contains an integer $N$ ($1 \leq N \leq 10^5$). The next $N$ lines each contain an integer $a_i$, representing the breed in the $i$-th pasture on the left side of the road. The next $N$ lines each contain an integer $b_i$, representing the breed in the $i$-th pasture on the right side of the road.

Output the maximum number of crosswalks.

It is guaranteed that both $a_i$ and $b_i$ are permutations of $1$ to $N$. Translated by ChatGPT 5