差别

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

--- 2020-2021:teams:legal_string:jxm2001:吉司机线段树 [2020/09/28 18:53]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:吉司机线段树 [2020/10/02 11:02] (当前版本)
jxm2001 [习题三]
@@ 行 428: / 行 428: @@
 </hidden>
-===== 算法例题 =====
+===== 算法练习 =====
+==== 习题一 ====
+[[https://www.luogu.com.cn/problem/P4314|洛谷p4314]]
+=== 题意 ===
+给定一个长度为 $n$ 序列，支持下列操作：
+  - 询问区间 $[l,r]$ 的最大值
+  - 询问区间 $[l,r]$ 的历史最大值
+  - 对 $i\in [l,r],a_i=a_i+v$
+  - 对 $i\in [l,r],a_i=v$
+=== 题解 ===
+对加法操作，考虑维护区间当前加法懒标记和区间历史最大加法懒标记。对赋值操作，考虑维护区间当前赋值懒标记和区间历史最大赋值懒标记。
+考虑标记下放的本质，即将当前区间的所有操作序列添加到子区间操作序列的后面，同时维护该操作对答案的影响。一个策略为合并操作。
+发现将加法操作添加到加法操作后面可以直接叠加，可以合并为一个加法操作。
+将赋值操作添加到加法操作无法合并，留下一个赋值操作。
+将赋值操作添加到赋值操作后面直接覆盖即可，可以合并为一个赋值操作。
+将加法操作添加到赋值操作后面可以理解为更新上一次的赋值操作，最后合共为一个赋值操作。
+于是整个操作序列最后可以合并为一个加法操作和一个赋值操作。懒标记下放的同时维护历史最值即可，时间复杂度 $O(n+q\log n)$。
+<hidden 查看代码>
+<code cpp>
+int a[MAXN];
+int lef[MAXN<<2],rig[MAXN<<2],maxv[MAXN<<2],mmaxv[MAXN<<2];
+int lazy1[MAXN<<2],lazy2[MAXN<<2],mlazy1[MAXN<<2],mlazy2[MAXN<<2],has_set[MAXN<<2];
+void push_up(int k){
+	maxv[k]=max(maxv[k<<1],maxv[k<<1|1]);
+	mmaxv[k]=max(mmaxv[k<<1],mmaxv[k<<1|1]);
+}
+void push_set(int k,int v,int mv){
+	maxv[k]=v,mmaxv[k]=max(mmaxv[k],mv);
+	if(has_set[k]){
+		lazy2[k]=v;
+		mlazy2[k]=max(mlazy2[k],mv);
+	}
+	else{
+		has_set[k]=1;
+		lazy2[k]=v;
+		mlazy2[k]=mv;
+	}
+}
+void push_add(int k,int v,int mv){
+	if(has_set[k])return push_set(k,lazy2[k]+v,lazy2[k]+mv);
+	mmaxv[k]=max(mmaxv[k],maxv[k]+mv);
+	mlazy1[k]=max(mlazy1[k],lazy1[k]+mv);
+	maxv[k]+=v,lazy1[k]+=v;
+}
+void push_down(int k){
+	push_add(k<<1,lazy1[k],mlazy1[k]);
+	push_add(k<<1|1,lazy1[k],mlazy1[k]);
+	lazy1[k]=mlazy1[k]=0;
+	if(has_set[k]){
+		push_set(k<<1,lazy2[k],mlazy2[k]);
+		push_set(k<<1|1,lazy2[k],mlazy2[k]);
+		has_set[k]=0;
+	}
+}
+void build(int k,int L,int R){
+	lef[k]=L,rig[k]=R,lazy1[k]=mlazy1[k]=has_set[k]=0;
+	int M=L+R>>1;
+	if(L==R){
+		maxv[k]=mmaxv[k]=a[M];
+		return;
+	}
+	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,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_set(int k,int L,int R,int v){
+	if(L<=lef[k]&&rig[k]<=R)
+	return push_set(k,v,v);
+	push_down(k);
+	int mid=lef[k]+rig[k]>>1;
+	if(mid>=L)update_set(k<<1,L,R,v);
+	if(mid<R)update_set(k<<1|1,L,R,v);
+	push_up(k);
+}
+int query_max(int k,int L,int R){
+	if(L<=lef[k]&&rig[k]<=R)return maxv[k];
+	push_down(k);
+	int mid=lef[k]+rig[k]>>1,vl=-Inf,vr=-Inf;
+	if(mid>=L)vl=query_max(k<<1,L,R);
+	if(mid<R)vr=query_max(k<<1|1,L,R);
+	return max(vl,vr);
+}
+int query_mmax(int k,int L,int R){
+	if(L<=lef[k]&&rig[k]<=R)return mmaxv[k];
+	push_down(k);
+	int mid=lef[k]+rig[k]>>1,vl=-Inf,vr=-Inf;
+	if(mid>=L)vl=query_mmax(k<<1,L,R);
+	if(mid<R)vr=query_mmax(k<<1|1,L,R);
+	return max(vl,vr);
+}
+int main()
+{
+	int n=read_int();
+	_rep(i,1,n)a[i]=read_int();
+	build(1,1,n);
+	int q=read_int();
+	while(q--){
+		char opt=get_char();
+		int l=read_int(),r=read_int();
+		switch(opt){
+			case 'Q':
+				enter(query_max(1,l,r));
+				break;
+			case 'A':
+				enter(query_mmax(1,l,r));
+				break;
+			case 'P':
+				update_add(1,l,r,read_int());
+				break;
+			case 'C':
+				update_set(1,l,r,read_int());
+				break;
+		}
+	}
+	return 0;
+}
+</code>
+</hidden>
+==== 习题二 ====
+[[https://ac.nowcoder.com/acm/contest/7817/B|2020牛客国庆集训派对day1 B题]]
+=== 题意 ===
+给定序列 $A$。定义 $G(i,j)=\text{gcd}(a_i,a_{i+1}\cdots a_j),M(i,j)=\max(a_i,a_{i+1}\cdots a_j)$，求
+$$
+\sum_{i=1}^n\sum_{j=i}^nG(i,j)M(i,j)
+$$
+=== 题解 ===
+考虑计算 $\sum_{j=1}^iG(i,j)M(i,j)$ 的贡献。
+发现 $1\le j\le i$ 的 $G(i,j)$ 只有 $O(\log v)$ 个取值，同时有 $G(i,j)=\text{gcd}(G(i-1,j),a_i)$。
+于是可以 $O(\log n\log v)$ 维护所有不同的 $G(i,j)$。不同取值的 $G(i,j)$ 将 $[1,i]$ 划分为若干区间。
+又有 $M(i,j)=\max (M(i-1,j),a_i)$，于是可以吉司机线段树维护区间最值操作下的区间和。
+对每个被划分的区间直接查询求和即可，时间复杂度 $O(\log n\log v)$。于是总时间复杂 $O(n\log n\log v)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=2e5+5,Mod=1e9+7;
+int a[MAXN];
+int lef[MAXN<<2],rig[MAXN<<2],minv[MAXN<<2],minc[MAXN<<2],secv[MAXN<<2],lazy[MAXN<<2];
+LL sum[MAXN<<2];
+void push_up(int k){
+	sum[k]=(sum[k<<1]+sum[k<<1|1])%Mod;
+	if(minv[k<<1]==minv[k<<1|1]){
+		minv[k]=minv[k<<1];
+		minc[k]=minc[k<<1]+minc[k<<1|1];
+		secv[k]=min(secv[k<<1],secv[k<<1|1]);
+	}
+	else if(minv[k<<1]<minv[k<<1|1]){
+		minv[k]=minv[k<<1];
+		minc[k]=minc[k<<1];
+		secv[k]=min(secv[k<<1],minv[k<<1|1]);
+	}
+	else{
+		minv[k]=minv[k<<1|1];
+		minc[k]=minc[k<<1|1];
+		secv[k]=min(minv[k<<1],secv[k<<1|1]);
+	}
+}
+void push_tag(int k,int v){
+	if(v<=minv[k])return;
+	sum[k]=(sum[k]+1LL*minc[k]*(v-minv[k]))%Mod;
+	minv[k]=lazy[k]=v;
+}
+void push_down(int k){
+	if(~lazy[k]){
+		push_tag(k<<1,lazy[k]);
+		push_tag(k<<1|1,lazy[k]);
+		lazy[k]=-1;
+	}
+}
+void build(int k,int L,int R){
+	lef[k]=L,rig[k]=R,lazy[k]=-1;
+	if(L==R){
+		sum[k]=minv[k]=0;
+		secv[k]=2e9;
+		minc[k]=1;
+		return;
+	}
+	int M=L+R>>1;
+	build(k<<1,L,M);
+	build(k<<1|1,M+1,R);
+	push_up(k);
+}
+void update(int k,int L,int R,int v){
+	if(minv[k]>=v)return;
+	if(L<=lef[k]&&rig[k]<=R&&secv[k]>v)
+	return push_tag(k,v);
+	push_down(k);
+	int mid=lef[k]+rig[k]>>1;
+	if(mid>=L)update(k<<1,L,R,v);
+	if(mid<R)update(k<<1|1,L,R,v);
+	push_up(k);
+}
+int query_sum(int k,int L,int R){
+	if(L<=lef[k]&&rig[k]<=R)return sum[k];
+	push_down(k);
+	int mid=lef[k]+rig[k]>>1;
+	LL s=0;
+	if(mid>=L)s+=query_sum(k<<1,L,R);
+	if(mid<R)s+=query_sum(k<<1|1,L,R);
+	return s%Mod;
+}
+int gcd(int a,int b){
+	int t;
+	while(b){
+		t=b;
+		b=a%b;
+		a=t;
+	}
+	return a;
+}
+struct Node{
+	int v,pos;
+}Stack[MAXN],temp[MAXN];
+int main()
+{
+	int n=read_int();
+	build(1,1,n);
+	_rep(i,1,n)
+	a[i]=read_int();
+	int top=0;
+	Stack[top]=Node{0,0};
+	int ans=0;
+	_rep(i,1,n){
+		update(1,1,i,a[i]);
+		_rep(j,1,top)
+		Stack[j].v=gcd(Stack[j].v,a[i]);
+		Stack[++top]=Node{a[i],i};
+		_rep(i,1,top)
+		temp[i]=Stack[i];
+		int top2=top;
+		top=0;
+		_rep(i,1,top2){
+			while(temp[i].v==Stack[top].v)top--;
+			Stack[++top]=temp[i];
+		}
+		for(int i=top;i;i--)
+		ans=(ans+1LL*Stack[i].v*query_sum(1,Stack[i-1].pos+1,Stack[i].pos))%Mod;
+	}
+	enter(ans);
+	return 0;
+}
+</code>
+</hidden>
+==== 习题三 ====
+[[https://www.luogu.com.cn/problem/CF1290E|CF1290E]]
+=== 题意 ===
+给定 $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

用户工具

站点工具

差别

页面工具