2020-2021:teams:legal_string:jxm2001:吉司机线段树
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:吉司机线段树 [2020/10/01 19:54] jxm2001 [习题二] |
2020-2021:teams:legal_string:jxm2001:吉司机线段树 [2020/10/02 11:02] (当前版本) jxm2001 [习题三] |
||
|---|---|---|---|
| 行 431: | 行 431: | ||
| ==== 习题一 ==== | ==== 习题一 ==== | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/P4314|洛谷p4314]] | ||
| === 题意 === | === 题意 === | ||
| 行 703: | 行 705: | ||
| </hidden> | </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> | ||
2020-2021/teams/legal_string/jxm2001/吉司机线段树.1601553278.txt.gz · 最后更改: 2020/10/01 19:54 由 jxm2001
