P10550 [THUPC 2024 Finals] Trade

The school where Little Z lives is like a chain: very long in diameter and very narrow in width. More specifically, there is a sequence of length $n$. Each position has an attribute $a_i\in \{0/1\}$ and a type $c_i$. Some trading events will happen here. Little Z moves through the sequence from left to right. If Little Z encounters a node with attribute $0$, then Little Z may buy at most one item of type $c_i$. If Little Z encounters a node with attribute $1$, then Little Z may sell at most one item of type $c_i$. Obviously, Little Z cannot sell an item of a type that Little Z does not have. A legal transaction is defined as buying at some node and selling at some node. Note that you must ensure that, in the end, Little Z has nothing left in hand. There are $q$ queries. In each query, Little Z walks in order from $l_i$ to $r_i$. Ask: what is the maximum number of legal transactions?

The first line contains two positive integers $n,q$. The next line contains $n$ numbers, where the $i$-th one denotes $a_i$. The next line contains $n$ numbers, where the $i$-th one denotes $c_i$. The next $q$ lines each contain two numbers denoting $l_i,r_i$.

Output $q$ lines in total, each line containing one number denoting the maximum number of legal transactions in the current query.

For all testdata, it holds that $1\le n,q\le5\times 10^5,1\le c_i\le n,1\le l_i\le r_i\le n,a_i\in\{0,1\}$. Please pay attention to input/output efficiency. **Source and Acknowledgements** From the finals of THUPC2024 (Tsinghua University Student Programming Contest 2024 and Collegiate Invitational). Thanks to THUSAA for providing the problem. For data, statement, reference solution, editorial, etc., please refer to the official THUPC repository . Translated by ChatGPT 5