hdu 4777 Rabbit Kingdom (树状数组+预处理)

Posted by 111qqz on Wednesday, November 8, 2017

TOC

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从1到n扫一遍,i代表的意义是左边界。

  1. 当扫到第i个数时,我们统计左边界为i+1的问题(这样范围一定满足左边界,因为右边界接下来也进行了处理,所以可以直接统计)。

  2.  我们还需要更新第i个数。i的意义是左边界,因为之后统计的问题左边界都大于i,都满足。所以我们找到所有左边界为i的数,将其+1处理。然后右边界-1处理。这样如果问题的边界大于右边界的话,这个数就不会统计在内。

  3.  最后处理完i后,因为以后问题的左边界都大于i,所以第i个数不会再被统计了,所以我们要除去第i个数的影响,就是把其右边界+1(自身为什么不处理,因为处不处理都一样,不会在涉及到它本身了)

转载又一段题解:

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付