题目描述

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

1,1,2,1,2,3,1,2,3,4,⋯1,1,2,1,2,3,1,2,3,4,⋯

小蓝发现，这个数列前 11 项是整数 11，接下来 22 项是整数 11 至 22，接下来 33 项是整数 11 至 33，接下来 44 项是整数 11 至 4，依次类推。

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

输入描述

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

接下来 TT 行，每行包含一组询问，其中第 ii 行包含两个整数 lili​ 和 riri​，表示询问数列中第 lili​ 个数到第 riri​ 个数的和。

输出描述

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

输入输出样例

示例

输入

3
1 1
1 3
5 8

输出

1
4
8

评测用例规模与约定

对于 1010% 的评测用例，1≤T≤30,1≤li≤ri≤1001≤T≤30,1≤li​≤ri​≤100。

对于 2020% 的评测用例，1≤T≤100,1≤li≤ri≤10001≤T≤100,1≤li​≤ri​≤1000。

对于 4040% 的评测用例，1≤T≤1000,1≤li≤ri≤1061≤T≤1000,1≤li​≤ri​≤106。

对于 7070% 的评测用例，1≤T≤10000,1≤li≤ri≤1091≤T≤10000,1≤li​≤ri​≤109。

对于 8080% 的评测用例，1≤T≤1000,1≤li≤ri≤10121≤T≤1000,1≤li​≤ri​≤1012。

对于 9090% 的评测用例，1≤T≤10000,1≤li≤ri≤10121≤T≤10000,1≤li​≤ri​≤1012。

对于所有评测用例，1≤T≤100000,1≤li≤ri≤10121≤T≤100000,1≤li​≤ri​≤1012。

运行限制

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

暴力会超时

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int n=scan.nextInt();int[] a=new int[n+1];int[] b=new int[n+1];int[] c=new int[n+1];for(int i=1;i<=n;i++) {a[i]=scan.nextInt();}for(int j=1;j<=n;j++) {b[j]=scan.nextInt();}for(int k=1;k<=n;k++) {c[k]=scan.nextInt();}int sum=0;scan.close();for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++) {for(int k=1;k<=n;k++) {if(a[i]<b[j]&&b[j]<c[k]) {sum++;}}}}System.out.println(sum);}
}

 仍然会超时

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int n=scan.nextInt();int[] a=new int[n+1];int[] b=new int[n+1];int[] c=new int[n+1];for(int i=1;i<=n;i++) {a[i]=scan.nextInt();}for(int j=1;j<=n;j++) {b[j]=scan.nextInt();}for(int k=1;k<=n;k++) {c[k]=scan.nextInt();}scan.close();int s=0;int[] ab=new int[n+1];int[] bc=new int[n+1];Arrays.sort(a);Arrays.sort(b);Arrays.sort(c);for(int i=1;i<n+1;i++) {for(int j=1;j<n+1;j++) {if(b[i]>a[j]) {ab[i]++;}}}for(int i=1;i<n+1;i++) {//  int s=0;for(int j=1;j<n+1;j++) {if(b[i]<c[j]) {bc[i]++;}}}int sum=0;for(int i=1;i<n+1;i++) {sum+=ab[i]*bc[i];}System.out.println(sum);}
}

指针：

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int n=scan.nextInt();int[] a=new int[n];int[] b=new int[n];int[] c=new int[n];for(int i=0;i<n;i++) {a[i]=scan.nextInt();}for(int j=0;j<n;j++) {b[j]=scan.nextInt();}for(int k=0;k<n;k++) {c[k]=scan.nextInt();}scan.close();Arrays.sort(a);Arrays.sort(b);Arrays.sort(c);long sum=0;int p=0,q=0;for(int i=0;i<n;i++) {while(p<n&&a[p]<b[i]) {p++;}while(q<n&&c[q]<=b[i]) {q++;}sum+=((long)p*(n-q));}System.out.println(sum);}
}