9719: Interval LRU

Little Q is learning about a page replacement algorithm in operating systems memory management~-- the LRU (Least Recently Used) algorithm.

To help Little Q understand this algorithm, you need to answer some questions regarding LRU in this problem. First, we briefly introduce the principle of this algorithm:

• Set up a cache container of capacity $k$ to store loaded pages and related information. Initially, no pages are in the container.
• The system will sequentially process requests to access pages, handling one request at a time.
• For accessing a page that is already in the cache (i.e., a cache hit), use the cache directly as the data source and update the page's most recent access time.
• For accessing a page that is not in the cache (i.e., a cache miss), if the number of pages in the cache has reached $k$, first evict a page from the cache to ensure the number of pages in the cache is less than $k$, and then load the accessed page from its real address into the cache, using the cache as the data source and updating the page's most recent access time.
• Whenever a page needs to be evicted, choose the one with the earliest most recent access time to release from the cache.

Next, we use pages numbered from $1$ to $n$ and provide an array of length $n$, [a1,a2,…,an][a_1, a_2, \ldots, a_n][a1,a2,…,an], along with $q$ queries, and you are asked to answer these queries. Each query is one of the following two types:

• 1 l r k1\ l\ r\ k1 l r k: Access the pages numbered al,al+1,…,ara_l, a_{l + 1}, \ldots, a_ral,al+1,…,ar in order, using an LRU cache with a maximum capacity of $k$, and report the number of cache hits.
• 2 l r k2\ l\ r\ k2 l r k: Access the pages numbered al,al+1,…,ara_l, a_{l + 1}, \ldots, a_ral,al+1,…,ar in order, using an LRU cache, requiring that the number of cache hits is at least $k$, and report the minimum required LRU capacity. If the goal of cache hits cannot be achieved, regard the capacity as $-1$.

The first line contains an integer $T$ (1<=T<=10⁵), indicating the number of test cases.
Then follow $T$ test cases. For each test case:
The first line contains two integers $n$ and $q$ (1<=n,q<=10⁵).
The second line contains $n$ integers a1,a2,…,ana_1, a_2, \ldots, a_na1,a2,…,an (1≤ai≤n1 \leq a_i \leq n1≤ai≤n).
The next $q$ lines describe the queries, each line of which contains four integers t,l,r,kt, l, r, kt,l,r,k (t∈{1,2},1≤l≤r≤n,1≤k≤r−l+1t \in \{1, 2\}, 1 \leq l \leq r \leq n, 1 \leq k \leq r - l + 1t∈{1,2},1≤l≤r≤n,1≤k≤r−l+1), representing a query of the $t$-th type (parameters' meaning are described above).
It is guaranteed that the sum of $n$ and the sum of $q$ over $T$ test cases do not exceed 2*10⁵ and 2*10⁵ respectively.

For each test case, output $q$ lines, the $i$-th line of which contains an integer, representing the answer to the $i$-th query.