蓝桥杯题型分类
二分
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;
}
