国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > HDU 3078 LCA转RMQ

HDU 3078 LCA转RMQ

来源:程序员人生   发布时间:2016-07-01 15:52:54 阅读次数:2209次

点击打开链接

题意:给1个树和每一个点的权值,然后m询问a b c,若a为0,则将b点的权值改成c,否则问你的是从b走到c的所有权值中的第a大的数,若不足a个输出那个

思路:就是用LCA转RMQ就能够了,每次的询问就是直接找到它们的最近公共先人,然后两个点都向上找到最近公共先人,沿途的所有的点全部记录下来,最后排个序输出第K大就好了

#include <vector> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int maxn=80010; vector<int>G[maxn]; bool vis[maxn]; int L[maxn*2],E[maxn*2],H[maxn],dis[maxn],dp[2*maxn][20],num[maxn],pre[maxn]; //H为每一个元素第1次出现的位置,E为dfs遍历的序号,L为深度,dis为每一个点到根的距离 //dp[i][j]代表的是i到j深度最小的位置 int k,n; void dfs(int t,int deep){ k++;E[k]=t;L[k]=deep;H[t]=k;//遍用时叶子在E中只会出现1次,而非叶子节点会出现屡次 for(unsigned int i=0;i<G[t].size();i++){ int tt=G[t][i]; if(!vis[tt]){//出现过就不再继续,保证dis的大小和H第1次出现的位置 pre[tt]=t; vis[tt]=1; dfs(tt,deep+1); k++;E[k]=t;L[k]=deep; } } } void RMQ_init(){//RMQ的ST算法 for(int i=1;i<=2*n⑴;i++) dp[i][0]=i; for(int i=1;(1<<i)<=2*n⑴;i++){ for(int j=1;j+(1<<i)⑴<=2*n⑴;j++){ if(L[dp[j][i⑴]]<L[dp[j+(1<<(i⑴))][i⑴]]) dp[j][i]=dp[j][i⑴]; else dp[j][i]=dp[j+(1<<(i⑴))][i⑴]; } } } int RMQ(int le,int ri){ le=H[le];ri=H[ri];//找到第1次出现的位置 if(le>ri) swap(le,ri);//le大于ri说明ri在le之前出现,交换 int kk=0; while((1<<(kk+1))<=ri-le+1) kk++; if(L[dp[le][kk]]<L[dp[ri-(1<<kk)+1][kk]]) return E[dp[le][kk]]; else return E[dp[ri-(1<<kk)+1][kk]];//返回的是dp位置的值 } int tmp[maxn]; int main(){ int q,a,b,c; while(scanf("%d%d",&n,&q)!=⑴){ for(int i=1;i<=n;i++) scanf("%d",&num[i]); for(int i=0;i<maxn;i++) G[i].clear(); memset(vis,0,sizeof(vis)); for(int i=0;i<n⑴;i++){ scanf("%d%d",&a,&b); G[a].push_back(b); G[b].push_back(a); } k=0;vis[1]=1; dfs(1,1);RMQ_init(); while(q--){ scanf("%d%d%d",&a,&b,&c); if(a==0){ num[b]=c;continue; } int en=RMQ(b,c); int sum=0; while(b!=en){ tmp[sum++]=num[b]; b=pre[b]; } while(c!=en){ tmp[sum++]=num[c]; c=pre[c]; } tmp[sum++]=num[en]; if(sum<a) printf("invalid request!\n"); else{ sort(tmp,tmp+sum); printf("%d\n",tmp[sum-a]); } } } return 0; }

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生