P7577 "PMOI-3" Simple Simulation Problem

You are given a sequence $s$ of length $n$. There are $q$ queries. Each query is in the form `a b c d e f`, and you need to compute the value of the following expression: $$\sum_{L=a}^{b}[e\le G(F(L,c),F(L,c+1),\cdots,F(L,d))\le f]$$ Here, $F(l,r)$ denotes the number of distinct values in the subarray $[l,r]$ of sequence $s$, and $G(x_1,x_2,\cdots,x_k)$ denotes the number of distinct values among $x_1,x_2,\cdots,x_k$.

The first line contains two integers $n,q$, representing the length of the sequence and the number of queries. The second line contains $n$ integers, where the $i$-th integer represents $s_i$. The next $q$ lines each contain $6$ integers $a',b',c',d',e,f$. Let the answer to the previous query be $\text{lastans}$ (in particular, if this is the first query, then $\text{lastans}=0$). Then in this query: $a=(a'+\text{lastans})\bmod n+1\\$ $b=(b'+\text{lastans})\bmod n+1\\$ $c=(c'+\text{lastans})\bmod n+1\\$ $d=(d'+\text{lastans})\bmod n+1\\$ **Note that you need to reorder $a,b,c,d$ so that $a\le b\le c\le d$.**

For each query, output the answer in order.

[Sample 1 Explanation] In the first query, $a=1,b=1,c=3,d=3,e=1,f=1$. It is easy to get $G(F(1,3))=1$, and $e\le G(F(1,3))\le f$, so the answer is $1$. [Sample 2 Explanation] | Query ID | $a$ | $b$ | $c$ | $d$ | $e$ | $f$ | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | ① | 3 | 4 | 5 | 6 | 1 | 2 | | ② | 2 | 5 | 8 | 10 | 2 | 4 | | ③ | 3 | 6 | 6 | 8 | 1 | 3 | [Constraints] **This problem uses bundled testdata.** - Subtask 1 (10 pts): $n,q\le500$, $1\le s_i\le10^6$. - Subtask 2 (15 pts): $n,q\le3\times10^3$. - Subtask 3 (20 pts): $b-a\le20$. - Subtask 4 (25 pts): $n,q\le10^5$. - Subtask 5 (30 pts): no special constraints. For $100\%$ of the testdata, $1\le n,q\le3\times10^5$, $0\le|s_i|\le10^9$. For all queries, $1\le a,b,c,d\le n$, $0\le e\le f\le n$. [Hint] 1. In this problem, $[x \le y \le z]$ indicates whether $y$ is $\in[x,z]$. If it is in this interval, the value is $1$; otherwise it is $0$. 2. The input size is large, so please use a faster input method. Translated by ChatGPT 5