题目来源

2021年蓝桥杯国赛F题

题目链接：http://acm.mangata.ltd/p/P1505

考点

前缀和、初中数学

视频讲解

视频连接：https://www.bilibili.com/video/BV1cL411w7eB/

思路

我们可以怎么考虑这个事情呢，我们会发现这个序列就是数量不断上升的一个等差数列，我们只需要预处理出每一段长度的一个和，然后我们求一个区间到[0,R]的一个和，因为我们与处理过，所以这个O(1)就能得出，然后再求一下[0,L-1]的一个区间和，那么我们相减就是我们所需要的答案了，注意的是这里的L和R不一定刚好都是完整区间，所以我们还得处理一下边角的情况，关于前缀和的知识请查看：

https://www.bilibili.com/video/BV1xq4y1y7Kz

代码实现

#include<bits/stdc++.h>
using namespace std;
//----------------自定义部分----------------
#define ll long long
#define mod 1000000009
#define endl "\n"
#define PII pair<int,int>

int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};

ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 1e7+10;
//----------------自定义部分----------------
ll n,m,q,a[N],pre[N];
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	n = 10000000;
	ll res = 0;
	for(int i = 1;i <= n; ++i) {
		ll loc = ((i+1LL)*i)/2LL;
		pre[i] = pre[i-1] + loc;
	}
	
	int t;
	cin>>t;
	ll l,r;
	while(t--){
		cin>>l>>r;
		ll ans = 0;
		//计算的是[0,R]这段区间的和
		//计算的完整区间的前缀和
		ll lenr = (sqrt(1+8.0*r)-1)/2LL;
		ans = pre[lenr];
		r -= ((lenr+1)*lenr)/2;
		//计算的是不完整的
		ans += ((r+1)*r)/2LL;
		//计算的是[0,L-1]这段区间的和
		l--;
		//计算的完整区间的前缀和
		ll lenl = (sqrt(1+8.0*l)-1)/2LL;
		ans -= pre[lenl];
		l -= (lenl+1)*lenl/2LL;
		//计算的是不完整的
		ans -= ((l+1)*l)/2LL;
		cout<<ans<<endl;
	}
	
	
	return 0;
}

import java.util.Scanner;

public class T6 {
static long loc(long p) {
double d = (Math.sqrt(1 + 8 * p) - 1) / 2;
return d==(long)d?(long)d:(long)d+1;
}

static long nsum(long i) {
//计算n*(n+1)/2这个数列的和
return (i * i * i + 3 * i * i + 2 * i)/6;
}

static long f(long from, long end) {
long sum = 0;
long locfrom = loc(from);
//计算起始位置到最近分界点的和
long n = locfrom * (locfrom + 1) / 2;
sum += (n - from + 1) * (locfrom + locfrom - (n - from))/2;
//计算分界点到距离end最近前面分界点的和

long locend = loc(end);
sum += nsum(locend-1) - nsum(locfrom);
//计算机距离end最近分界点到end的和
long ncp = locend * (locend - 1) / 2;
sum += (end - ncp) * (1 + end - ncp) / 2;
return sum;
}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);
int count = scanner.nextInt();
for (int i = 0; i < count; i++) {
long from = scanner.nextLong();
long end = scanner.nextLong();
System.out.println(f(from, end));
}
scanner.close();

}
}

打卡

#include <iostream>
using namespace std;
#define ll long long
const int N=1e7+10;
ll w[N],pre[N]; 
int main(){
	int k=1;
	for(ll i=1;i<=N;i++){
		w[i]=(1+i)*i/2;
		pre[i]=pre[i-1]+w[i];
	}
	int n;
	scanf("%d",&n);
	while(n--){
		ll l=0,r=0;
		scanf("%lld%lld",&l,&r);
		l--;
		ll R=lower_bound(w,w+N,r)-w;
		ll L=lower_bound(w,w+N,l)-w;
		ll m=w[R]-r;//相差的项数 
		ll mm=w[L]-l;//相差的项数 
		ll sum1=pre[R]-m*(R-m+1+R)/2;
		ll sum2=pre[L]-mm*(L-mm+1+L)/2;
		printf("%lld\n",sum1-sum2);
	}
	return 0;
}