【2024.10.31练习】123

题目描述

题目分析

数据量大的题目首先考虑二分。

将该数列写成下类似三角行列式形式：

1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
...

求数字位置，可以先求数字所在行数（二分查找），再求数字在第几列。

这里注意数据范围，一开始我将最大行数设为1e6，但是这样最多只能容纳5*10^11个数字。

我的代码

#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#define int long long 
using namespace std;
const int MAX_ROW = 10000005;
int sum[MAX_ROW];
int s, t;
void init() {sum[0] = 0;for (int i = 1; i <= MAX_ROW; i++){sum[i] = sum[i - 1] + i * (i + 1) / 2;}
}
int binary_search(int x,int l,int r) {while (r - l > 1) {int mid = (r + l) / 2;if ((mid + 1) * (mid + 2) / 2 > x) {r = mid;}else {l = mid;}}return r;
}
int get_sum(int row, int x) {int e = x - row * (row + 1) / 2;return e * (e + 1) / 2 + sum[row];
}
signed main(void)
{init();int n;cin >> n;for (int i = 0; i < n; i++){cin >> s >> t;cout << get_sum(binary_search(t, -1, MAX_ROW), t) - get_sum(binary_search(s - 1, -1, MAX_ROW), s - 1) << endl;}return 0;
}