线段树合并"/>
EC Round 33 F. Subtree Minimum Query 主席树/线段树合并
这题非常好!!!
主席树版本
很简单的题目,给一个按照指定节点的树,树上有点权,你需要回答给定节点的子树中,和其距离不超过k的节点中,权值最小的。
肯定首先一想,按照dfs序列建树,然后按照深度为下标,建立主席树,那么我们通过主席树相间得到区间状态,但是很不幸,区间最值不能通过减去历史版本的主席树得到。
考虑照深度建立主席树,按照dfs下标建立,貌似可以耶!!!
我们直接查询当前节点往下k深度的主席树,它保存的就是从深度为1-到深度为deep[p]+k深度的所有节点的dfs序对应的点权值
我们查询子树对应区间的dfs序的最小值,就是答案啦!!!
主席树的话,不建议最开始去建树初始化,本来就是动态开点了,不用这么麻烦,这个题也是一样,我们建立主席树的时候,直接写一个析构函数初始化最大值即可
不用再buildtree了2333。。。
#include<bits/stdc++.h> #define LL long long using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 1e5+6; struct node{int l,r;int w;node(){w=INF;} }tree[maxn*40]; struct ID{int pre,bac; }id[maxn]; int cnt,tot,dfsorder,mxdep; int root[maxn*2]; int a[maxn],deepth[maxn]; int ver[maxn*2],Next[maxn*2],head[maxn]; int mp[maxn*2]; queue<int>q; int n,r; void add(int x,int y){ver[++tot]=y;Next[tot]=head[x];head[x]=tot;ver[++tot]=x;Next[tot]=head[y];head[y]=tot; } void dfs(int u,int fa){deepth[u]=deepth[fa]+1;id[u].pre=++dfsorder;mxdep=max(mxdep,deepth[u]);for(int i=head[u];i;i=Next[i]){int v=ver[i];if(v==fa)continue;dfs(v,u);}id[u].bac=dfsorder; }void inserts(int l,int r,int pre,int &now,int pos,int w){now=++cnt;tree[now]=tree[pre];tree[now].w=min(tree[now].w,w);if(l==r){return;}int mid=(l+r)>>1;if(pos<=mid){inserts(l,mid,tree[pre].l,tree[now].l,pos,w);}else {inserts(mid+1,r,tree[pre].r,tree[now].r,pos,w);} } int query(int rt,int l,int r,int ql,int qr){if(ql<=l && r<=qr){return tree[rt].w;}int mid=(l+r)>>1;if (qr<=mid){return query(tree[rt].l,l,mid,ql,qr);}else if(ql>mid){return query(tree[rt].r,mid+1,r,ql,qr);}else {return min(query(tree[rt].l,l,mid,ql,mid),query(tree[rt].r,mid+1,r,mid+1,qr));} } void bfs(int s){q.push(s);int tmp=0;while(q.size()){int now=q.front();q.pop();inserts(1,2*n,root[tmp],root[tmp+1],id[now].pre,a[now]);mp[deepth[now]]=++tmp;for (int i=head[now];i;i=Next[i]){int nex=ver[i];if(deepth[nex]==deepth[now]+1){q.push(nex);}}} } int main(){int uu,vv;while(~scanf("%d%d",&n,&r)){tot=0;cnt=0;dfsorder=0;mxdep=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for (int i=1;i<=n-1;i++){scanf("%d%d",&uu,&vv);add(uu,vv);}dfs(r,0);bfs(r);int op;int p,q;int ans=0;scanf("%d",&op);while(op--){scanf("%d%d",&p,&q);p=(p+ans)%n+1,q=(q+ans)%n;ans=query(root[mp[min(deepth[p]+q,mxdep)]],1,n*2,id[p].pre,id[p].bac);printf("%d\n",ans);}}return 0; }
线段树合并方法
在机房搞搞瞎搞了半天,看了半天没怎么懂线段树合并,属实菜。。。
最后再瞄了一眼,嗯,貌似懂了,不就是从每个节点都新建一个线段树,然后两个树,暴力对这两个线段树的每个节点,都去 暴力比较取最小值后,再拆掉以前的节点,用新建节点保存合并之后的信息,然后父亲节点的线段树得到儿子节点的信息。然后?然后就没了哈哈哈哈。
然后这道题就变成一道模版题了,子树的信息可以通过合并得到,而线段树保存的就是以深度为下标的儿子节点的点权最小值。询问的时候,我们只需要询问当前节点的线段树,其线段树内部就包含了儿子节点的信息,然后我们在给定的深度区间进行区间询问最小值,就能得到答案。真~模版题,注意这种线段树合并,由于每个节点都要开线段树,大佬说空间接近o(n*logn)所以线段树还是*40吧。
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int INF = 0x3f3f3f3f; const int maxx = 1e5+6; struct node{int l,r;int w;node(){w=INF;} }tree[maxx*40]; int cnt,tot,maxdeep; int root[maxx]; int deepth[maxx],ver[maxx*2],Next[maxx*2],head[maxx]; int a[maxx]; int n,r; void add(int x,int y){ver[++tot]=y;Next[tot]=head[x];head[x]=tot;ver[++tot]=x;Next[tot]=head[y];head[y]=tot; } void inserts(int &rt,int l,int r,int pos,int w){rt=++cnt;tree[rt].w=min(tree[rt].w,w);if(l==r){return ;}int mid=(l+r)>>1;if(pos<=mid)inserts(tree[rt].l,l,mid,pos,w);else inserts(tree[rt].r,mid+1,r,pos,w); } int merge(int x,int y){if(!x||!y){return x+y;}int tmp=++cnt;tree[tmp].l=merge(tree[x].l,tree[y].l);tree[tmp].r=merge(tree[x].r,tree[y].r);tree[tmp].w=min(tree[x].w,tree[y].w);return tmp; } int query(int rt,int l,int r,int ql,int qr){if(ql<=l && r<=qr){return tree[rt].w;}int mid=(l+r)>>1;if(qr<=mid){return query(tree[rt].l,l,mid,ql,qr);}else if(ql>mid){return query(tree[rt].r,mid+1,r,ql,qr);}else{return min(query(tree[rt].l,l,mid,ql,qr),query(tree[rt].r,mid+1,r,ql,qr));} } void dfs(int u,int fa){deepth[u]=deepth[fa]+1;maxdeep=max(maxdeep,deepth[u]);inserts(root[u],1,n,deepth[u],a[u]);for (int i=head[u];i;i=Next[i]){int v=ver[i];if(v==fa)continue;dfs(v,u);root[u]=merge(root[u],root[v]);} } int main(){int uu,vv;while(~scanf("%d%d",&n,&r)){maxdeep=0;cnt=0;tot=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<n;i++){scanf("%d%d",&uu,&vv);add(uu,vv);}int op;scanf("%d",&op);dfs(r,0);int ans=0;int p,q;while(op--){scanf("%d%d",&p,&q);p=(p+ans)%n+1,q=(q+ans)%n;ans=query(root[p],1,n,deepth[p],min(deepth[p]+q,n));printf("%d\n",ans);}}return 0; }
转载于:.html
更多推荐
EC Round 33 F. Subtree Minimum Query 主席树/线段树合并
发布评论