CF1060G Balls and Pockets 题解
Gold14526
·
·
题解
$\rm Difficulty:3400
题意
有一个无限长的序列 p=\{0,1,2,3,4,\dots\}，其中第 i 个位置上的数是 i。
给定长度为 n 的非负整数序列 a，我们对序列 p 做无限次以下操作：
- 对于每个 i\in [1,n]，删去 p_{a_i}。
- 将剩下的元素顺次拼接作为新的序列 p。
### 做法
设 $f(x)$ 表示第一次操作后 $p_x$ 的值，那么可以得到每次操作后 $p_x$ 会变成 $p_{f(x)}$，以及第 $k$ 次操作后 $p_x=f^k(x)$。
第二个结论可以归纳证明：第一次操作后 $p_x=f(x),p_{f(x)}=f(f(x)),\dots$，以此类推可以证明上述结论。
上面考虑了对于一个位置上的值的性质，接下来考虑一下一个值如何移动。
对于一个值 $x$，它暂时没被删掉，假设它的下标是 $id$，有 $cnt$ 个 $a_i<id$，那么下一步它的下标会减 $cnt$，每一步都是如此。
我们找一个很靠右的区间，例如 $[10^{18},10^{18}+n-1]$，令 $L=10^{18}$，每次这个区间中的数下标都会减 $n$，直到遇到 $a_n$，在此之前这些数会不重不漏地覆盖右侧的所有数。当现存区间的左端点现在在 $a_i\sim a_{i+1}$ 间时，区间中会剩下 $i$ 个数，然后每个数下标都会减 $i$，所以它们会不重不漏地覆盖 $[a_1,L+n-1]$ 中的所有位置。
于是，对于一次询问 $x,k$，我们找到 $x$ 这个位置被覆盖的时间 $t$，那我们就求出了 $f^t(x)$，考虑求出 $f^{k-t}(f^t(x))$。
这个比较简单，我只需要查询 $f^t(x)$ 在 $t-k$ 时刻前在哪个位置即可。
显然我们需要特判 $x<a_1$。
以上过程可以用主席树维护，不知道会不会卡常，但是可以把查询离线下来再跑一遍，这样就只需要树状数组，可以轻易通过，时间复杂度 $O((n+q)\log n)$。
### 代码
```cpp
#include<bits/stdc++.h>
#define cint const int
#define uint unsigned int
#define cuint const unsigned int
#define ll long long
#define cll const long long
#define ull unsigned long long
#define cull const unsigned long long
#define sh short
#define csh const short
#define ush unsigned short
#define cush const unsigned short
using namespace std;
int read()
{
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9')
{
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch-'0');
ch=getchar();
}
return x;
}
void print(cll x)
{
if(x<10)
{
putchar(x+'0');
return;
}
print(x/10);
putchar(x%10+'0');
}
void princh(cll x,const char ch)
{
print(x);
putchar(ch);
}
inline ll Div(cll x,cll y)
{
return (x+y-1)/y;
}
int n,q,a[500001];
ll ans[500001];
struct BIT{
int a[500001];
void clear()
{
for(int i=1;i<=n;++i)a[i]=0;
}
void add(cint x,cint y)
{
for(int i=x;i<=n;i+=(i&-i))a[i]+=y;
}
int ask(cint x)
{
int s=0;
for(int i=x;i;i-=(i&-i))s+=a[i];
return s;
}
int find(int k)
{
int s=0,p=0;
for(int i=1<<__lg(n);i;i>>=1)
{
if(p+i>n)continue;
if(s+a[p+i]<k)
{
p+=i;
s+=a[p];
}
}
return p+1;
}
}T;
struct query{
int idx;
ll x,k;
}op[500001];
bool cmpx(query x,query y)
{
return (x.x>y.x);
}
bool cmpk(query x,query y)
{
return (x.k<y.k);
}
ll L=1e18,step;
int main()
{
n=read();
q=read();
for(int i=1;i<=n;++i)
{
a[i]=read();
T.add(i,1);
}
for(int i=1;i<=q;++i)
{
op[i].idx=i;
op[i].x=read();
op[i].k=read();
ans[i]=(op[i].x<a[1]?op[i].x:-1);
}
sort(op+1,op+q+1,cmpx);
for(int i=1,j=n;i<=q&&j;)
{
cll d=Div(L-a[j],j),k=d*j;
while(i<=q&&op[i].x>=L-k)
{
if(ans[op[i].idx]==-1)
{
op[i].k=step+Div(L-op[i].x,j)-op[i].k;
op[i].x=T.find(op[i].x-(L-j*Div(L-op[i].x,j))+1);
}
++i;
}
while(j&&a[j]>=L)
{
cint tmp=T.find(a[j]-L+1);
T.add(tmp,-1);
--j;
}
L-=k;
step+=d;
}
sort(op+1,op+q+1,cmpk);
L=1e18;
step=0;
T.clear();
for(int i=1;i<=n;++i)T.add(i,1);
for(int i=1,j=n;i<=q&&j;)
{
cll d=Div(L-a[j],j),k=d*j;
while(i<=q&&op[i].k<=step+d)
{
if(ans[op[i].idx]==-1)
{
ans[op[i].idx]=L-1+T.ask(op[i].x)-(op[i].k-step)*j;
}
++i;
}
while(j&&a[j]>=L)
{
cint tmp=T.find(a[j]-L+1);
T.add(tmp,-1);
--j;
}
L-=k;
step+=d;
}
for(int i=1;i<=q;++i)
{
princh(ans[i],'\n');
}
return 0;
}
```