G - Generate Arrays Editorial by erduolong

Faster Solution

Here 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: