当前位置：首页 > article >正文

蓝桥杯题型

article 2025/3/8 13:08:07

蓝桥杯题型分类

二分

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;
}