如何提高网站的访问速度必应搜索引擎入口

蓝桥杯题型分类

二分

123

传送门

1. 小区间的构成

假设数列的构成是如下形式：

• 第 1 个区间包含 1 个元素（1）。
• 第 2 个区间包含 2 个元素（1 2）。
• 第 3 个区间包含 3 个元素（1 2 3）。
• 第 4 个区间包含 4 个元素（1 2 3 4）。
• …

第 i 个小区间包含 i 个元素。我们将这些小区间连起来形成整个数列。

2. 数组 a[j] 的定义

数组 a[j] 表示前 j 个小区间的总元素数，同时也能表示每个小区间的和。例如：

• a[1] = 1 （表示前 1 个小区间有 1 个元素）
• a[2] = 1 + 2 = 3 （表示前 2 个小区间共有 3 个元素）
• a[3] = 1 + 2 + 3 = 6 （表示前 3 个小区间共有 6 个元素）
• a[4] = 1 + 2 + 3 + 4 = 10 （表示前 4 个小区间共有 10 个元素）

注意，数组 a[j] 是单调递增的，因为每个小区间的元素个数都在增加。

关键点：k = i - a[j]

• 数列中的位置 i 是在第 j+1 个区间中的某个元素。
• 前 j 个区间包含了 a[j] 个元素，也就是说，第 j+1 个区间的第一个元素出现在位置 a[j] + 1。

因此，位置 i 在第 j+1 个区间的具体位置是：

• 第 j+1 个区间的第 k 个元素：k 就是位置 i 相对于第 j+1 个区间开始位置的偏移量。

由于前 j 个区间包含了 a[j] 个元素，第 j+1 个区间从位置 a[j] + 1 开始。所以位置 i 在第 j+1 个区间中的具体位置是：

k = i - a[j]

#include <iostream>
using namespace std;
using ll=long long;
const int N=1414215;ll a[N],s[N];ll persum(ll i)
{ll l=0,r=N;while(l<r){ll mid=(l+r+1)>>1;if(a[mid]<i)l=mid;else r=mid-1;}return  s[l]+a[i-a[l]];
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);for(int i=1;i<N;i++){a[i]=a[i-1]+i;s[i]=s[i-1]+a[i];}int t;cin>>t;while(t--){ll l,r;cin>>l>>r;cout<<persum(r)-persum(l-1)<<endl;}return 0;
}