$fib$ 数组存的是 $10^{18}$ 内的斐波那契数，共 $86$ 个,能过 $1\le l,r \le10^{18},T\le5\times10^4$ 的数据。

求帮忙分析一下复杂度，本蒟在此感激不尽。

#include<bits/stdc++.h>
using namespace std;

const int n=86;
long long fib[n+1],sum[n+1];
int tmp=0;
long long work(long long l,long long r)
{
    if(l>r) return 0;
    int L=lower_bound(fib+1,fib+n+1,l)-fib,R=upper_bound(fib+1,fib+n+1,r)-fib-1;
    if(L>R)
    {
        long long ret=((r-l+1)&1)?fib[R]:0;
        ret^=work(l-fib[R],r-fib[R]);
        return ret;
    }
    long long ret=sum[R]^sum[L]^fib[L];
    ret=ret^work(l,fib[L]-1)^work(fib[R]+1,r);
    return ret;
}
int main()
{
    fib[1]=1,fib[2]=2;
    for(int i=3;i<=n;++i) fib[i]=fib[i-1]+fib[i-2];
    sum[1]=1,sum[2]=3;
    for(int i=3;i<=n;++i)
    {
        sum[i]=sum[i-1]^sum[i-2]^fib[i-2]^fib[i];
        if((fib[i-2]-1)&1) sum[i]^=fib[i-1];
    }
    int T;
    cin>>T;
    long long l,r;
    while(T--)
    {
        scanf("%lld %lld",&l,&r);
        printf("%lld\n",work(l,r));
    }
    return 0;
}