[数据结构与算法]第十二届蓝桥杯国赛123（AC：二分）

题目描述

小蓝发现了一个有趣的数列，这个数列的前几项如下：

1, 1, 2, 1, 2, 3, 1, 2, 3, 4?

小蓝发现，这个数列前?1?项是整数?1，接下来?2?项是整数?1?至?2，接下来?3?项是整数?1?至?3，接下来?4?项是整数?1?至 4，依次类推。

小蓝想知道，这个数列中，连续一段的和是多少。

输入描述

输入的第一行包含一个整数?T，表示询问的个数。

接下来?T?行，每行包含一组询问，其中第?ii?行包含两个整数 li??和?ri?，表示询问数列中第?li??个数到第?ri??个数的和。

输出描述

输出?T?行，每行包含一个整数表示对应询问的答案。

输入输出样例

示例

输入

3
1 1
1 3
5 8

输出

1
4
8

评测用例规模与约定

对于?10% 的评测用例，1≤T≤30,1≤li?≤ri?≤100。

对于?20% 的评测用例，1≤T≤100,1≤li?≤ri?≤1000。

对于?40% 的评测用例，1≤T≤1000,1≤li?≤ri?≤10^6。

对于?70% 的评测用例，1≤T≤10000,1≤li?≤ri?≤10^9。

对于?80% 的评测用例，1≤T≤1000,1≤li?≤ri?≤10^12。

对于?90% 的评测用例，1≤T≤10000,1≤li?≤ri?≤10^12。

对于所有评测用例，1≤T≤100000,1≤li?≤ri?≤10^12。

运行限制

• 最大运行时间：5s
• 最大运行内存: 256M

思路分析:先二分查找l和r分别会出现在什么位置，然后计算l-r之间的数据sum，但是，由于数据量过大，for循环求和（for(ll i=l+2;i<=r;i++) sum+=(i*(i+1)/2);）必定超时，这是需要预备一个知识，我们发现

1? ?=? 1

1，2? ?=? 3

1，2，3? ?=? ?6

1，2，3，4? ?=? ?10

1，2，3，4，5? =? 15

......

1,3,6,10,15......数列的通项公式n*(n+1)/2,故前n项和为n(n+1)(n+2)/6;

AC代码：

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
//#define rep(i,a,b) for(int i=a;i<=b;i++)
//#define rep2(i,a,b) for(int i=a;i>=b;i--)
///* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
typedef pair<int,int>PII;
const int Max=1e5+5;
const ll INF=1e15+5;

ll Power(ll base, ll power) {
	ll result = 1;
	while (power > 0) {
		if (power % 2 == 1) {
			result = result * base;
		}
		power = power / 2;
		base = (base * base);
	}
	return result;
}
ll gcd(ll x,ll y){
	if(x==0&&y!=0) return y;
	if(x!=0&&y==0) return x;
	if(x==0&&y==0) return 0;
	if(x%y==0) return y;
	return gcd(y,x%y);
}
ll binary(ll x){
	ll l=0,r=1e7;
	while(l<=r){
		ll mid=(l+r)/2;
		ll m=mid;
		mid=mid*(mid+1)/2;
		if(mid>x) r=m-1;
		else l=m+1;
	}
	return r;
}
int main(){
	int t;sc(t);
	while(t--){
		ll left,right;
		sl(left);sl(right);
		ll l=binary(left);
		ll r=binary(right);
		ll sum=0;
		if(l==r){
			if((l+1)*l/2!=left) left=left-l*(l+1)/2;
			else left=l;
			if((r+1)*r/2!=right) right=right-r*(r+1)/2;
			else right=l;
			sum+=((right*(right+1)/2)-(left-1)*left/2);
			cout<<sum<<endl;
			continue;
		}
		if((l+1)*l/2==left&&(r+1)*r/2==right){
			if(l+1<=r){
				ll len=r-l-1;
				sum+=((l+1)*(l+2)/2)*(r-l);
				if(len>=0) sum=sum+(l+2)*(len*(len+1)/2);
				len--;
				if(len>=0) sum+=(len*(len+1)*(len+2)/6);
			}
//			n(n+1)(n+2)/6
//			for(ll i=l+1;i<=r;i++) sum+=(i*(i+1)/2);
			sum+=l;
		}
		else if((l+1)*l/2!=left&&(r+1)*r/2==right){
			if(l+2<=r){
				ll len=r-l-2;
				sum+=((l+2)*(l+3)/2)*(len+1);
				if(len>=0) sum=sum+(l+3)*(len*(len+1)/2);
				len--;
				if(len>=0) sum+=(len*(len+1)*(len+2)/6);
//				sum+=(len*(l+3+r)/2);
			}

//			for(ll i=l+2;i<=r;i++) sum+=(i*(i+1)/2);
			left=left-l*(l+1)/2;
			sum+=((l+1)*(l+2)/2-left*(left+1)/2+left);
		}
		else if((l+1)*l/2==left&&(r+1)*r/2!=right){
			if(l+1<=r){
				ll len=r-l-1;
				sum+=((l+1)*(l+2)/2)*(r-l);
				if(len>=0) sum=sum+(l+2)*(len*(len+1)/2);
				len--;
				if(len>=0) sum+=(len*(len+1)*(len+2)/6);
			}
//			for(ll i=l+1;i<=r;i++) sum+=(i*(i+1)/2);
			sum+=l;
			right=right-r*(r+1)/2;
			sum+=(right*(right+1)/2);
		}
		else{
			left=left-l*(l+1)/2;
			right=right-r*(r+1)/2;
			if(l+2<=r){
				ll len=r-l-2;
				sum+=((l+2)*(l+3)/2)*(len+1);
				if(len>=0) sum=sum+(l+3)*(len*(len+1)/2);
				len--;
				if(len>=0) sum+=(len*(len+1)*(len+2)/6);
//				sum+=(len*(l+3+r)/2);
			}
//			for(ll i=l+2;i<=r;i++) sum+=(i*(i+1)/2);
			sum+=((l+1)*(l+2)/2-left*(left+1)/2+left);
			sum+=(right*(right+1)/2);
		}
		cout<<sum<<endl;
	}
}