G - Generate Arrays Editorial by erduolong
Faster SolutionHere is a solution with \(O((n+q)\log n)\) time complexity.
Let \(S=\{(i,A_i)\mid 1\le i\le n\}\). For a sequence \(Q\), if we consider \(Q_i\) as a point \((i,Q_i)\), there exist four numbers \((U,D,L,R)\) such that \(\{(i,Q_i)\mid 1\le i\le |Q|\}=\{(x,y)\mid L\le x\le R\wedge D\le y\le U\}\cap S\). For example, for \(Q_3\) in Sample 1, we can let \(L=2,R=10,D=3,\) and \(U=4\). So each sequence can be represented as four numbers.
For given \(U,D,L,R\), we can use Persistent Segment Trees to calculate the size of \(\{(x,y)\mid L\le x\le R\wedge D\le y\le U\}\cap S\).
Initially, \(L_0=D_0=1,R_0=U_0=n\). For an operation \((t_i,s_i,x_i)\), we do the following to update \(U_{s_i},D_{s_i},L_{s_i},R_{s_i},U_i,D_i,L_i,R_i\):
- When \(t_i=2\), we let \(L_i=L_{s_i},R_i=R_{s_i},U_i=U_{s_i}\).
- If \(x_i<D_{s_i}\), \(D_i\gets D_{s_i}, D_{s_i}\gets U_{s_i}+1\).
- If \(D_{s_i}\le x_i<U_{s_i}\), \(D_i\gets x_i+1,U_{s_i}\gets x_i\).
- If \(U_{s_i}\le x_i\), \(D_i\gets U_i+1\).
- When \(t_i=1\), we let \(R_i=R_{s_i},D_i=D_{s_i},U_i=U_{s_i}\).
- If \(x_i=0\), \(L_i\gets L_{s_i},L_{s_i}\gets R_{s_i}+1\).
- If \(0<x_i< |Q_{s_i}|\), we can perform binary seacrh on the Persistent Segment Tree to find a least \(Z\) such that \(|\{(x,y)\mid L\le x\le Z\wedge D\le y\le U\}\cap S|\ge x_i\), then \(R_{s_i}\gets Z,L_i\gets Z+1\).
- If \(|Q_{s_i}|\le x_i\), \(L_i\gets R_i+1\).
Code
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n,q,p[N],rt[N],idx,u[N],d[N],l[N],r[N];
struct tn{int ls,rs,val;}tr[N*20];
void ins(int&u,int v,int x,int l=1,int r=n){
tr[u=++idx]=tr[v];
if(l^r){
int mid=l+r>>1;
if(x<=mid) ins(tr[u].ls,tr[v].ls,x,l,mid);
else ins(tr[u].rs,tr[v].rs,x,mid+1,r);
tr[u].val=tr[tr[u].ls].val+tr[tr[u].rs].val;
}else ++tr[u].val;
}
int que(int u,int L,int R,int l=1,int r=n){
if(!u||(L<=l&&r<=R)) return tr[u].val;
int mid=l+r>>1,res=0;
if(L<=mid) res=que(tr[u].ls,L,R,l,mid);
if(R>mid) res+=que(tr[u].rs,L,R,mid+1,r);
return res;
}
int sch(int u,int v,int x,int l=1,int r=n){//binary search
if(l==r) return l;
int mid=l+r>>1,val=tr[tr[u].ls].val-tr[tr[v].ls].val;
if(val>=x) return sch(tr[u].ls,tr[v].ls,x,l,mid);
return sch(tr[u].rs,tr[v].rs,x-val,mid+1,r);
}
int ask(int u,int d,int l,int r){//ask for the size
if(l>r||d>u) return 0;
return que(rt[u],l,r)-que(rt[d-1],l,r);
}
int main(){
scanf("%d",&n),u[0]=r[0]=n,l[0]=d[0]=1;
for(int i=1,x;i<=n;++i) scanf("%d",&x),p[x]=i;
for(int i=1;i<=n;++i) ins(rt[i],rt[i-1],p[i]);//build the tree
scanf("%d",&q);
for(int i=1,t,s,x;i<=q;++i){
scanf("%d%d%d",&t,&s,&x),u[i]=u[s],d[i]=d[s],l[i]=l[s],r[i]=r[s];
if(t==2){
if((x=max(x,d[i]-1))<u[i]) u[s]=x,d[i]=x+1;
else d[i]=u[i]+1;
}else{
if(!x) l[s]=r[s]+1;
else if(x<ask(u[i],d[i],l[i],r[i])){
t=l[i]>1?ask(u[i],d[i],1,l[i]-1):0;
r[s]=sch(rt[u[i]],rt[d[i]-1],x+t),l[i]=r[s]+1;
}else l[i]=r[i]+1;
}
printf("%d\n",ask(u[i],d[i],l[i],r[i]));
}
return 0;
}
posted:
last update: