当前位置：首页 > news >正文

线段树题解

news 2026/3/27 5:33:01

P6025 线段树

ZKY解题思路

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

10pts
暴力,在这里不展开了。
40pts

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

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

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

在这里就不开longlong了反正也过不了

代码:

#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)均相同,于是就想到了倍增处理。

最终如果连续的个数为奇数那么将an**s异或其中的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;
}