EC Round 33 F. Subtree Minimum Query 主席树/线段树合并

线段树合并"/>

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