icontofig | 发布于 2019-09-08 00:15:37 | 阅读量 331 | 树状数组 偏序
发布于 2019-09-08 00:15:37 | 树状数组 偏序
The Preliminary Contest for ICPC Asia Xuzhou 2019 I.query 树状数组 二维偏序
题目大意给定一个1---n的排列和m次询问,每次询问区间 [l,r]之间min(pi,pj) = gcd(pi,pj)的数对的个数。 题解一开始看到是数对问题还以为是莫队,不过话说回来莫队WA了而不是T是怎么回事…… 首先我们需要注意min(pi,pj) = gcd(pi,pj)可以转化为pi和pj互为因数和倍数的关系(这样可以做一点常数上面的优化,也更好判断总体的数对的个数)。 然后我们要知道,所有的数对个数大概是O(nlogn)级别的。 于是我们可以枚举每个数的倍数预处理出所有的数对的位置对(i,j),我们尽量让i比j大,这有利于下面的思路。 然后有没有发现这个位置对很像是二维平面上的坐标
继续阅读