HDU 4366 Successor（树链剖分+zkw线段树+扫描线）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=4366
【题目大意】
有一个公司，每个员工都有一个上司，所有的人呈树状关系，现在给出每个人的忠诚值和能力值，每次当一个人被辞退的时候，会由能力值大于他的下属中忠诚值最高的去代替他的位置，下属的关系是可传递的，上司的编号一定大于下属。现在给出一些询问，问如果一个人辞退将会由哪个人代替他，所有人的忠诚值都是唯一的。
【题解】
现在这道题就相当于是从子树中找出key1值大于子树根节点且key2值最高的子节点。首先，单纯考虑key2值最高的问题，发现只要树链剖分一下线段树维护RMQ即可，对于key1值的处理问题，我们考虑扫描线算法，将节点按照key1值降序扫描，那么在顺序统计答案的时候，只会统计到大于等于key1值的子节点，特别的，为处理等于的问题，在key1值相同的情况下，优先扫描编号小的节点，就不会出现统计了key1值相同的子节点的情况了。因为忠诚值唯一，所以只需用zkw线段树维护key2单值，在忠诚值和编号之间做一个单映射就可以得到需要输出的答案。
【代码】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | #include <cstdio>#include <algorithm>#include <climits>#include <cstring>using namespace std;const int N=100010;int tot,x,d[N],num[N],ed=0,u,w,n,m,i;int v[N],vis[N],f[N],g[N],nxt[N],size[N],son[N],st[N],en[N],dfn,top[N],t;void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}void dfs(int x){ size[x]=1; for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]){ f[v[i]]=x,d[v[i]]=d[x]+1; dfs(v[i]),size[x]+=size[v[i]]; if(size[v[i]]>size[son[x]])son[x]=v[i]; }}void dfs2(int x,int y){ if(x==-1)return; st[x]=++dfn;top[x]=y; if(son[x])dfs2(son[x],y); for(int i=g[x];i;i=nxt[i])if(v[i]!=son[x]&&v[i]!=f[x])dfs2(v[i],v[i]); en[x]=dfn;}void init(){ memset(g,dfn=ed=tot=0,sizeof(g)); memset(v,0,sizeof(v)); memset(nxt,0,sizeof(nxt)); memset(son,-1,sizeof(son));}struct person{int id,a,b,c;}p[N];bool cmp(person a,person b){return a.c==b.c?a.id<b.id:a.c>b.c;}int M,Cas,T[N*4],ans[N],Hash[1000005];int main(){ scanf("%d",&Cas); while(Cas--){ init(); scanf("%d%d",&n,&m); for(int i=2;i<=n;i++){ scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c); add(p[i].a+1,i); p[i].id=i; Hash[p[i].b]=i-1; }dfs(1);dfs2(1,1); sort(p+2,p+n+1,cmp); memset(T,-1,sizeof(T)); for(M=1;M<(dfn+2);M<<=1); for(int i=2;i<=n;i++){ int Ans=-1; int x=st[p[i].id]+M-1,y=en[p[i].id]+M+1; while(x^y^1>0){ if(~x&1)Ans=max(Ans,T[x+1]); if(y&1)Ans=max(Ans,T[y-1]); x>>=1;y>>=1; }if(Ans==-1)ans[p[i].id-1]=-1; else ans[p[i].id-1]=Hash[Ans]; T[M+st[p[i].id]]=p[i].b; for(x=(M+st[p[i].id])/2;x;x/=2)T[x]=max(T[x<<1],T[(x<<1)^1]); }while(m--){ int x; scanf("%d",&x); printf("%d\n",ans[x]); } }return 0;} |
评论 (0)
