RMQ问题的在线ST算法

VIJOS 1514

#include <cstdio> #include <algorithm> #include <cmath> using namespace std; int n,m,a,b,dp[201000][30],s[201000]; void init_RMQ(){ for(int i=1;i<=n;i++) dp[i][0]=s[i]; for(int j=1;(1<<j)<=n;j++) for(int i=1;i<=n;i++) dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); return; } int query_RMQ(int l,int r){ int k=log(r-l+1)/log(2.0); return max(dp[l][k],dp[r-(1<<k)+1][k]); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&s[i]); init_RMQ(); scanf("%d",&m); while(m--){ scanf("%d%d",&a,&b); printf("%d\n",query_RMQ(a,b)); } return 0; } //记住dp[i][0]=s[i] //dp[i][j]=min/max{dp[i][j-1],dp[i+(1<<j-1)][j-1]} //设k=log2(r-l+1) //要查询的结果为min/max{dp[l][k],dp[r-(1<<k)+1][k]}

Tarjan（离线求LCA）

#include <cstdio> #include <algorithm> #include <cstring> #define maxn 50000 struct qu{ int from,to; }q[maxn]; int m,n,s,cntq=0; int g[maxn][1000]; int fa[maxn],ancestor[maxn]; bool vis[maxn]; int find(int x){ return fa[x]==x ? x : fa[x]=find(fa[x]); } void lca(int u,int p){ ancestor[find(u)]=u; vis[u]=1; for(int i=1;i<=g[u][0];i++) if(g[u][i]!=p){ lca(g[u][i],u); fa[find(g[u][i])]=find(u); ancestor[find(u)]=u; } for(int i=1;i<=cntq;i++){ int qa=q[i].from,qb=q[i].to; if(qa==u&&vis[qb]) printf("%d\n",ancestor[find(qb)]); else if(qb==u&&vis[qa]) printf("%d\n",ancestor[find(qa)]); } return; } int main(){ scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=n;i++) fa[i]=ancestor[i]=i; cntq=m; for(int i=1;i<n;i++){ int x,y; scanf("%d%d",&x,&y); g[x][++g[x][0]]=y; g[y][++g[y][0]]=x; } for(int i=1;i<=m;i++){ scanf("%d%d",&q[i].from,&q[i].to); } lca(s,-1); return 0; }

VIJOS 1460（我也不知道是不是Tarjan，反正dfs跑一遍就过了）

#include <cstdio> #include <algorithm> #include <cstring> #define maxn 100100 int cnt,ans1=0,head[maxn],k,q; long long dist[maxn],fa[maxn],ans2=0; struct edge{ int to,next,val; }edges[maxn]; void add(int u,int v,int val){ edges[++cnt].to=v; edges[cnt].val=val; edges[cnt].next=head[u]; head[u]=cnt; }//head[u]代表以u出发的第一条边的编号，edge[head[u]就是这条边 //把i++换成edge[i].next //for(int i=head[u];i;i=edge[i].next) int n,m,a,b,t; void dfs(int rt,int pa,int dis){ fa[rt]=pa; dist[rt]=dis; for(int i=head[rt];i;i=edges[i].next){ int cur=edges[i].to; if(cur==pa) continue; dfs(cur,rt,dis+edges[i].val); } } bool find(int x,int y){ //寻找x的祖先中有没有y if(fa[x]==y) return 1; if(fa[x]==1) return 0; return find(fa[x],y); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<n;i++){ scanf("%d%d%d",&a,&b,&t); add(a,b,t); add(b,a,t); } dfs(1,1,0); for(int i=1;i<=m;i++){ scanf("%d%d",&k,&q); if(find(q,k)){ ans1++; ans2+=(dist[q]-dist[k]); } } printf("%d\n%lld",ans1,ans2); return 0; }

解法2：用倍增求LCA

#include <cstdio> #include <algorithm> #include <cstring> #define maxn 100100 using namespace std; int cnt,ans1=0,head[maxn],k,q; long long dist[maxn],p[maxn][20],dep[maxn],ans2=0; struct edge{ int to,next,val; }edges[maxn]; void add(int u,int v,int val){ edges[++cnt].to=v; edges[cnt].val=val; edges[cnt].next=head[u]; head[u]=cnt; }//head[u]代表以u出发的第一条边的编号，edge[head[u]就是这条边 //把i++换成edge[i].next //for(int i=head[u];i;i=edge[i].next) int n,m,a,b,t; void dfs(int rt,int father,int dis){ dist[rt]=dis; for(int i=head[rt];i!=0;i=edges[i].next){ if(!dep[edges[i].to]&&edges[i].to!=father){ dep[edges[i].to]=dep[rt]+1; p[edges[i].to][0]=rt; dfs(edges[i].to,rt,dis+edges[i].val); } } } void init_bz(){ for(int j=1;(1<<j)<=n;j++) for(int i=1;i<=n;i++) if(p[i][j-1]!=-1) p[i][j]=p[p[i][j-1]][j-1]; return; } int LCA(int a,int b){ int i,j; if(dep[a]<dep[b]) swap(a,b); for(i=0;(1<<i)<=dep[a];i++);i--; for(j=i;j>=0;j--) if(dep[a]-(1<<j)>=dep[b]) a=p[a][j]; if(a==b) return a; for(j=i;j>=0;j--) if(p[a][j]!=-1&&p[a][j]!=p[b][j]){ a=p[a][j]; b=p[b][j]; } return p[a][0]; } int main(){ scanf("%d%d",&n,&m); memset(p,-1,sizeof(p)); memset(dep,0,sizeof(dep)); memset(head,0,sizeof(head)); for(int i=1;i<n;i++){ scanf("%d%d%d",&a,&b,&t); add(a,b,t); add(b,a,t); } dfs(1,1,0); dep[1]=0; p[1][0]=1; init_bz(); for(int i=1;i<=m;i++){ scanf("%d%d",&k,&q); int temp=LCA(k,q); if(k==temp){ ans1++; ans2+=dist[q]-dist[k]; } } printf("%d\n%lld",ans1,ans2); return 0; }

转载于:https://www.cnblogs.com/leotan0321/p/6081374.html