vani有约会：线段树合并

线段树合并

• • • P1456 Monkey King
    • P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并
    • P1552 [APIO2012]派遣
    • CF1009F Dominant Indices
    • P4197 Peaks
    • P3521 [POI2011]ROT-Tree Rotations

P1456 Monkey King

链接：https://www.luogu.com.cn/problem/P1456

题意：给定 n 只猴子打 m 次架，每次询问两只猴子，选择它们所在集合中，战斗力最大的两只猴子，将它们的战斗力减半。输出这个减半之后的战斗力，然后将这两个集合合并。如果两只猴子已经在同一个集合，那么就输出 -1.

思路：用并查集维护集合关系。然后用 动态开点权值线段树 + 线段树合并来维护操作。

• 每次先查询 u 、v 是否在同一个集合。不在，则查询当前集合中的最大战斗力的两只猴子，然后删除战斗力，并插入原来战斗力的一半。然后将这两个集合合并。最后查询答案

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e5+5,tot=32768;int n,m;int root[maxn],st[maxn*40],ls[maxn*40],rs[maxn*40],no;int query(int rt,int L,int R){ if(!rt) return 0; if(L==R) return L; int mid=(L+R)>>1; if(st[rs[rt]]) return query(rs[rt],mid+1,R); else return query(ls[rt],L,mid);}void insert(int &rt,int pos,int L,int R){ if(!rt) rt=++no; st[rt]++; if(L==R) return; int mid=(L+R)>>1; if(pos<=mid) insert(ls[rt],pos,L,mid); else insert(rs[rt],pos,mid+1,R);}void del(int &rt,int pos,int L,int R){ if(!rt) return; st[rt]--; if(L==R) return; int mid=(L+R)>>1; if(pos<=mid) return del(ls[rt],pos,L,mid); else return del(rs[rt],pos,mid+1,R);}int merge(int rt1,int rt2,int L,int R){ if(!rt1||!rt2) return rt1?rt1:rt2; int rt=rt1; st[rt]+=st[rt2]; int mid=(L+R)>>1; ls[rt]=merge(ls[rt1],ls[rt2],L,mid); rs[rt]=merge(rs[rt1],rs[rt2],mid+1,R); return rt;}int pa[maxn];int find(int x){ return x==pa[x]?x:pa[x]=find(pa[x]);}int main(){ while(~scanf("%d",&n)) { memset(root,0,sizeof(root)); for(int i=0; i<=no; ++i) st[i]=ls[i]=rs[i]=0; no=0; for(int i=1; i<=n; ++i) { int x; scanf("%d",&x); pa[i]=i; insert(root[i],x,1,tot); } scanf("%d",&m); int u,v,ru,rv; while(m--) { scanf("%d%d",&u,&v); ru=find(u); rv=find(v); if(ru==rv) puts("-1"); else { u=query(root[ru],1,tot); v=query(root[rv],1,tot); del(root[ru],u,1,tot); del(root[rv],v,1,tot); insert(root[ru],u/2,1,tot); insert(root[rv],v/2,1,tot); pa[ru]=rv; root[rv]=merge(root[ru],root[rv],1,tot); printf("%d\n",query(root[rv],1,tot)); } } } return 0;}

P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并

链接：https://www.luogu.com.cn/problem/P4556

题意：首先村落里的一共有 n 座房屋，并形成一个树状结构。然后救济粮分 mm 次发放，每次选择两个房屋 ( x , y ) (x, y) (x,y)，然后对于 x 到 y 的路径上(含 x 和 y)每座房子里发放一袋 z 类型的救济粮。当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

思路：树上差分前缀和，维护 sz 和 每个点的最大值。

• 先访问到叶节点，然后差分回溯

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e5+5,tot=1e5;int n,m;vector<int> e[maxn];int visit[maxn],ans[maxn];int root[maxn],ls[maxn*70],rs[maxn*70],no;struct ST{ int cnt,sz;} st[maxn*70];void update(int &rt,int pos,int L,int R,int val){ if(!rt) rt=++no; if(L==R) { st[rt].sz+=val; st[rt].cnt+=val; return; } int mid=(L+R)>>1; if(pos<=mid) update(ls[rt],pos,L,mid,val); else update(rs[rt],pos,mid+1,R,val); st[rt].sz=st[ls[rt]].sz+st[rs[rt]].sz; st[rt].cnt=max(st[ls[rt]].cnt,st[rs[rt]].cnt);}int depth[maxn],fa[maxn][22];void dfs1(int u,int f){ depth[u]=depth[f]+1; fa[u][0]=f; for(int i=1; i<=20; ++i) fa[u][i]=fa[fa[u][i-1]][i-1]; for(auto v: e[u]) { if(v==f) continue; dfs1(v,u); }}int lca(int u,int v){ if(depth[u]<depth[v]) swap(u,v); int dis=depth[u]-depth[v]; for(int i=0; (1<<i)<=dis; ++i) if(dis>>i&1) u=fa[u][i]; if(u==v) return u; for(int i=20; i>=0; --i) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0];}int merge(int rt1,int rt2,int L,int R){ if(!rt1||!rt2) return rt1?rt1:rt2; int rt=rt1; if(L==R) { st[rt].sz+=st[rt2].sz; st[rt].cnt+=st[rt2].cnt; return rt; } int mid=(L+R)>>1; ls[rt]=merge(ls[rt1],ls[rt2],L,mid); rs[rt]=merge(rs[rt1],rs[rt2],mid+1,R); st[rt].sz=st[ls[rt]].sz+st[rs[rt]].sz; st[rt].cnt=max(st[ls[rt]].cnt,st[rs[rt]].cnt); return rt;}int query(int rt,int L,int R){ if(!rt) return 0; if(L==R) return st[rt].cnt?L:0; int mid=(L+R)>>1; if(st[ls[rt]].cnt>=st[rs[rt]].cnt) return query(ls[rt],L,mid); else return query(rs[rt],mid+1,R);}void dfs2(int u,int f){ visit[u]=1; for(auto v: e[u]) { if(v==f) continue; dfs2(v,u); root[u]=merge(root[u],root[v],1,tot); } if(root[u]) ans[u]=query(root[u],1,tot);}int main(){ scanf("%d%d",&n,&m); for(int i=1; i<=n-1; ++i) { int u,v; scanf("%d%d",&u,&v); e[u].push_back(v); e[v].push_back(u); } dfs1(1,0); int u,v,w; while(m--) { scanf("%d%d%d",&u,&v,&w); int x=lca(u,v); int fx=fa[x][0]; update(root[u],w,1,tot,1); update(root[v],w,1,tot,1); update(root[x],w,1,tot,-1); if(fx) update(root[fx],w,1,tot,-1); } dfs2(1,0); for(int i=1; i<=n; ++i) printf("%d\n",ans[i]); return 0;}

P1552 [APIO2012]派遣

链接：https://www.luogu.com.cn/problem/P1552

题意：给定一棵树，每个点有点权 c i c_i ci​ 和 l i l_i li​ ，可以在每棵子树内选择最大的点数使得 c i c_i ci​ 之和不超过 m m m 。设选择的点数为 c n t cnt cnt ，问 l i × c n t l_i \times cnt li​×cnt 的最大值是多少。

思路：

• 对每个点开一棵权值线段树：维护 cnt 和 sum ，表示当前值域区间的个数和区间和
• 从叶到根，先合并当前点子树的所有信息，然后查询即可

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e5+5;int n,m,tot;ll C[maxn],L[maxn];vector<int> allx,e[maxn];int root[maxn],ls[maxn*40],rs[maxn*40],no;struct Node{ int cnt; ll sum;} st[maxn*40];void update(int &rt,int pos,int L,int R){ if(!rt) rt=++no; if(L==R) { st[rt].cnt++; st[rt].sum+=allx[pos-1]; return; } int mid=(L+R)>>1; if(pos<=mid) update(ls[rt],pos,L,mid); if(pos>mid) update(rs[rt],pos,mid+1,R); st[rt].cnt=st[ls[rt]].cnt+st[rs[rt]].cnt; st[rt].sum=st[ls[rt]].sum+st[rs[rt]].sum;}int query(int rt,int L,int R,int val){ if(!rt) return 0; if(L==R) return min(st[rt].cnt,val/allx[L-1]); int mid=(L+R)>>1; if(st[ls[rt]].sum>=val) return query(ls[rt],L,mid,val); else return st[ls[rt]].cnt+query(rs[rt],mid+1,R,val-st[ls[rt]].sum);}int merge(int rt1,int rt2,int L,int R){ if(!rt1||!rt2) return rt1?rt1:rt2; int rt=rt1; if(L==R) { st[rt].cnt+=st[rt2].cnt; st[rt].sum+=st[rt2].sum; return rt; } int mid=(L+R)>>1; ls[rt]=merge(ls[rt1],ls[rt2],L,mid); rs[rt]=merge(rs[rt1],rs[rt2],mid+1,R); st[rt].cnt=st[ls[rt]].cnt+st[rs[rt]].cnt; st[rt].sum=st[ls[rt]].sum+st[rs[rt]].sum; return rt;}ll ans=0;void dfs(int u){ for(auto v: e[u]) { dfs(v); root[u]=merge(root[u],root[v],1,tot); } if(root[u]) ans=max(ans,1ll*L[u]*query(root[u],1,tot,m));}int main(){ scanf("%d%d",&n,&m); int rt; for(int i=1; i<=n; ++i) { int u; scanf("%d%lld%lld",&u,&C[i],&L[i]); e[u].push_back(i); if(u==0) rt=i; allx.push_back(C[i]); } sort(allx.begin(),allx.end()); allx.resize(unique(allx.begin(),allx.end())-allx.begin()); tot=allx.size(); for(int i=1; i<=n; ++i) { int pos=lower_bound(allx.begin(),allx.end(),C[i])-allx.begin()+1; update(root[i],pos,1,tot); } dfs(rt); printf("%lld\n",ans); return 0;}

CF1009F Dominant Indices

链接：https://www.luogu.com.cn/problem/CF1009F

题意：给定一棵以 1 为根，n 个节点的树。设 d(u,x) 为 u 子树中到 u 距离为 x 的节点数。 对于每个点，求一个最小的 k，使得 d(u,k) 最大。

思路：

• 每个点根据深度建立权值线段树。查询深度出现次数最多的且最小的k。
• 从叶到根，一遍更新答案一遍向上合并
• 注意一下深度，根节点深度为 1 ，有 n 次更新，空间复杂度为 n l o g 2 ( m a x   d e p t h ) n log2(max~depth) nlog2(max depth)

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e6+5,tot=1e6;int n;vector<int> e[maxn];int depth[maxn],ans[maxn];int root[maxn],ls[maxn*25],rs[maxn*25],st[maxn*25],no;void update(int &rt,int pos,int L,int R){ if(!rt) rt=++no; if(L==R) { st[rt]++; return; } int mid=(L+R)>>1; if(pos<=mid) update(ls[rt],pos,L,mid); else update(rs[rt],pos,mid+1,R); st[rt]=max(st[ls[rt]],st[rs[rt]]);}int query(int rt,int L,int R){ if(!rt) return 0; if(L==R) return L; int mid=(L+R)>>1; if(st[ls[rt]]>=st[rs[rt]]) return query(ls[rt],L,mid); else return query(rs[rt],mid+1,R);}int merge(int rt1,int rt2,int L,int R){ if(!rt1||!rt2) return rt1?rt1:rt2; int rt=rt1; if(L==R) { st[rt]+=st[rt2]; return rt; } int mid=(L+R)>>1; ls[rt]=merge(ls[rt1],ls[rt2],L,mid); rs[rt]=merge(rs[rt1],rs[rt2],mid+1,R); st[rt]=max(st[ls[rt]],st[rs[rt]]); return rt;}void dfs(int u,int fa){ depth[u]=depth[fa]+1; for(auto v: e[u]) { if(v==fa) continue; dfs(v,u); root[u]=merge(root[u],root[v],1,tot); } update(root[u],depth[u],1,tot); ans[u]=query(root[u],1,tot);}int main(){ scanf("%d",&n); for(int i=1; i<=n-1; ++i) { int u,v; scanf("%d%d",&u,&v); e[u].push_back(v); e[v].push_back(u); } dfs(1,0); for(int i=1; i<=n; ++i) printf("%d\n",ans[i]-depth[i]); return 0;}

P4197 Peaks

链接：https://www.luogu.com.cn/problem/P4197

题意：在 Bytemountains 有 n n n 座山峰，每座山峰有他的高度 h i h_i hi​ 。有些山峰之间有双向道路相连，共 m 条路径，每条路径有一个困难值 c i c_i ci​，这个值越大表示越难走。 现在有 q q q 组询问，每组询问询问从点 v 开始只经过困难值小于等于 x 的路径所能到达的山峰中第 k k k 高的山峰，如果无解输出 − 1 -1 −1

对于 100% 的数据， n ≤ 1 0 5 ， 0 ≤ m , q ≤ 5 × 1 0 5 ， h i , c , x ≤ 1 0 9 n \le 10^5，0 \le m,q \le 5\times 10^5，h_i,c,x \le 10^9 n≤105，0≤m,q≤5×105，hi​,c,x≤109

思路：

• 边根据 w 排序，询问根据 x 排序。然后更新并查集、合并线段树。
• 然后查询第 k 大就好了

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e5+5,maxm=5e5+5;int n,m,q,tot;int h[maxn],ans[maxm];vector<int> allh;struct Opt{ int v,x,k,id; bool operator<(const Opt &b) const { return x<b.x; }} opt[maxm];struct Edge{ int u,v,w; bool operator<(const Edge& b) const { return w<b.w; }} e[maxm];int pa[maxn],sz[maxn];int find(int x){ return x==pa[x]?x:pa[x]=find(pa[x]);}int root[maxn],ls[maxn*25],rs[maxn*25],st[maxn*25],no;void update(int &rt,int pos,int L,int R){ if(!rt) rt=++no; st[rt]++; if(L==R) return; int mid=(L+R)>>1; if(pos<=mid) update(ls[rt],pos,L,mid); else update(rs[rt],pos,mid+1,R);}int merge(int rt1,int rt2,int L,int R){ if(!rt1||!rt2) return rt1|rt2; int rt=rt1; if(L==R) { st[rt]+=st[rt2]; return rt; } int mid=(L+R)>>1; ls[rt]=merge(ls[rt1],ls[rt2],L,mid); rs[rt]=merge(rs[rt1],rs[rt2],mid+1,R); st[rt]=st[ls[rt]]+st[rs[rt]]; return rt;}int query(int rt,int k,int L,int R){ if(L==R) return L; int mid=(L+R)>>1; if(st[rs[rt]]>=k) return query(rs[rt],k,mid+1,R); else return query(ls[rt],k-st[rs[rt]],L,mid);}int main(){ scanf("%d%d%d",&n,&m,&q); for(int i=1; i<=n; ++i) { scanf("%d",&h[i]); allh.push_back(h[i]); pa[i]=i; sz[i]=1; } sort(allh.begin(),allh.end()); allh.resize(unique(allh.begin(),allh.end())-allh.begin()); tot=allh.size(); for(int i=1; i<=n; ++i) { int p=lower_bound(allh.begin(),allh.end(),h[i])-allh.begin()+1; update(root[i],p,1,tot); } for(int i=1; i<=m; ++i) { int u,v,w; scanf("%d%d%d",&u,&v,&w); e[i]= {u,v,w}; } sort(e+1,e+1+m); for(int i=1; i<=q; ++i) { int v,x,k; scanf("%d%d%d",&v,&x,&k); opt[i]= {v,x,k,i}; } sort(opt+1,opt+1+q); int pos=1; for(int i=1; i<=q; ++i) { while(pos<=m&&e[pos].w<=opt[i].x) { int u=e[pos].u,v=e[pos].v; int ru=find(u),rv=find(v); pos++; if(ru==rv) continue; pa[rv]=ru; sz[ru]+=sz[rv]; root[ru]=merge(root[ru],root[rv],1,tot); } int v=opt[i].v; if(sz[find(v)]<opt[i].k) ans[opt[i].id]=-1; else { int p=query(root[find(v)],opt[i].k,1,tot); ans[opt[i].id]=allh[p-1]; } } for(int i=1; i<=q; ++i) printf("%d\n",ans[i]); return 0;}

P3521 [POI2011]ROT-Tree Rotations

链接：https://www.luogu.com.cn/problem/P3521

题意：给定一棵有 n 个叶节点的二叉树，每个叶节点带有权值 p_i ，构成了一个 n 的排列。保证除了叶节点之外的所有节点左右孩子都存在。现在你可以交换任意节点的左右孩子，交换任意次。问最终得到的叶节点前序遍历得到的排列的最小逆序对是多少。

思路：

• 每一个节点与节点直接是相互独立的。可以对每一个节点开一个权值线段树，在向上合并的过程中统计逆序对。

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=2e5+5,tot=2e5;int n;int ls[maxn*20],rs[maxn*20],st[maxn*20],no;void update(int &rt,int pos,int L,int R){ if(!rt) rt=++no; if(L==R) { st[rt]++; return; } int mid=(L+R)>>1; if(pos<=mid) update(ls[rt],pos,L,mid); else update(rs[rt],pos,mid+1,R); st[rt]=st[ls[rt]]+st[rs[rt]];}ll cnt1,cnt2,ans;int merge(int rt1,int rt2,int L,int R){ if(!rt1||!rt2) return rt1|rt2; int rt=rt1; if(L==R) { st[rt]+=st[rt2]; return rt; } cnt1+=1ll*st[ls[rt1]]*st[rs[rt2]]; cnt2+=1ll*st[rs[rt1]]*st[ls[rt2]]; int mid=(L+R)>>1; ls[rt]=merge(ls[rt1],ls[rt2],L,mid); rs[rt]=merge(rs[rt1],rs[rt2],mid+1,R); st[rt]=st[ls[rt]]+st[rs[rt]]; return rt;}void dfs(int &rt){ int u=0,v=0,val; scanf("%d",&val); if(val==0) { dfs(u); dfs(v); cnt1=cnt2=0; rt=merge(u,v,1,tot); ans+=min(cnt1,cnt2); } else update(rt,val,1,tot);}int main(){ scanf("%d",&n); int rt=0; ans=0; dfs(rt); printf("%lld\n",ans); return 0;}