下载掌阅APP，畅读海量书库
立即打开
题目描述（HDU4902）： 有 n 个数字 a 1 , a 2 , …, a n ，每次都可以将[ l , r ]区间的每个数字都更改为数字 x （类型1），或将[ l , r ]区间每个大于 x 的 a i 都更改为最大公约数gcd( a i , x )（类型2），请输出最后的序列。
输入： 第1行包含一个整数 T ，表示测试用例的数量。每个测试用例的第1行都包含整数 n 。下一行包含以空格分隔的 n 个整数 a 1 , a 2 , …, a n 。再下一行包含一个整数 Q ，表示操作数量。下面的 Q 行，每行都包含4个整数 t 、 l 、 r 、 x ， t 表示操作类型， l 、 r 表示区间左右端点。 T ≤2， n , Q ≤100000， a i , x ≥0且在int32范围内。
输出： 对每个测试用例，都单行输出以空格分隔的最终序列，在序列结束后输出一个空格。
题解： 本题是很明显的区间更新问题，但不仅仅是简单的区间更新，而是将[ l , r ]区间每个大于 x 的 a i 都更改为gcd( a i , x )。
（1）创建线段树。
（2）区间更新（类型1），将[ l , r ]区间的每个数字都更改为数字 x。
（3）区间更新（类型2），将[ l , r ]区间每个大于 x 的 a i 都更改为gcd( a i , x )。
（1）创建线段树。根据输入样例，首先输入10个数，将其存储在数组中。
由于数值较大，为了方便起见，在下图中标记的是数值对应的下标，在程序中记录的是数值自身data[ i ]。初时化时，区间最大值、懒标记等于数据自身，maxs[ i ]=lazy[ i ]=data[ i ]。
（2）1 3 6 74243042：将[3, 6]区间的值修改为 x （ x =74243042，用下标11标识）。找到[3, 3]、[4, 5]、[6, 6]区间，更新这些区间的懒标记和最大值为 x ，返回时更新最大值。
（3）2 4 8 16531729：将[4, 8]区间大于 x （ x =16531729）的值修改为两者的最大公约数。首先找到[4, 5]、[6, 8]区间。[4, 5]区间带有懒标记，因此更新该区间的懒标记和最大值：lazy[ i ]=gcd(lazy[ i ], x )=1，maxs[ i ]=lazy[ i ]=1。返回时更新最大值。[6, 8]区间没有懒标记，说明该区间的数值不同，因此继续查找左右子树，更新[6, 6]、[7, 7]、[8, 8]区间。该区间的懒标记lazy[ i ]=gcd(lazy[ i ], x )=1，最大值maxs[ i ]=lazy[ i ]=1。返回时更新最大值。
（4）1 3 4 1474833169：将[3, 4]区间的值修改为 x （ x =1474833169，用下标12标识）。找到[3, 3]、[4, 4]区间，更新这些区间的懒标记和最大值为 x ，返回时更新最大值。在查找区间的过程中因为[4, 5]区间带有懒标记，所以懒标记下传，再更新[4, 4]区间。
（5）2 1 8 1131570933：将[1, 8]区间大于 x （ x =1131570933）的值修改为两者的最大公约数。首先找到[1, 5]、[6, 8]区间。[6, 8]区间的最大值比 x 小，什么也不做。[1, 5]区间没有懒标记，说明该区间内的数值不同，因此继续查找左右子树，更新[1, 2]、[3, 3]、[4, 4]、[5, 5]区间，其中[1, 2]、[5, 5]区间的最大值比 x 小，什么也不做。只需更新[3, 3]、[4, 4]区间的懒标记和最大值：lazy[ i ]=gcd(lazy[ i ], x )=1，maxs[ i ]=lazy[ i ]=1，返回时更新最大值。
（6）2 7 9 1505795335：将[7, 9]区间大于 x （ x =1505795335）的值修改为两者的最大公约数。首先找到[7, 7]、[8, 8]、[9, 9]区间，这3个区间的最大值比 x 小，什么也不做。
（7）2 3 7 101929267：将[3, 7]区间大于 x （ x =101929267）的值修改为两者的最大公约数。首先找到[3, 3]、[4, 5]、[6, 7]区间，这3个区间的最大值比 x 小，什么也不做。
（8）1 4 10 1624379149：将[4, 10]区间的值修改为 x （ x =1624379149，用下标13标识）。找到[4, 5]、[6, 10]区间，更新这些区间的懒标记和最大值为 x ，返回时更新最大值。
（9）2 2 8 2110010672：将[2, 8]区间大于 x （ x =2110010672）的值修改为两者的最大公约数。首先找到[1, 10]区间，该区间的最大值比 x 小，什么也不做。
（10）2 6 7 156091745：将[6, 7]区间大于 x （ x =156091745）的值修改为两者的最大公约数。首先找到[6, 7]区间，在查找过程中经过的[6, 10]区间带有懒标记，懒标记下传，一直找到[6, 7]区间，该区间带有懒标记，因此更新该区间的懒标记和最大值：lazy[ i ]=gcd(lazy[ i ], x )=1，maxs[ i ]=lazy[ i ]=1，返回时更新最大值。
（11）1 2 5 937186357：将[2, 5]区间的值修改为 x （ x =937186357，用下标14标识）。找到[2, 2]、[3, 3]、[4, 5]区间，更新这些区间的懒标记和最大值为 x ，返回时更新最大值。
（12）输出结果。因为节点可能带有懒标记，因此在查找叶子的过程中懒标记下传，然后输出叶子即可。上图中[4, 5]、[6, 7]、[9, 10]区间带有懒标记，懒标记下传后如下图所示。
所有叶子节点的数据为1、937186357、937186357、937186357、937186357、1、1、1624379149、1624379149、1624379149。
（1）区间更新（类型1）。将[ l , r ]区间的每个数字都更改为数字 x ，找到区间后更新最大值为 x 。在查找过程中下传懒标记，返回时更新最大值。
（2）区间更新（类型2）。将[ l , r ]区间每个大于 x 的 a i 都更改为gcd( a i , x )。若该区间的最大值小于或等于 x ，则什么也不做，因此在操作过程中可记录区间最大值，提高效率。若懒标记不为0，且待更新区间覆盖当前节点区间，则lazy[ i ]=gcd(lazy[ i ], x )，maxs[ i ]=lazy[ i ]，返回。懒标记下传，更新左右子树，返回时更新最大值。
算法代码：
