NOIP 模拟赛 T2。很厉害的题。
想象数轴上 \(a_1, a_2, \ldots, a_n\) 位置上各有一个洞，每个非负整数位置上有一个点。
每次操作相当于，对于每个点，如果它刚好位于一个洞，那么它会掉进去；否则设它的位置为 \(p\)，位置在它前面的洞有 \(t\) 个，那么这个点的位置变成 \(p - t\)。容易发现每时刻每个点的位置互不相同。
一次询问 \((x, k)\) 相当于，进行 \(k\) 次操作后，找到数轴上位置为 \(x\) 的点，求它进行所有操作前的位置。
单点的移动没有很好的性质。考虑一段连续点的移动。比如极远处 \(L = 10^{18}\) 有一段连续点 \([L, L + n - 1]\)；那么容易发现这些点不重不漏地经过 \([a_1, L + n - 1]\) 的位置。并且每一时刻连续点都是一段连续的区间。
发现对于一个 \([a_i, a_{i + 1})\) 段内的移动，连续点的区间 \([L, L + i - 1]\) 只会重复地进行 \(L \gets L - i\) 的变化，直到连续点覆盖了 \(a_i\)。那么我们只需要维护当连续点的区间覆盖了一个洞时连续点的变化（有哪些点掉洞里了）。
对于一个询问 \((x, k)\)，设在 \(t\) 时刻连续点覆盖了 \(x\)，就相当于求它 \(t - k\) 时刻的位置。
那么每个询问都可以被转化成，初始位于 \(L + x\) 的点，求它 \(k\) 时刻的位置。询问全部离线下来按 \(k\) 从小到大排序，直接模拟一遍即可。
使用树状数组维护初始 \([L, L + n - 1]\) 的连续点哪些掉洞里了。
时间复杂度 \(O((n + m) \log n)\)。
code
// Problem: G. Balls and Pockets
// Contest: Codeforces - Codeforces Round 513 by Barcelona Bootcamp (rated, Div. 1 + Div. 2)
// URL: https://codeforces.com/problemset/problem/1060/G
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 100100;
ll n, m, a[maxn], ans[maxn];
namespace BIT {
ll c[maxn];
inline void init() {
mems(c, 0);
}
inline void update(ll x, ll d) {
for (int i = x; i <= n; i += (i & (-i))) {
c[i] += d;
}
}
inline ll query(ll x) {
ll res = 0;
for (int i = x; i; i -= (i & (-i))) {
res += c[i];
}
return res;
}
inline ll kth(ll k) {
ll s = 0, p = 0;
for (int i = (1 << __lg(n)); i; i >>= 1) {
if (p + i <= n && s + c[p + i] < k) {
p += i;
s += c[p];
}
}
return p + 1;
}
}
struct node {
ll x, k, id;
} qq[maxn];
void solve() {
scanf("%lld%lld", &n, &m);
mems(ans, -1);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
BIT::update(i, 1);
}
for (int i = 1; i <= m; ++i) {
scanf("%lld%lld", &qq[i].x, &qq[i].k);
qq[i].id = i;
if (qq[i].x < a[1]) {
ans[i] = qq[i].x;
}
}
sort(qq + 1, qq + m + 1, [&](const node &a, const node &b) {
return a.x > b.x;
});
ll l = 1e18, t = 0;
for (int i = 1, j = n; i <= m && j;) {
ll d = (l - a[j] + j - 1) / j;
ll k = d * j;
while (i <= m && qq[i].x >= l - k) {
if (ans[qq[i].id] != -1) {
++i;
continue;
}
qq[i].k = t + (l - qq[i].x + j - 1) / j - qq[i].k;
qq[i].x = BIT::kth(qq[i].x - (l - (l - qq[i].x + j - 1) / j * j) + 1);
++i;
}
while (j && a[j] >= l) {
ll t = BIT::kth(a[j] - l + 1);
BIT::update(t, -1);
--j;
}
l -= k;
t += d;
}
BIT::init();
for (int i = 1; i <= n; ++i) {
BIT::update(i, 1);
}
sort(qq + 1, qq + m + 1, [&](const node &a, const node &b) {
return a.k < b.k;
});
l = 1e18;
t = 0;
for (int i = 1, j = n; i <= m && j;) {
ll d = (l - a[j] + j - 1) / j;
ll k = d * j;
while (i <= m && qq[i].k <= t + d) {
if (ans[qq[i].id] != -1) {
++i;
continue;
}
ans[qq[i].id] = l - 1 + BIT::query(qq[i].x) - (qq[i].k - t) * j;
++i;
}
while (j && a[j] >= l) {
ll t = BIT::kth(a[j] - l + 1);
BIT::update(t, -1);
--j;
}
l -= k;
t += d;
}
for (int i = 1; i <= m; ++i) {
printf("%lld\n", ans[i]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}