5953: 进阶2.4.3 数据结构难题
内存限制：128 MB
时间限制：4.000 S
评测方式：文本比较
命题人：
提交：76
解决：18
题目描述
有n个数字a1,a2,……,an，你可以进行两种操作：
1.将区间[l,r]间的每个数字都改为x
2.将区间[l,r]间的每个大于x的数字ai都改为最大公约数gcd(ai,x)
请输出操作后的序列
1.将区间[l,r]间的每个数字都改为x
2.将区间[l,r]间的每个大于x的数字ai都改为最大公约数gcd(ai,x)
请输出操作后的序列
输入
第一行T表示测试数量 T<=2
每个测试样例的第一行为n，表示数组元素个数 n<=1e5
接下来一行有n个数字，表示a1 a2 …… an ai>0且在int32范围内
下一行为Q，表示操作数量 Q<=1e5
下面Q行，每行是个整数 t l r x，t表示操作类型，l r表示区间左右端点 x>0且在int32范围内
每个测试样例的第一行为n，表示数组元素个数 n<=1e5
接下来一行有n个数字，表示a1 a2 …… an ai>0且在int32范围内
下一行为Q，表示操作数量 Q<=1e5
下面Q行，每行是个整数 t l r x，t表示操作类型，l r表示区间左右端点 x>0且在int32范围内
输出
输出以空格分割的最终序列
样例输入 复制
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