尧图网页设计 
ATabc478感觉这次 abc 不算太难就是 T3 假了一遍有点浪费时间T5 拓扑没学做不出来话说这次 T4 为啥没考搜索我记得之前好几次都是。T1 Grapes简单。全部分完的共⌊ n m ⌋ \lfloor \frac{ n }{ m } \rfloor⌊mn⌋次最后一次中1 11到n m o d m n \mod mnmodm的人分到直接套公式就行。T2 Topping有点像背包 DP但只用选3 33个直接搜索就行完全不担心会 T。T3 Sort Subarray就是问只排序一段长度为k kk的区间能否让a aa升序。转换一下就是排完序后在所有和原来不一样的位置中(就是原来有哪些位置需要排)最左边的和最右边的组成的区间长度是否大于k kk因为只能排一段所以必须包含所有需要排序的位置。T4 Range Set Insertion Query名字真是越来越长了…离线对于每一个x xx分开求。对于每一个x xx把x xx所有要改的区间按左端点排序这样我们只用往右更新设r m a x r_{max}rmax为已经改过的区间中最大的左端点那么对于当前区间只有3 33中选择r n o w ≤ r m a x r_{now} \leq r_{max}rnow≤rmax显然这个区间已经被修改过了因为左端点使有序的不用考虑往左加。l n o w r m a x l_{now} r_{max}lnowrmax显然这个区间没有任何一部分被覆盖把区间内每个元素修改就行。l n o w ≤ r m a x l_{now} \leq r_{max}lnow≤rmax且r n o w r m a x r_{now} r_{max}rnowrmax此时对于区间[ l n o w , r n o w ] [l_{now}, r_{now}][lnow,rnow][ l n o w , r m a x ] [l_{now}, r_{max}][lnow,rmax]被覆盖( r m a x , r n o w ] (r_{max}, r_{now}](rmax,rnow]没有覆盖那么把区间二的元素都修改就行。注意到是区间修改用线段树维护即可。 ATabc478T1~4 题解
ATabc478感觉这次 abc 不算太难就是 T3 假了一遍有点浪费时间T5 拓扑没学做不出来话说这次 T4 为啥没考搜索我记得之前好几次都是。T1 Grapes简单。全部分完的共⌊ n m ⌋ \lfloor \frac{ n }{ m } \rfloor⌊mn⌋次最后一次中1 11到n m o d m n \mod mnmodm的人分到直接套公式就行。T2 Topping有点像背包 DP但只用选3 33个直接搜索就行完全不担心会 T。T3 Sort Subarray就是问只排序一段长度为k kk的区间能否让a aa升序。转换一下就是排完序后在所有和原来不一样的位置中(就是原来有哪些位置需要排)最左边的和最右边的组成的区间长度是否大于k kk因为只能排一段所以必须包含所有需要排序的位置。T4 Range Set Insertion Query名字真是越来越长了…离线对于每一个x xx分开求。对于每一个x xx把x xx所有要改的区间按左端点排序这样我们只用往右更新设r m a x r_{max}rmax为已经改过的区间中最大的左端点那么对于当前区间只有3 33中选择r n o w ≤ r m a x r_{now} \leq r_{max}rnow≤rmax显然这个区间已经被修改过了因为左端点使有序的不用考虑往左加。l n o w r m a x l_{now} r_{max}lnowrmax显然这个区间没有任何一部分被覆盖把区间内每个元素修改就行。l n o w ≤ r m a x l_{now} \leq r_{max}lnow≤rmax且r n o w r m a x r_{now} r_{max}rnowrmax此时对于区间[ l n o w , r n o w ] [l_{now}, r_{now}][lnow,rnow][ l n o w , r m a x ] [l_{now}, r_{max}][lnow,rmax]被覆盖( r m a x , r n o w ] (r_{max}, r_{now}](rmax,rnow]没有覆盖那么把区间二的元素都修改就行。注意到是区间修改用线段树维护即可。