【2019 Multi-University 9 K】Rikka with Segment Tree 题解

题目大意

  规定线段树上 $[l,r]$ 这个区间往下分会分到 $[l,\lfloor \frac{l+r}2 \rfloor]$、$[\lfloor \frac{l+r}2 \rfloor+1,r]$，直到区间长度为 $1$ 为止。
  设 $f(i,n)$ 为 $[i,i]$ 这个区间在有 $n$ 个叶子的线段树上的深度（根节点深度为 $1$），求：

$$\sum_{n=L}^R \sum_{i=1}^n f(i,n) \times i$$

  $L,R \leq 5 \times 10^{17}$

题解

  设 $f_n$ 表示有 $n$ 个叶子的线段树的叶子深度和，$g_n$ 表示 叶子深度乘叶子 id 的和，$h_n$ 表示 叶子深度乘 $n$ 的和，设 $F_n$、$G_n$、$H_n$ 分别为它们的前缀和。

  答案就是 $G_R-G_{L-1}$，$F$ 和 $H$ 算是辅助函数。

  考虑怎么递推求 $F_n$，这里一共是 $n$ 棵线段树，每一棵都分一半，分成这样：

$$\begin{aligned} [1,1]&:~~[1,1] \\ [1,2]&:~~[1,1]+[2,2] \\ [1,3]&:~~[1,2]+[3,3] \\ [1,4]&:~~[1,2]+[3,4] \\ [1,5]&:~~[1,3]+[4,5] \\ [1,6]&:~~[1,3]+[4,6] \\ [1,7]&:~~[1,4]+[5,7] \\ &\vdots \end{aligned}$$

  这是 $n$ 为奇数的情况，可以发现，左边分为了两组前缀和：$F_{\lfloor \frac n2 \rfloor}$ 和 $F_{\lceil \frac n2 \rceil}$（偶数下标对应第一组，奇数下标对应第二组，每一组的区间长度恰好是 $1,2,3,\cdots$，所以是分成两组前缀和），右边也分为了两组前缀和：都是 $F_{\lfloor \frac n2 \rfloor}$（偶数下标对应第一组，奇数下标对应第二组）。
  然后还要考虑左右子树拼起来之后，除第一棵树外所有叶子的深度都加了 $1$，因此 $n$ 棵树增加的深度和就是 $2+3+\cdots+n=\frac{n(n+1)}{2}-1$。
  因此 $n$ 为奇数时的 $F$ 的递推式出来了：

$$F_n=3 \cdot F_{\lfloor \frac n2 \rfloor}+F_{\lceil \frac n2 \rceil}+\frac{n(n+1)}{2}-1~~~~~~,n~is~odd$$

  $n$ 为偶数是类似的，左边分成的两组都是 $F_{\frac n2}$，右边的两组分别为 $F_{\frac n2}$ 和 $F_{\frac n2 -1}$：

$$F_n=3 \cdot F_{\frac n2}+F_{\frac n2 -1}+\frac{n(n+1)}{2}-1~~~~~~,n~is~even$$

  接下来推 $H_n$，也是同样的思路，左边右边各分成两组。以 $n$ 为奇数时左边两组为例，因为 $h_i=\sum deep_x \cdot i$，先考虑把 $i$ 变对，那么其中一组是要把 $i$ 变成 $2i-1$，另一组要把 $i$ 变成 $2i$，因此对应的分别是 $2H_{\lceil \frac n2 \rceil}-F_{\lceil \frac n2 \rceil}$ 和 $2H_{\lfloor \frac n2 \rfloor}$。
  然后考虑左右子树拼起来后增加的深度的贡献，区间长度为 $i$ 的树有 $i$ 个叶子，每个叶子贡献增加 $i$，那么是 $2^2+3^2+4^2+\cdots+n^2=\frac{n(n+1)(2n+1)}6-1$。
  因此递推式为：

$$H_n=(2H_{\lceil \frac n2 \rceil}-F_{\lceil \frac n2 \rceil})+(2H_{\lfloor \frac n2 \rfloor})+(2H_{\lfloor \frac n2 \rfloor}+F_{\lfloor \frac n2 \rfloor})+(2H_{\lfloor \frac n2 \rfloor})+\frac{n(n+1)(2n+1)}6-1~~~~~~,n~is~odd \\$$

  偶数就不写了。

  接下来推 $G_N$，还是一样的，要考虑的就是右子树的起始下标被左子树抬上去了，所以这部分是用 $H$ 函数来做贡献：

$$G_n=G_{\lceil \frac n2 \rceil}+G_{\lfloor \frac n2 \rfloor}+(G_{\lfloor \frac n2 \rfloor}+H_{\lfloor \frac n2 \rfloor})+(G_{\lfloor \frac n2 \rfloor}+H_{\lfloor \frac n2 \rfloor}+F_{\lfloor \frac n2 \rfloor})+\sum_{i=2}^n \frac{i(i+1)}{2}~~~~~~,n~is~odd$$

  偶数就不写了。

  最后来分析时间复杂度，$n$ 为奇数时递归到 $\lceil \frac n2 \rceil$ 和 $\lfloor \frac n2 \rfloor$，$n$ 为偶数时递归到 $\frac n2$ 和 $\frac n2 -1$，可以观察到，每往下走一层都是一段连续的区间，比如 $n=32$，往下走到 $15$ 和 $16$，再往下走到 $7,8,9$，再往下走到 $3,4,5$……
  因为同一层相邻的两个数，往下走是会交的，因此每一层最多比上一层多一个数，因此总量是 $O(\log^2 n)$ 的。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;

const LL mo=998244353;

LL L,R,inv2,inv6;

LL mi(LL x,LL y)
{
	LL re=1;
	for(; y; y>>=1, x=x*x%mo) if (y&1) re=re*x%mo;
	return re;
}

map<LL,LL> f,g,h; // f = sum of deep,  g = sum of deep*id,  h = sum of deep*n
LL sum(LL n) // 1+2+3+..+n
{
	n%=mo;
	return n*(n+1)%mo*inv2%mo;
}
LL sum2(LL n) // 1+4+9+...+n^2
{
	n%=mo;
	return n*(n+1)%mo*(2*n+1)%mo*inv6%mo;
}
LL sums(LL n) // 1+3+6+10+...+n(n+1)/2
{
	return (sum2(n)+sum(n))%mo*inv2%mo;
}
void dfs(LL n)
{
	if (f.count(n)) return;
	if (n<=1)
	{
		f[n]=g[n]=h[n]=n;
		return;
	}
	if (n&1)
	{
		LL l=(n+1)>>1, r=n>>1;
		dfs(l), dfs(r);
		f[n]=(f[l]+f[r]*3+sum(n)-1+mo)%mo;
		g[n]=(g[l]+g[r]+(g[r]+h[r])+(g[r]+h[r]+f[r])+mo+sums(n)-1+mo)%mo;
		h[n]=(h[l]*2-f[l]+h[r]*2+h[r]*2+f[r]+h[r]*2+sum2(n)-1+mo)%mo;
	} else
	{
		LL l=n>>1, r=l-1;
		dfs(l), dfs(r);
		f[n]=(f[l]*3+f[r]+sum(n)-1+mo)%mo;
		g[n]=(g[l]*2+(g[l]+h[l])+(g[r]+h[r]+f[r])+mo+sums(n)-1+mo)%mo;
		h[n]=(h[l]*2-f[l]+h[l]*2+h[l]*2+h[r]*2+f[r]+sum2(n)-1+mo)%mo;
	}
}

LL calc(LL n)
{
	dfs(n);
	return g[n];
}

int T;
int main()
{
	inv2=mi(2,mo-2);
	inv6=mi(6,mo-2);
	
	scanf("%d",&T);
	while (T--)
	{
		scanf("%lld %lld",&L,&R);
		
		printf("%lld\n",(calc(R)-calc(L-1)+mo*2)%mo);
	}
}