有某个你不知道的排列\(p\)
设\(f_i\)表示\(\sum_{j<i}[p_j>p_i]\)。给你\(f_i\)。要维护：
- 给\(f_i\)单点修改。
- 询问\(p_i\)。
\(n,Q\le 10^5\)
令\(f_i\leftarrow i-1-f_i\)。增量构造，每次将\(i\)插入到第\(f_i\)个数后面，最后得到的东西即\(p_i\)。
发现前面插入的数的具体相对顺序对后面没有影响。
于是对于每个块，预处理：模拟这样插的过程，一开始有块外前面的数，不关心其相对顺序。然后一个个插，记下插完这个块之后块内所有点的位置。预处理暴力可以做到\(O(nB)\)，也能用数据结构做到\(O(n\lg n)\)。
询问从\(i\)开始，先查\(i\)在这个块以及之前块的排名。然后往后枚举块，根据\(i\)之前的排名，二分出插入了后面的块后的新的排名，用这个新的排名继续做下去。时间\(O(\frac{n}{B}\lg B)\)。
修改可以用数据结构做到\(O(B\lg B)\)。不过还能更优：设小于等于\(i\)的点（包括块外前面）为黑点，将黑点从最终的排名中单独提出按照最后的顺序排好，改变\(i\)的位置（也就是将某个区间循环移位），然后再将这些黑点按照顺序放回拿出它们排列中的位置。模拟这个过程，可以做到\(O(B)\)。
于是时间就可以做到\(O(n\sqrt {n\lg n})\)啦。
说得简单实际上处理循环移位那一部分老阴间了；而且CF机子那么快写\(O(n\sqrt n\lg n)\)过去也应该是轻轻松松。
using namespace std;
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
const int N=100005;
const int B=1500;
int n,Q;
int f[N];
int bel[N],R[N],nb;
pair<int,int> _rk[N/B+5][B+5];
int p[N];
void init(int b,pair<int,int> rk[]){
rk[R[b]-R[b-1]+1]=mp(R[b]+1,0);
for (int i=R[b-1]+1,k=1;i<=R[b];++i,++k){
int x=upper_bound(rk+1,rk+k,mp(f[i],i))-rk-1;
for (int j=k;j>x+1;--j)
rk[j]=rk[j-1],rk[j].fi++;
rk[x+1]=mp(f[i]+1,i);
}
for (int i=1;i<=R[b]-R[b-1];++i)
p[rk[i].se]=i;
}
int query(int v){
int u=_rk[bel[v]][p[v]].fi;
for (int b=bel[v]+1;b<=nb;++b){
int l=1,r=R[b]-R[b-1],res=0;
while (l<=r){
int mid=l+r>>1;
if (u>_rk[b][mid].fi-mid)
l=(res=mid)+1;
else
r=mid-1;
}
u+=res;
}
return u;
}
void mdf(int x,int c,int b,pair<int,int> rk[]){
int k=0,y=-1;
if (f[x]==c) return;
if (f[x]<c){
int k_=-1;
for (int i=1;i<=R[b]-R[b-1];++i){
if (rk[i].fi-k>c){
break;
}
if (rk[i].se>=x)
++k;
y=i,k_=k;
if (rk[i].fi-k==c){
break;
}
}
c=k_+c;
for (int i=p[x];i<y;++i)
rk[i]=rk[i+1];
rk[y]=mp(c,x);
int pos=p[x]-1;
for (int i=p[x];i<y;++i){
if (rk[i].se<=x){
if (rk[i-1].fi+1<rk[i].fi){
rk[i].fi--;
pos=i;
}
else{
for (int j=i;j>pos+1;--j)
swap(rk[j],rk[j-1]);
rk[pos+1].fi=rk[pos+2].fi-1;
pos=i;
}
}
else if (rk[i].fi+1<rk[i+1].fi)
pos=i;
}
}
else{
y=-1;
for (int i=1;i<=R[b]-R[b-1];++i){
if (rk[i].se>=x)
++k;
if (rk[i].fi-k>=c+1){
y=i;
if (rk[i].se<x)
c=k+c+1;
else
c=k-1+c+1;
break;
}
}
if (y==-1)
y=p[x],c=R[b];
for (int i=p[x];i>y;--i)
rk[i]=rk[i-1];
rk[y]=mp(c,x);
int pos=p[x]+1;
for (int i=p[x];i>y;--i){
if (rk[i].se<=x){
if (rk[i+1].fi-1>rk[i].fi){
rk[i].fi++;
pos=i;
}
else{
for (int j=i;j<pos-1;++j)
swap(rk[j],rk[j+1]);
rk[pos-1].fi=rk[pos-2].fi+1;
pos=i;
}
}
else if (rk[i].fi-1>rk[i-1].fi)
pos=i;
}
}
for (int i=1;i<=R[b]-R[b-1];++i)
p[rk[i].se]=i;
}
int main(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;++i){
scanf("%d",&f[i]);
f[i]=i-1-f[i];
}
for (int i=1;i<=n;++i){
bel[i]=(i-1)/B+1;
R[bel[i]]=i;
}
nb=bel[n];
for (int i=1;i<=nb;++i)
init(i,_rk[i]);
scanf("%d",&Q);
while (Q--){
int op,x,c;
scanf("%d%d",&op,&x);
if (op==1){
scanf("%d",&c);
c=x-1-c;
mdf(x,c,bel[x],_rk[bel[x]]);
f[x]=c;
}
else{
int ans=query(x);
printf("%d\n",ans);
}
}
return 0;
}