P7707 "Wdsr-2.7" The Sunflower Field Where a Hundred Flowers Bloom

> Spring arrives, and the flowers bloom... But this time there are far more flowers than usual; even flowers from all seasons are blooming. $$\kern{1pt}\tag*{\small\text{——东方花映冢}}$$ This year's sunflower field has become especially lively because all kinds of flowers are blooming. Although this is an incident related to flowers, the owner of the sunflower field, Kazami Yuuka, is enjoying the colorful flower field brought by the blossoms—after all, the usually quiet field has become lively thanks to the activity of various fairies. Yuuka likes these flowers very much. Each flower has its own type, and it also represents a kind of personality. For example, sunflowers, dandelions, gaillardias... Strangely, some flowers may belong to the same type, but due to related factors (such as age, nutrition, etc.), each flower has its own height. Yuuka is very interested, because these flowers vary in height and appearance, making the sunflower field show a different kind of scenery. While in the mood, Yuuka picked some flowers and hopes you can help her solve a problem.

At the beginning, Yuuka chooses $n$ flowers in the sunflower field. Each flower has a height $h_i$ and a type $t_i$. They are arranged in a line and numbered $1,2,3\cdots n$. Yuuka has $m$ operations of two kinds: - $\colorbox{f0f0f0}{\verb!1 l r x!}$: Consider all flowers in the interval $[l,r]$. Take out all flowers whose height is not greater than $x$ (that is, flowers with $h_i\le x$), and arrange them **in order** (that is, do not change their relative order in the original sequence). Then, according to their types, they can be divided into several consecutive segments (for example, $\{\underline{1,}\ \underline{2,2},\underline{1,1},\underline {3,}\ \underline{4,4,4}\}$ can be divided into $5$ segments). Yuuka wants you to tell her how many segments there are in total. - $\colorbox{f0f0f0}{\verb!2 x y!}$: Yuuka selects one flower with height $x$ and type $y$, and appends it to the end. **Forced online.**

- The first line contains three integers $n,m,k$. The meanings of $n,m$ are as above, and $k$ is the **forced online parameter**. - The next two lines: the first line contains $n$ integers, representing $\{h_1,h_2\cdots h_n\}$; the third line contains $n$ integers, representing the sequence $\{t_1,t_2\cdots t_n\}$. Their meanings are as described above. - Then follow $m$ lines. Each line begins with an integer $op$, indicating the type of this operation. - If $op = 1$, then three integers $l',r',x'$ follow, describing one query. - If $op = 2$, then two integers $x',y'$ follow, describing one modification. - In all operations, the real $l,r,x,y$ are obtained by XOR-ing the input values $l',r',x',y'$ with $k \times last$. Here, $last$ is the answer of the last query, initially $0$.

- There are several lines. For each operation $1$, output one integer per line, which is the answer.

$n'$ denotes the length of the sequence after all operations. $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \bf{Subtask} & \bm{n',m} & \textsf{\textbf{Special Property}} & \textsf{\textbf{Score}} \cr\hline 1 & 1\le n',m \le 10^3 & \text{None} & 10 \cr\hline 2 & 1\le n',m \le 3\times 10^5 & k=0 & 20\cr\hline 3 & 1\le n',m \le 3\times 10^5 & l=1 & 25\cr\hline 4 & 1\le n',m \le 10^5 & \text{None} & 15\cr\hline 5 & 1\le n',m \le 3\times 10^5 & \text{None} & 20\cr\hline 6 & \text{No special constraints} & \text{Time limit 3s, memory limit 300MB} & 10\cr\hline \end{array}$$ - For $100\%$ of the testdata: $1 \le n',m \le 5 \times 10 ^ 5$。 $1 \le h_i,t_i,x,y \le 10^9$，$1 \le l \le r \le n'$。 $1 \le op \le 2$，$0 \le k \le 10^3$。 Hint: please pay attention to constant optimization. Translated by ChatGPT 5