
0 点赞 评论 收藏
分享
狗傻:我说下O(NlogN)的做法. 先按照b[i]排序 考虑b[I]=k[I]*m+r[I] , 其中0<=r[I]<m 答案 其中对于固定的i,可以利用后缀和计算; 因此关键在于求 事实上,对于每对,我们考虑:如果,那么;否则. 因此还是对于固定的i,我们需要计算有多少个j,满足:j>i 且。这一步可以用离散化+树状数组解决。 最后的时间复杂度是O(NlogN+N*(1+1+logN))=O(NlogN)
0 点赞 评论 收藏
分享
创作者周榜
更多
关注他的用户也关注了: