XX Open Cup, Grand Prix of Tokyo D,L

本文主要是介绍XX Open Cup, Grand Prix of Tokyo D,L，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

D
二分max值为L，判定能否使用\(\leq L\)的数构造出答案。

暂时不管L的限制。此时如果我们有一组解，表示为\(c_{0},c_{1},...,c_{60}\)，其中\(c_{i}\)是有多少个数在第\(i\)位为\(1\)。那么我们可以将\(c_{i}\)减\(2\)，\(c_{i-1}\)加\(4\)；或者\(c_{i}\)减\(4\)，\(c_{i+1}\)加\(2\)，构造出所有合法解。（为什么不是\(c_{i}\)减\(1\)，\(c_{i-1}\)加\(2\)呢？因为我们不仅要让\(sum\)不变，还要让\(xor\)不变，所以加减的数必然是偶数）

那么我们如何构造\(c\)？设\(x_{i}\)为异或和\(X\)的第\(i\)位，\(s_{i}\)为和\(S\)的第\(i\)位。那么\(x_{i}=1\)意味着\(c_{i}\)为奇数，也就是\(c_{i}\geq 1\)，那么我们不妨将\(X\)减去\(S\)，此时每个数都出现了偶数次，那么我们将其除以二，我们设这样操作后的数为\(Y\)（\(Y=(S-X)/2\)），第\(i\)位为\(y_{i}\)。不难构造出\(c_{i}=2y_{i}+x_{i}\)。

L
我们对第一个限制分治，也就是，我们对\(y\)坐标从小到大排序，每次分成左右两个区间，并且记录出现在左侧的红点和出现在右侧的蓝点，那么我们就想让红点和蓝点匹配。

直接暴力匹配是\(O(n^2)\)的（当然也体现不出分治的意义），但是这里有一个结论：最大权值的匹配必然是有一个颜色的点的权值最大。也就是，只能是左侧红点中\(w\)最大的和右侧所有蓝点匹配；或者右侧蓝点\(w\)最大的和左侧红点匹配。

证明很简单——假设当前我们的询问为\([L,R]\)，当前分治的区间为\([lef,rig]\)，左半部分为\([lef,mid]\)，右半部分为\([mid+1,rig]\)。若\(L\leq lef\leq rig\leq R\)，那么区间内所有点对都满足条件\(2\)。否则若\(lef\leq L\leq mid\leq R\leq rig\)，则左侧最大值和右侧最大值会落到\([lef,L-1],[L,mid],[mid+1,R],[R+1,rig]\)这四个区间的两个中，那么根据抽屉原理，我们取\(1,4\)和\(2,3\)段时，必然会出现包含左侧最大值或右侧最大值的段。否则就是相交的情况，其实就是将四段变成三段或更少，也是满足条件的。

那么这样点对数就降到\(O(n\log n)\)。我们处理出这些点对。回答询问可以让询问离线，将询问和点对按左节点从小往大\从大往小排序，用BIT处理前缀和后缀max即可。具体实现看程序。（有点像扫描线，但这里空间有些大，开线段树很危险，只能用树状数组了）

https://codeforces.com/gym/102586/submission/168237465

这篇关于XX Open Cup, Grand Prix of Tokyo D,L的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！