题意 给定一个长度不超过$5*10^{6}$的数列和不超过$100$个询问，每次询问这个数列第$k$小的数，返回所有询问的和
内存限制很小，小到不能存下这个数列。（数列以种子的形式给出）
时限$10s$，内存限制$13MB$
我自己YY的分治缩小答案上下界范围第三个样例要跑$90s$左右，果断放弃
根据题目给出的条件我们知道每一个数的范围都在$[0, 10^{9}+6]$里。
那么我们开一个大小为$32000$的数组，把$[0, 10^{9}+6]$分成$32000$个大小相同的块。
然后先遍历整个数列，求出每个块中有多少个数。
在询问的时候先确定当前要查询的那个数在哪个块里。
确定了那个块的位置之后，我们再遍历一遍数列，找到那些在这个块里的数，再把精确值求出来。
时间复杂度$O(qn)$
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define MP make_pair
#define fi first
#define se second typedef long long LL; const int N = 32000; int block[N], c[N]; class LimitedMemorySeries1 {
public:
LL getSum(int n, int x0, int a, int b, vector<int> query){
memset(block, 0, sizeof block); int x = x0;
rep(i, 0, n - 1){
block[x / N]++;
x = (int)((x * (LL)a + b) % 1000000007);
} LL sum = 0;
for (auto q : query){
int acum = 0;
int p = -1;
int before = 0;
rep(i, 0, N - 1){
if (acum <= q && q < acum + block[i]){
p = i;
before = acum;
break;
}
acum += block[i];
} memset(c, 0, sizeof c); x = x0;
for (int i = 0; i < n; i++){
if (p * N <= x && x < (p + 1) * N){
c[x - p * N]++;
}
x = (int)((x * (LL)a + b) % 1000000007);
} acum = before;
int r = -1;
for (int i = 0; i < N; i++){
if (acum <= q && q < acum + c[i]){
r = p * N + i;
break;
}
acum += c[i];
}
sum += r;
} return sum;
}
};