zcmimi's blog
查看原题

点击跳转

40%的log n做法挺容易的,就是一直往右儿子走,走到叶子就往左走,一直重复即可

100%的做法:

首先可以把f(l)\bigoplus\dots\bigoplus f(r)变成

[f(1)\bigoplus f(2)\bigoplus\dots\bigoplus f(r)]\bigoplus[f(1)\bigoplus f(2)\bigoplus\dots\bigoplus f(l-1)]

显然f(2^k)=f(2^k+1)=2^{k+1}-1

接着可以发现\forall k,1\le t\le 2^k-1,f(2^k+2t)=f(2^k+2t+1)

因为最下一层没有填满整一层,只填满了根节点的左子树,根节点的右子树并没有发生变化

剩下的f(n)就需要考虑一下了

首先算出树的深度(根节点深度为0)

左边: 即使没占满也全算

右边: f(n/2)

#include<bits/stdc++.h>
typedef long long ll;
bool chk(ll n){return !(n&(n-1));}
ll f(ll n,int d){
    if(chk(n)||chk(n-1))return (n<<1)-1;
    return f(n>>1,d-1)+(1ll<<d);
}
ll f(ll n){return f(n,log2(n-1)+1);}
#include<bits/extc++.h>
ll g(ll n){
    if(!n)return 0;
    ll res=0;
    __gnu_pbds::gp_hash_table<ll,bool>b;
    for(ll i=1;i<=n;i<<=1){
        if(!b[i])b[i]=1,res^=f(i);
        if(i<n&&!b[i+1])b[i+1]=1,res^=f(i+1);
    }
    if(n&1^1&&!b[n])res^=f(n);
    return res;
}
int main(){
    ll l,r;
    scanf("%lld%lld",&l,&r);
    printf("%lld\n",g(r)^g(l-1));
}
LG 6025 线段树
comment评论
Search
search