本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-09 18:15:31

思路：

先考虑连续偶数的和：

$ \begin{matrix} \sum_{i=1}^{n} 2i \ =2\sum_{i=1}^{n}i \ =2\frac{n(n+1)}{2}\ =n(n+1) \end{matrix} $。

然后是奇数的和：

$\begin{matrix} \sum_{i=0}^{n} 2i+1 \ =(2\sum_{i=0}^{n-1}i)+n \ =2\frac{n(n-1)}{2}+n\ =n(n-1)+n\ =n^2 \end{matrix}$

于是可以求出进行 $k$ 轮的和。

那么对于一个 $n$ 求第 $1,2 \dots n$ 所有数的和可以考虑先求出最大的 $k$ 使得 $2^k-1 \le n$。

那么对于进行了 $k$ 轮后没算的数字可以考虑 $k$ 的奇偶，然后算出要添加的种类的数的总个数，用总个数的贡献减去已有的贡献即可。

然后对于 $[l,r]$ 这段区间可以拆分成 $[1,r] - [1,l-1]$，然后按照上面说的做即可。

由于中途怕爆 long long，所以用了 __int128。

Code：

#include <bits\/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

ll l, r;
array<ll, 3> s[70];

ll power(ll a, ll b) {
	ll res = 1;

	for (; b; b >>= 1, a = a * a % mod)
		if (b & 1) res = res * a % mod;

	return res;
}

ll solve(ll n) {
	if (!n) return 0;

	ll k = 1;
	while ((1ll << (k + 1)) - 1 <= n)
		++k;

	\/\/ cout << n << ' ' << k << endl;
	ll ans = s[k][0];
	if (k & 1) {
		ll even = s[k][2], cnt = n - s[k][1];
		ans = (__int128)ans + (__int128)cnt * (cnt + 1) % mod - (__int128)even * (even + 1) % mod;
		ans = (ans + mod) % mod;
	} else {
		ll odd = s[k][1], cnt = n - s[k][2];
		\/\/ cout << odd << ' ' << cnt <<  ' ' << n << endl;
		ans = ((__int128)ans + (__int128)cnt * (cnt - 1) % mod - (__int128)odd * (odd - 1) % mod + cnt - odd) % mod;
		ans = (ans + mod) % mod;
	}

	return ans;
}

int main() {
	ll odd = 0, even = 0;
	for (ll i = 1; i <= 60; ++i) {
		if (i & 1) odd += (1ll << (i - 1ll));
		else even += (1ll << (i - 1ll));

		s[i] = {((__int128)even * ((__int128)even + 1) % mod + (__int128)odd * ((__int128)odd - 1) % mod + (__int128)odd % mod) % mod, odd, even};
\/\/		cout << s[i][0] << ' ' << i << endl;
	}

	scanf("%lld%lld", &l, &r);

	\/\/ cout << solve(r) << ' ' << solve(l - 1) << endl;

	printf("%lld\n", (solve(r) - solve(l - 1) + mod) % mod);

	return 0;
}