P4477 [BJWC2018] Basic Matching Algorithm Practice

Xiao S recently learned the Hungarian algorithm for bipartite matching. Now the X part of a bipartite graph has $N$ numbers $A_i$, and the Y part has $K$ numbers $C_i$. If $A_i + C_j \le Z$, then there is an edge between $A_i$ and $C_j$. Find the maximum matching size of the bipartite graph $(X, E, Y)$. Xiao S is a beginner, so she wants to do more practice to consolidate her knowledge. She found a positive integer array $B$ of length $M$. Each time, she picks a continuous subarray $[L_i, R_i]$ from $B$, takes all numbers in $[L_i, R_i]$ as the $K$ numbers $C_i$ on the Y part of the bipartite graph, and then recomputes the maximum matching size. Xiao S plans to do $Q$ practice sessions, but she is not sure whether each computed answer is correct. Can you help her?

The first line contains three positive integers $N, M, Z$. The second line contains $N$ positive integers, where the $i$-th integer is $A_i$. The third line contains $M$ positive integers, where the $i$-th integer is $B_i$. The fourth line contains an integer $Q$ denoting the number of queries. Each of the next $Q$ lines contains two positive integers; on the $i$-th line, the two integers are $L_i, R_i$.

For each practice session, output the answer for that session.

Testdata ID|$N$|$M$|$Q$ :-:|:-:|:-:|:-: $1 \sim 4$|$\le 50$|$\le 50$|$\le 50$ $5 \sim 10$|$\le 2501$|$\le 2501$|$\le 2501$ $11 \sim 14$|$\le 152501$|$\le 45678$|$\le 45678$ $15 ,16$|$\le 152501$|$\le 50$|$\le 52501$ $17 \sim 20$|$\le 152501$|$\le 52501$|$\le 52501$ For $100\%$ of the testdata, $1 \le A_i, B_i, Z \le 10^9$, $1 \le L_i \le R_i \le M$. The testdata is graded. Translated by ChatGPT 5