大佬博客
题意可以从上面的博客中看题解也完全可以
思路就是定义3个函数F , G , H F,G,HF,G,H
他们都是关于长度为1 到 n 1到n1到n的线段树的某种答案的和。
然后思考一下线段树分成两个线段树的过程，就可以递归计算答案了。
所以这个题的算法就是递归普及减难度对不起要熟练运用STL使用map，所以应该是提高减
#include<bits/stdc++.h>#definemod 998244353#defineLL long longusingnamespacestd;map<LL,int>f,g,h;intinv6=(mod+1)/6;intsolve(LL n){if(f.count(n))returng[n];if(n<=1)returnf[n]=g[n]=h[n]=n;if(n&1){LL u=n/2,v=n-n/2;solve(u),solve(v);intfu=f[u],fv=f[v],hu=h[u],hv=h[v],gu=g[u],gv=g[v];f[n]=(3ll*fu+fv+1ll*(n%mod)*(n%mod+1)/2-1)%mod;h[n]=(6ll*hu+2ll*hv+fu-fv+1ll*(n%mod)*(n%mod+1)%mod*(2ll*n%mod+1)%mod*inv6%mod-1)%mod;g[n]=(3ll*gu+gv+2ll*hu+fu+1ll*(n%mod)*(n%mod+1)%mod*(n%mod+2)%mod*inv6%mod-1)%mod;}else{LL u=n/2,v=u-1;solve(u),solve(v);intfu=f[u],fv=f[v],hu=h[u],hv=h[v],gu=g[u],gv=g[v];f[n]=(3ll*fu+fv+1ll*(n%mod)*(n%mod+1)/2-1)%mod;h[n]=(6ll*hu+2ll*hv-fu+fv+1ll*(n%mod)*(n%mod+1)%mod*(2ll*n%mod+1)%mod*inv6%mod-1)%mod;g[n]=(3ll*gu+gv+hu+hv+fv+1ll*(n%mod)*(n%mod+1)%mod*(n%mod+2)%mod*inv6%mod-1)%mod;}returng[n];}intmain(){intT;for(scanf("%d",&T);T--;){LL a,b;scanf("%lld%lld",&a,&b);printf("%d\n",((solve(b)-solve(a-1))%mod+mod)%mod);}}
