#P1411. 集体会议

集体会议

集体会议

时间限制:2 s

空间限制:256 MiB

题目描述

现有 nn 人构成的集体,一开始第 ii 人持有的观点为 aia_i

接下来有 qq 个事件发生,每个事件是以下两种之一:

  • 集体会议事件:给定 l,rl,r,第 l,l+1,,rl,l+1,\cdots,r 人进行集体会议,设 xxal,al+1,,ara_l,a_{l+1},\cdots,a_r 的众数(若有多个数出现次数一致,取最早出现的数,例如 a3,a4,,a7={1,3,4,4,3}a_3,a_4,\cdots,a_7=\{1, 3, 4, 4, 3\},则 a3,a4,,a7a_3,a_4,\cdots,a_7 的众数为 33),即 xx 是这些人中的主流观点,持有该观点的人数最多。会议后,参与会议的所有人的观点更改为 xx
  • 观点改变事件:给定 idx,xidx,x,第 idxidx 人经过思考后,改变其观点为 xx

qq 个事件完全发生后,请给出每个人持有的观点。

输入格式

第一行两个整数 n,qn,q,表示集体的人数和事件的数量。

第二行 nn 个整数 a1,a2,ana_1,a_2,\cdots a_n,表示一开始每个人的观点。

接下来 qq 行每行 33 个整数。其中第一个整数为事件种类 opop,然后:

  • op=1op=1,接下来跟着两个整数 l,rl,r,表示一次集体会议事件。
  • op=2op=2,接下来跟着两个整数 idx,xidx,x,表示一次观点改变事件。

输出格式

一行 nn 个整数,表示所有事件完全发生后,每个人持有的观点。

样例输入1

5 4
1 3 2 1 2
1 3 5
1 1 2
1 1 4
2 3 2

样例输出1

1 1 2 1 2

样例1解释

第一次事件后:[1 3 2 2 2]

第二次事件后:[1 1 2 2 2]

第三次事件后:[1 1 1 1 2]

第四次事件后:[1 1 2 1 2]

数据范围与约定

对于 50%50\% 的数据,1n,q30001\le n,q\le 3000

对于 100%100\% 的数据,$1\le n,q\le 5\times 10^5, 1\le l\le r \le n,1\le idx,x,a_i\le n$