1007. 小乖的在益起

题目描述

小乖最近喜欢喝在益起乳酸菌饮料。

在益起有 $k$ 种口味，分别记为 $0,1,\ldots,k-1$。每一瓶饮料还有一个编号 $a_i$，表示它属于哪一批特别口味。

小乖觉得，一个区间里的饮料是“均衡”的，当且仅当对于每一种编号 $x$，$k$ 种口味的出现次数都完全相同。

也就是说，对所有编号 $x$，均需要满足

其中 $cnt_{x,c}$ 表示当前区间内编号为 $x$、口味为 $c$ 的饮料数量。现在小乖会不断更换某个位置的饮料，也会询问某个区间是否均衡。请你帮她回答所有询问。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。 对于每个测试用例：

第一行包含三个整数 $n,q,k$，分别表示序列长度、操作次数和口味数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每个位置的编号。

第三行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$，表示每个位置的口味。

接下来 $q$ 行，每行表示一次操作，格式为以下两种之一：

1 p x c

表示把第 $p$ 个位置改成编号为 $x$、口味为 $c$ 的饮料。

2 l r

询问区间 $[l,r]$ 是否均衡。

对于所有数据，有：$1\le \sum n, \sum q\le 2\cdot 10^6$，$1\le a_i,x\le 10^9$，$0\le c_i,c<k,$，$1\le l\le r\le n$，$1\le k,p \le n$

输出格式

对于每次查询操作2，输出一行。如果区间 $[l,r]$ 均衡，输出：

YES

否则输出：

NO

样例输入

1
9 6 3
1 1 1 2 2 2 3 3 3
0 1 2 0 1 2 0 1 2
2 1 9
2 2 4
1 9 1 0
2 1 9
1 1 3 2
2 1 9

样例输出

YES
NO
NO
YES

来源：2026杭电多校-测试专用（杭电第1场-内测） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1237&pid=1007