差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:吉司机线段树 [2020/10/02 10:39]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:吉司机线段树 [2020/10/02 11:02] (当前版本)
jxm2001 [习题三]
@@ 行 711: / 行 711: @@
 === 题意 ===
+给定 $1\sim n$ 的排列 $A$。
+对 $k\in [1,n]$，输出由 $a_i\le k$ 构成的子序列建立的大根堆笛卡尔树的所有结点的子树大小之和。
 === 题解 ===
+对任意 $k$，将子序列 $B$ 中的数按 $1\sim k$ 编号，设 $l_i$ 表示所有满足 $b_j\lt b_i\cap j\lt i$ 的 $j$ 的最大值，如果 $j$ 不存在则 $l_i=0$。
+$r_i$ 表示所有满足 $b_j\lt b_i\cap j\lt i$ 的 $j$ 的最小值，如果 $j$ 不存在则 $r_i=k+1$。于是 $b_i$ 的子树代表序列为 $(l_i,r_i)$，子树大小为 $r_i-l_i+1$。
+故 $ans_k=\sum_{i=1}^k (r_i-l_i-1)$，先考虑求 $\sum_{i=1}^k r_i$。
+考虑将 $k$ 插入序列 $B$ 后 $r_i$ 数组的变化，设 $k$ 在 $A$ 中的位置为 $p$，利用线段树不难求出 $k$ 在 $B$ 中的位置为 $p'$。
+于是 $r_{p'}=i+1$。如果 $i\lt p$，则 $r_i=\min (r_i,p')$。如果 $i\gt p$，则 $r_i=r_i+1$。
+利用吉司机线段树额外维护有效结点数即可，时间复杂度 $O(n\log^2 n)$。
+对 $\sum_{i=1}^k l_i$，先将 $A$ 序列翻转再按上述过程求出 $\sum_{i=1}^k r'_i$，于是有
+$$\sum_{i=1}^k (r_i-l_i-1)=\sum_{i=1}^k (r_i-(k+1-r'_i)-1)=\sum_{i=1}^k r_i+\sum_{i=1}^k r'_i-k(k+2)$$
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1.5e5+5,Inf=2e9;
+int a[MAXN];
+int lef[MAXN<<2],rig[MAXN<<2],maxv[MAXN<<2],maxc[MAXN<<2],secv[MAXN<<2],sz[MAXN<<2];
+int lazy1[MAXN<<2],lazy2[MAXN<<2];
+LL sum[MAXN<<2];
+void push_up(int k){
+	sum[k]=sum[k<<1]+sum[k<<1|1];
+	sz[k]=sz[k<<1]+sz[k<<1|1];
+	if(maxv[k<<1]==maxv[k<<1|1]){
+		maxv[k]=maxv[k<<1];
+		maxc[k]=maxc[k<<1]+maxc[k<<1|1];
+		secv[k]=max(secv[k<<1],secv[k<<1|1]);
+	}
+	else if(maxv[k<<1]>maxv[k<<1|1]){
+		maxv[k]=maxv[k<<1];
+		maxc[k]=maxc[k<<1];
+		secv[k]=max(secv[k<<1],maxv[k<<1|1]);
+	}
+	else{
+		maxv[k]=maxv[k<<1|1];
+		maxc[k]=maxc[k<<1|1];
+		secv[k]=max(maxv[k<<1],secv[k<<1|1]);
+	}
+}
+void push_add(int k,int v){
+	sum[k]+=1LL*sz[k]*v;
+	maxv[k]+=v,lazy1[k]+=v;
+	if(secv[k]!=-Inf)secv[k]+=v;
+	if(lazy2[k]!=-Inf)lazy2[k]+=v;
+}
+void push_min(int k,int v){
+	if(v>=maxv[k])return;
+	sum[k]-=1LL*maxc[k]*(maxv[k]-v);
+	maxv[k]=lazy2[k]=v;
+}
+void push_down(int k){
+	if(lazy1[k]){
+		push_add(k<<1,lazy1[k]);
+		push_add(k<<1|1,lazy1[k]);
+		lazy1[k]=0;
+	}
+	if(lazy2[k]!=-Inf){
+		push_min(k<<1,lazy2[k]);
+		push_min(k<<1|1,lazy2[k]);
+		lazy2[k]=-Inf;
+	}
+}
+void build(int k,int L,int R){
+	lef[k]=L,rig[k]=R,lazy1[k]=0,lazy2[k]=-Inf;
+	if(L==R){
+		sum[k]=maxv[k]=sz[k]=maxc[k]=0;
+		secv[k]=-Inf;
+		return;
+	}
+	int M=L+R>>1;
+	build(k<<1,L,M);
+	build(k<<1|1,M+1,R);
+	push_up(k);
+}
+void update_add(int k,int L,int R,int v){
+	if(L<=lef[k]&&rig[k]<=R)
+	return push_add(k,v);
+	push_down(k);
+	int mid=lef[k]+rig[k]>>1;
+	if(mid>=L)update_add(k<<1,L,R,v);
+	if(mid<R)update_add(k<<1|1,L,R,v);
+	push_up(k);
+}
+void update_min(int k,int L,int R,int v){
+	if(maxv[k]<=v)return;
+	if(L<=lef[k]&&rig[k]<=R&&secv[k]<v)
+	return push_min(k,v);
+	push_down(k);
+	int mid=lef[k]+rig[k]>>1;
+	if(mid>=L)update_min(k<<1,L,R,v);
+	if(mid<R)update_min(k<<1|1,L,R,v);
+	push_up(k);
+}
+void insert_node(int k,int pos,int v){
+	if(lef[k]==rig[k]){
+		sum[k]=maxv[k]=v;
+		maxc[k]=sz[k]=1;
+		return;
+	}
+	push_down(k);
+	int mid=lef[k]+rig[k]>>1;
+	if(mid>=pos)
+	insert_node(k<<1,pos,v);
+	else
+	insert_node(k<<1|1,pos,v);
+	push_up(k);
+}
+int query_sz(int k,int L,int R){
+	if(L<=lef[k]&&rig[k]<=R)return sz[k];
+	push_down(k);
+	int mid=lef[k]+rig[k]>>1;
+	int s=0;
+	if(mid>=L)s+=query_sz(k<<1,L,R);
+	if(mid<R)s+=query_sz(k<<1|1,L,R);
+	return s;
+}
+int p[MAXN];
+LL ans[MAXN];
+int main()
+{
+	int n=read_int();
+	_rep(i,1,n)
+	p[read_int()]=i;
+	build(1,1,n);
+	_rep(i,1,n){
+		insert_node(1,p[i],i+1);
+		if(p[i]<n)update_add(1,p[i]+1,n,1);
+		if(p[i]>1)update_min(1,1,p[i]-1,query_sz(1,1,p[i]));
+		ans[i]+=sum[1];
+	}
+	build(1,1,n);
+	_rep(i,1,n)p[i]=n+1-p[i];
+	_rep(i,1,n){
+		insert_node(1,p[i],i+1);
+		if(p[i]<n)update_add(1,p[i]+1,n,1);
+		if(p[i]>1)update_min(1,1,p[i]-1,query_sz(1,1,p[i]));
+		ans[i]+=sum[1];
+	}
+	_rep(i,1,n)
+	enter(ans[i]-1LL*i*(i+2));
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具