自动搬运

查看原文

来自洛谷，原作者为

	zhoukangyang ^w^/

搬运于2025-08-24 22:16:38，当前版本为作者最后更新于2020-01-30 22:29:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题十分在考场上十分坑,调了$1$个多小时后结果是题目出锅了,现在说一下我的做法。

10pts

暴力,在这里不展开了。

40pts

对于一珂线段树,我们只要走最大的那条路,并得到最终节点坐标即可。具体方法如下: 假设我们走到一个节点,它的子树共有$x$个节点,它的下标为$y$, 要求的是子树上最大下标：

1. 首先如果x==1,直接返回$y$
2. 否则,如果x%2==0,返回的最大下标一定在右子树。
3. 否则,如果lowbit(x/2)==x/2 表示左子树深度深，返回的最大下标一定在左子树。
4. 否则,直接返回右子树(因为右子树相同深度下标一定比左子树大)

复杂度$O(nlogn)$ n=(r-l+1)

在这里就不开$long long$了反正也过不了

代码:

#include<bits/stdc++.h>
using namespace std;
int l,r,S,SS,ans;
int lowbit(int x) {
	return x&-x;
}
int q(int x,int y) {
	if(x==1) return y;
	if(x%2==0) return q(x/2,y*2+1);
	else if(lowbit(x/2)==x/2) return q(x/2+1,y*2);
	else return q(x/2,y*2+1);
}
int main() {
	scanf("%d%d",&l,&r);
	S=l;
	while(1) {
		SS=S;
		for(int i = 40; i >= 0; i--) {
			int QwQ=(1ll<<i);
			if(q(S,1)==q(S+QwQ,1)) S+=QwQ;
		}
		if(S>=r) {
			if((r-SS+1)%2) ans^=q(S,1);
			printf("%d",ans);
			return 0;
		}
		if((S-SS+1)%2) ans^=q(S,1);
		++S;
	}
	return 0;
}

100pts

然后我发现,有非常多的连续的$f(i)$相同,比如$f(1536)$~$f(2047)$均相同,于是就想到了倍增处理。

最终如果连续的个数为奇数那么将$ans$异或其中的$f$函数值。

代码长度短,时间复杂度很低但为$O($玄学$)$

代码：

#include<bits/stdc++.h>
using namespace std;
long long l,r,S,SS,ans;
long long lowbit(long long x) {
	return x&-x;
}
long long q(long long x,long long y) {
	if(x==(1ll)) return y;
	if(!(x&(1ll))) return q(x/(2ll),y*(2ll)+(1ll));
	else if(lowbit(x/(2ll))==x/(2ll)) return q(x/(2ll)+(1ll),y*(2ll));
	else return q(x/(2ll),y*(2ll)+(1ll));
}
int main() {
	scanf("%lld%lld",&l,&r);
	S=l;
	while(1) {
		SS=S;
		for(long long i = (40ll); i >= (0ll); i--) {
			long long QwQ=((1ll)<<i);
			if(q(S,(1ll))==q(S+QwQ,(1ll))) S+=QwQ;
		}
		if(S>=r) {
			if((r-SS+(1ll))%(2ll)) ans^=q(S,(1ll));
			printf("%lld",ans);
			return 0;
		}
		if((S-SS+(1ll))%(2ll)) ans^=q(S,(1ll));
		++S;
	}
	return 0;
}