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