2371. [HDU4902]数据结构难题

【题目描述】

给定一个由$n$个数构成的序列$a$，共有$q$次操作：

1 l r x，将区间$[l,r]$内的每个数修改为$x$；

2 l r x，将区间$[l,r]$内的每个大于$x$的数都改为$\gcd(x,a_i)$。

【输入格式】

第一行一个整数$T(T\leq 2)$，表示测试数据组数。

对于每组测试数据，第一行一个整数$n(n\leq 10^5)$，表示序列的长度。

接下来一行$n$个整数，表示原始的序列($a_i\geq 0$)。

接下来一行一个整数$q(q\leq 10^5)$，表示操作的个数。

接下来$n$行，每行一个操作，具体格式见题目描述$(x\geq 0)$。

输入保证$a_i,x$不超过int范围。

【输出格式】

对于每组测试数据，输出一行$n$个用空格隔开的整数，表示最终序列。

【样例输入】

1
10
16807 282475249 1622650073 984943658 1144108930 470211272 101027544 1457850878 1458777923 2007237709 
10
1 3 6 74243042
2 4 8 16531729
1 3 4 1474833169
2 1 8 1131570933
2 7 9 1505795335
2 3 7 101929267
1 4 10 1624379149
2 2 8 2110010672
2 6 7 156091745
1 2 5 937186357

【样例输出】

16807 937186357 937186357 937186357 937186357 1 1 1624379149 1624379149 1624379149