lanqiao OJ 1591 “123”

#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std ;
 
const int N = 1414215 ;
typedef long long LL ;
LL a[N],s[N] ;//a数组有两个含义，既是前面所有区间中的元素的个数和，也是这个区间内的数值和；
               //b数组的含义是前i个区间的元素数值和。
 
LL presum(LL i){
  LL l = 0 , r = N;
  while(l < r){//二分，找大于i的第一个数的a[j+1] 那i就落在第j + 1个区间中
    LL mid =l + r  >> 1 ;
    if(a[mid] > i) r = mid ;
    else l = mid +1 ; 
  }
  return s[l-1] + a[i-a[l-1]]  ;//前j个区间的和 再加上在当前区间的k位置的前面的数的和
}
 
int main(){
  for(int i = 1 ; i <= N ; i ++){
    a[i] = a[i-1] + i ;
    s[i] = s[i-1] + a[i] ;
  }
  int q ; cin >> q;
  while(q --){
    LL l , r ; cin >> l >> r ;
    LL ans = presum(r) - presum(l-1) ;//要包含l所以剪的是 l-1 的前缀和
    cout << ans << endl ;
  }
}