这是我第二次做这道题了，还是没做出来，真是惭愧。。
题意：长度n的序列, m个询问区间[L, R], 问区间内的所有子段的不同GCD值有多少种.
题解：考虑固定左端点的不同GCD值，只有不超过logA种, 所以事件点只有nlogA个. 那么离线处理, 按照区间右端点排序从小到大处理询问, 用一个树状数组维护每个GCD值的最大左端点位置即可. 复杂度是O(nlogAlogn).
最后
以上就是如意樱桃最近收集整理的关于hdu5869——Different GCD Subarray Query（思考+树状数组）的全部内容，更多相关hdu5869——Different内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复