专栏文章

题解：P13968 [VKOSHP 2024] Classics

ccogimyun
P13968题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minnx3e2
此快照首次捕获于
2025/12/02 05:29
3 个月前
此快照最后确认于
2025/12/02 05:29
3 个月前
查看原文
我们不妨先维护出按照题目要求插入数据后的数列 aa，很明显，每次将 ii 插入 第 pp 位就是要找到数列 aa 中的第 p−1p-1 号元素，然后将 ii 插入到 p−1p-1 号元素与 pp 号元素之间，这可以非常轻松的用平衡树维护，具体来说就是将排名小于等于 p−1p-1 与大于 pp 的两棵子树分裂，然后新建节点记录 ii,最后将这三棵子树合并。
接下来，我们分析 ii 插入到数列 aa 的第 jj 位，由于 1 到 nn 是从小到大插入的，所以我们不难发现 aja_j 是不可能对 ak,k∈[j+1,n]a_k,k\in[j+1,n] 中已经插入的元素造成贡献的，而对 ak,k∈[1,j−1]a_k,k\in[1,j-1] 而言我们只需找出其中以 ak,k∈[1,j−1]a_k,k\in[1,j-1] 结尾的最大的最长上升子序列长度 ll，那么以 aja_j 为结尾的最长上升子序列长度为 l+1l+1，特别的，当 aja_j 前面没有元素时，长度即为 1，这一过程明显可以用线段树实现。

CODE

CPP
#include<bits/stdc++.h>
using namespace std;
int n,rt,a[200005],idx,b[200005],tt[800005];
struct node{
	int l,r,sz,val,pri;
}tr[200005];
void split(int p,int x,int &l,int &r){
	if(!p){
		l=0;
		r=0;
		return;
	}
	if(tr[tr[p].l].sz+1>x){
		r=p;
		split(tr[p].l,x,l,tr[p].l);
		tr[p].sz=tr[tr[p].l].sz+tr[tr[p].r].sz+1;
	}
	else{
		l=p;
		split(tr[p].r,x-tr[tr[p].l].sz-1,tr[p].r,r);
		tr[p].sz=tr[tr[p].l].sz+tr[tr[p].r].sz+1;
	}
}
void check(int x){
	if(!x)
		return;
	check(tr[x].l);
	a[++idx]=tr[x].val;
	check(tr[x].r);
}
int merge(int u,int v){
	if(!u||!v)
		return u|v;
	if(tr[u].pri>tr[v].pri){
		tr[u].r=merge(tr[u].r,v);
		tr[u].sz=tr[tr[u].l].sz+tr[tr[u].r].sz+1;
		return u;
	}
	tr[v].l=merge(u,tr[v].l);
	tr[v].sz=tr[tr[v].l].sz+tr[tr[v].r].sz+1;
	return v;
}
int query(int p,int s,int t,int r){
	if(r==0)
		return 0;
	if(t<=r)
		return tt[p];
	int mid=(s+t)>>1,res=query(p<<1,s,mid,r);
	if(r>mid)
		res=max(res,query(p<<1|1,mid+1,t,r));
	return res;
}
void modify(int p,int l,int r,int x,int y){
	if(l==r){
		tt[p]=y;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
		modify(p<<1,l,mid,x,y);
	else
		modify(p<<1|1,mid+1,r,x,y);
	tt[p]=max(tt[p<<1],tt[p<<1|1]);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	srand(time(NULL));
	cin>>n;
	int x;
	cin>>x;
	rt=1;
	tr[1].val=1;
	tr[1].sz=1;
	tr[1].pri=rand();
	for(int i=2;i<=n;i++){
		cin>>x;
		int l,r;
		split(rt,x-1,l,r);
		tr[i].pri=rand();
		tr[i].val=i;
		tr[i].sz=1;
		rt=merge(l,merge(i,r));
	}
	check(rt);
	for(int i=1;i<=n;i++)
		b[a[i]]=i;
	int maxn=0;
	for(int i=1;i<=n;i++){
		int ttt=query(1,1,n,b[i]-1);
		modify(1,1,n,b[i],ttt+1);
		cout<<(maxn=max(maxn,ttt+1))<<endl;
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...