題目描述

小藍發現了一個有趣的數列，這個數列的前幾項如下：

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

小藍發現，這個數列前?1?項是整數?1，接下來?2?項是整數?1?至?2，接下來?3?項是整數?1?至?3，接下來?4?項是整數?1?至 4，依次類推。

小藍想知道，這個數列中，連續一段的和是多少。

輸入描述

輸入的第一行包含一個整數?T，表示詢問的個數。

接下來?T?行，每行包含一組詢問，其中第?i?行包含兩個整數?li??和?ri?，表示詢問數列中第?li??個數到第?ri?個數的和。

輸出描述

輸出?T?行，每行包含一個整數表示對應詢問的答案。

輸入輸出樣例

示例

輸入

3
1 1
1 3
5 8

輸出

1
4
8

評測用例規模與約定

?前綴和這個方法彎彎繞繞有點多：

#include<iostream>
#include<algorithm>  //for lower_bound
using namespace std;typedef long long ll;const int N = 2e6+10;
ll a[N];  //a[i]:前i組所有元素的個數（第i組元素的和） 
ll b[N];  //b[i]:前i組所有元素的和 int t;//計算數列中前x項的和
ll f(ll x)
{if(x==0) return 0;//pos:數列中第x項是第pos組 //-a:得到下標i int pos=lower_bound(a+1, a+1+N, x)-a;//前pos-1組的和 + 第pos組的前(x-a[pos-1])項的和//第pos組的前(x-a[pos-1])項的和 = 第i組元素的和return b[pos-1]+a[x-a[pos-1]]; 
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);for(ll i=1; i<N; ++i){a[i] = a[i-1]+i;b[i] = b[i-1]+a[i];  //第i組元素的和恰好等于前i組的元素個數 }cin>>t; while(t--){ll l, r;cin>>l>>r;cout<<f(r)-f(l-1)<<'\n';}return 0;
}