我是靠谱客的博主 如意樱桃，最近开发中收集的这篇文章主要介绍hdu5869——Different GCD Subarray Query（思考+树状数组），觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
这是我第二次做这道题了，还是没做出来，真是惭愧。。
题意：长度n的序列, m个询问区间[L, R], 问区间内的所有子段的不同GCD值有多少种.
题解：考虑固定左端点的不同GCD值，只有不超过logA种, 所以事件点只有nlogA个. 那么离线处理, 按照区间右端点排序从小到大处理询问, 用一个树状数组维护每个GCD值的最大左端点位置即可. 复杂度是O(nlogAlogn).
最后
以上就是如意樱桃为你收集整理的hdu5869——Different GCD Subarray Query（思考+树状数组）的全部内容，希望文章能够帮你解决hdu5869——Different GCD Subarray Query（思考+树状数组）所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复