蓝桥杯2021年第十二届国赛真题-123（二分+前缀和）

解题思路

对于1，2，3，4，5，6，…, n
我们用数组s_n表示前n项和，使用数组sum_n表示数组s前n项和;
初始化：

void init() {
    for (int i = 1; i < N; i++) {
        s[i] = s[i - 1] + i;
        sum[i] = sum[i - 1] + s[i];
    }
}

每次查询 l 和 r 时，使用二分查找大于s_i的最小下标fl和fr;
二分查找：

ll find(ll x) {
    ll l = 1, r = N - 5;
    ll mid;
    while (l <= r) {
        mid = l + ((r - l) >> 1);
        if (s[mid] >= x) r = mid - 1;
        else l = mid + 1;
    }
    return l;
}

如上图所示：那么区间l到r的值即为：
sum[fr] - sum[fl - 1] - s[l - 1 - s[fl - 1]] - s[fr] + s[r - s[fr - 1]]

完整代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 15e5 + 5;
ll s[N];
ll sum[N];
void init() {
    for (int i = 1; i < N; i++) {
        s[i] = s[i - 1] + i;
        sum[i] = sum[i - 1] + s[i];
    }
}
ll find(ll x) {
    ll l = 1, r = N - 5;
    ll mid;
    while (l <= r) {
        mid = l + ((r - l) >> 1);
        if (s[mid] >= x) r = mid - 1;
        else l = mid + 1;
    }
    return l;
}
ll t, l, r;
int main() {
    init();
    scanf("%lld", &t);
    while (t--) {
        scanf("%lld%lld", &l, &r);
        int fl = find(l);
        int fr = find(r);
        ll ans = sum[fr] - sum[fl - 1] - s[l - 1 - s[fl - 1]] - s[fr] + s[r - s[fr - 1]];
        printf("%lld\n", ans);
    }
    return 0;
}