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;
}
|