G题 - 栈与公约数
讲道理，这题 q 的数据量达到了 2e5 ，朴素做法为啥没被卡 ？
在 q 足够大 且 op = 4 的操作数量足够多的时候时间复杂度可以达到 O(n^2) 的吧？
我写的线段树，看了一下大家写的都是朴素做法，而且跑的飞快。
2022-10-23 19:18 已编辑 蚌埠坦克学院 C++ 发布于河南
关注
全部评论
着魔之人
大连理工大学 后端
实际朴素算法优化一下就是 On的 第四个操作 处理k的数据，可以pop前 k个数据，然后将一个数据入栈，标记这个数据占k个，下次再做第四个操作的时候，这k个就可以直接处理，每个数据入栈和出栈，只要处理一次就行，最后运行时间44ms。嘎嘎快
相关推荐
点赞 评论 收藏
分享