https://vjudge.net/problem/47450/origin
题意：#
有一个含有n个数的序列，m个询问。问 [l, r] 区间内与所有数都互质的数有几个？
思路：#
想到了预处理每个数最左最右的，最远的互质的数的范围。。
之后对于询问区间[l,r]，我们要知道 对于 i>=L && i <= R 并且 a[i].l<=L，a[i].r>=R的i的个数…
没有想到怎么维护,gg
转载一段题解：
先算出每个数的有效范围，l[i]，r[i]代表与第i个数一直互质到的最左端和最右端。这个处理方法是，预处理出一张因子表。然后对每个输入的数，判断其因子出现的最接近它的位置。从左到右扫一遍求出l[i]，从右到左扫一遍求出r[i]；我们还需要用一个vector记录下左边界为i时的所有数。
我们思考一个范围内，当一个数的l[i]和r[i]都在范围之外时，这个数会被统计在内。反过来讲就是一个范围在一个数的边界之内，当前的数会被统计到范围之内。
我们先对问题进行离线处理，先根据问题的左边界排序。我们需要维护一个树状数组来统计和增减值。
然后我们按照i从1到n扫一遍，i代表的意义是左边界。
当扫到第i个数时，我们统计左边界为i+1的问题(这样范围一定满足左边界，因为右边界接下来也进行了处理，所以可以直接统计）。
我们还需要更新第i个数。i的意义是左边界，因为之后统计的问题左边界都大于i，都满足。所以我们找到所有左边界为i的数，将其+1处理。然后右边界-1处理。这样如果问题的边界大于右边界的话，这个数就不会统计在内。
最后处理完i后，因为以后问题的左边界都大于i，所以第i个数不会再被统计了，所以我们要除去第i个数的影响，就是把其右边界+1（自身为什么不处理，因为处不处理都一样，不会在涉及到它本身了）
转载又一段题解：
先预处理出来每个数的贡献区间，每个数的贡献区间是 [左边最近不互质数的位置，右边最近不互质数的位置] ，现在问题就转化为了求区间 [L, R] 中有几个数的贡献区间能完整覆盖 [L, R] 区间。但是数据范围挺大的，可以考虑用树状数组离线处理来达到优化的目的。先对所有的查询进行排序 (按照L升序排列) ，然后从左到右依次处理。我们用树状数组区间和sum [L, R] 表示区间[L, R]中符合题意的有多少个数。假设现在需要查询 [L, R] 区间，我们可以考虑贡献区间L[i]<L的数，可以在i位置加 1，然后在R[i]位置减1。这样处理的话必须要保证L[i]小于查询区间L的值，以及i要在查询区间内。所以我们每次向后移动的时候，要在树状数组中减去当前位置的数对树状数组的影响，也就是进行操作 i 位置减1，R[i]位置加1. 分析到这里这个题目就变成了一个比较水的利用树状数组进行点更新，区间查询的题目了，也可以用线段树搞的。