蓝桥杯 十二届 决赛 C/C++ 大学B组 F:123

时间限制: 1.0s 内存限制: 256.0MB 本题总分：20 分
【问题描述】
小蓝发现了一个有趣的数列，这个数列的前几项如下：
1, 1, 2, 1, 2, 3, 1, 2, 3, 4, …
小蓝发现，这个数列前 1 项是整数 1，接下来 2 项是整数 1 至 2，接下来
3 项是整数 1 至 3，接下来 4 项是整数 1 至 4，依次类推。
小蓝想知道，这个数列中，连续一段的和是多少。
【输入格式】
输入的第一行包含一个整数 T，表示询问的个数。
接下来 T 行，每行包含一组询问，其中第 i 行包含两个整数 l i 和 r i ，表示
询问数列中第 l i 个数到第 r i 个数的和。
【输出格式】
输出 T 行，每行包含一个整数表示对应询问的答案。

【样例输入】
3
1 1
1 3
5 8

【样例输出】
1
4
8

【评测用例规模与约定】
对于 10% 的评测用例，1 ≤ T ≤ 30, 1 ≤ l i ≤ r i ≤ 100。
对于 20% 的评测用例，1 ≤ T ≤ 100, 1 ≤ l i ≤ r i ≤ 1000。
对于 40% 的评测用例，1 ≤ T ≤ 1000, 1 ≤ l i ≤ r i ≤ 10 6 。
对于 70% 的评测用例，1 ≤ T ≤ 10000, 1 ≤ l i ≤ r i ≤ 10 9 。
对于 80% 的评测用例，1 ≤ T ≤ 1000, 1 ≤ l i ≤ r i ≤ 10 12 。
对于 90% 的评测用例，1 ≤ T ≤ 10000, 1 ≤ l i ≤ r i ≤ 10 12 。
对于所有评测用例，1 ≤ T ≤ 100000, 1 ≤ l i ≤ r i ≤ 10 12 。

解题思路：将子串分组，如1为一组，12为一组，123为一组.......

分组后找到大于左边界的最小的一组 

while(j 
在段代码中，count表示该组的项数，j用来记录总项数和各组的和
 
例如count为3时表示当前组为1，2，3，共有1，1，2，1，2，3,六项，因此j为6，该组的和为1+2+3=6；
 
找到左边界所在的组后要把该组中，左边界及左边界以后的值保存起来
 
while(j 
ans表示区间和，j-l为这组有几个值应该被记入区间和，该组的项数count减掉（j-l）再减1（左边界）就是不应该被记入区间和的项的项数，然后用等差求和公式计算一波。
 
对右边界的操作和左边界差不多
 
while(j+count+1 
这里ans+=j就是把在区间内的值全保存起来
 
end[k++] = ans + (1+r - j)*(r-j)/2; //把右侧没加上的全加上
 
这里就是把右边多计算的删掉
 
全部代码：
 
// #include
// #include
#include
typedef unsigned long long ull;
using namespace std;
int main()
{
    ull T, l, r;
    cin >> T;
    ull end[T] = {0};
    int k = 0;
    for (long i = 0; i < T;i++)
    {
        cin >> l >> r;
        ull j = 1,count=1;
        ull ans = 0;//记录区间和
        while(j 
代码包熟，和其他人的代码结果进行了很多次比较，莫得问题
 
最后能弱弱的求个点赞麻（哎嘿~）