0%

「Codeforces 1060G」Balls and Pockets

Codeforces 1060G. Balls and Pockets

题意

有一个从 $0$ 到 $\infty$ 的序列,第 $a_1,a_2,\dotsc,a_n$ 个位置上各有一个口袋

每秒每个口袋会吃掉当前位置上的数,较大的数会向较小的方向移动以填补空位

$m$ 次询问在 $k_i$ 秒后一个位置 $x_i$ 上的数是什么

$a_1< a_2< \cdots< a_n$

$n,m\le 10^5, a_i,k_i,x_i\le 10^9$

做法

考虑每个口袋吃掉的数是不重复的,在无穷远处连续的 $n$ 个数字最终会被不同的口袋吃掉。

可以用平衡树简单模拟这一过程。

求解一组询问 $x_i,k_i$ 时,如果 $x_i<a_1$,这个位置不会改变。

否则 $x_i$ 必然会被上述过程中的恰好一个数字经过。记录下经过的数字设为 $y$,时间为 $t$,即数字 $y$ 在 $t$ 秒后到了 $x_i$ 的位置。

要求 $k_i$ 秒后在 $x_i$ 位置上的数,即 $y$ 在 $t-k_i$ 秒后到达的位置,这可以再进行一遍上述过程求出。

具体描述一下模拟的过程。

假设当前这些数占据了 $[l,l+w-1]$ 的位置,如果不考虑口袋的影响,$1$ 秒后会移动到 $[l-w,l-1]$ 的位置。如果移动多次没有碰到口袋,可以快速计算;如果移动后覆盖了至少一个口袋,可以从后往前依次吃掉,假设吃掉的是第 $e$ 个位置上的数,即当前存在的数中的第 $e-l+1$ 个,可以用平衡树简单维护。

复杂度 $\mathcal O((n+m)\log n)$

代码

手写线段树会快很多吧..但是用 pb_ds 抢到了长度第一和速度第二 = =

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define ll long long

const int N = 100005;
int n, m, cnt, a[N];
ll ans[N];
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> s;
struct query{
ll x;
int t, id;
inline bool operator<(const query &r)const{ return x<r.x;}
} q[N], f[N];
int main() {
scanf("%d%d", &n, &m);
for(int i=1; i<=n; ++i) scanf("%d", a+i);
for(int i=1; i<=m; ++i){
++cnt;
scanf("%lld%d", &q[cnt].x, &q[cnt].t);
if(q[cnt].x<a[1]) ans[i]=q[cnt].x, --cnt; else q[cnt].id=i;
}
sort(q+1, q+cnt+1);
for(int i=0; i<n; ++i) s.insert(i);
ll now=1e18, tim=0;
int i=n, j=cnt;
while(j){
ll x=(now-a[i]-1)/i+1;
while(j && q[j].x>=now-i*x)
f[j].x=tim+(now-q[j].x-1)/i+1-q[j].t,
f[j].t=*s.find_by_order(i-(now-q[j].x+i-1)%i-1),
f[j].id=q[j].id, --j;
tim+=x, now-=i*x;
while(i && a[i]>=now) s.erase(s.find_by_order(a[i--]-now));
}
sort(f+1, f+cnt+1);
s.clear();
for(int i=0; i<n; ++i) s.insert(i);
now=1e18, tim=0, i=n, j=1;
while(j<=cnt){
ll x=(now-a[i]-1)/i+1;
while(j<=cnt && tim+x>=f[j].x)
ans[f[j].id]=now+s.order_of_key(f[j].t)-(f[j].x-tim)*i, ++j;
tim+=x, now-=i*x;
while(i && a[i]>=now) s.erase(s.find_by_order(a[i--]-now));
}
for(int i=1; i<=m; ++i) printf("%lld\n", ans[i]);
return 0;
}