正文

lca欧拉序+rmq(st)欧拉序+rmq(线段树)离线dfs(代码片段)

cmyg  cmyg  2022-12-26  599

关键词：

https://www.luogu.org/problemnew/show/P3379

1.欧拉序+rmq(st)

  1 /*
  2 在这里，对于一个数，选择最左边的
  3 选择任意一个都可以，[left_index,right_index]，深度都大于等于这个数的深度
  4 */
  5 #include <cstdio>
  6 #include <cstdlib>
  7 #include <cmath>
  8 #include <cstring>
  9 #include <time.h>
 10 #include <string>
 11 #include <set>
 12 #include <map>
 13 #include <list>
 14 #include <stack>
 15 #include <queue>
 16 #include <vector>
 17 #include <bitset>
 18 #include <ext/rope>
 19 #include <algorithm>
 20 #include <iostream>
 21 using namespace std;
 22 #define ll long long
 23 #define minv 1e-6
 24 #define inf 1e9
 25 #define pi 3.1415926536
 26 #define E  2.7182818284
 27 const ll mod=1e9+7;//998244353
 28 const int maxn=5e5+10;
 29 
 30 struct node
 31 
 32     int d;
 33     node *next;
 34 *e[maxn];
 35 
 36 int s=0;
 37 
 38 ///每条边走两遍，n-1条边，走2(n-1)个点
 39 int a[maxn<<1],b[maxn<<1],f[maxn<<1][20],lef[maxn],er[20];
 40 bool vis[maxn]=0;
 41 
 42 void dfs(int d,int dep)
 43 
 44     node* p=e[d];
 45     vis[d]=1;
 46     s++;
 47     lef[d]=s;
 48     a[s]=d;
 49     b[s]=dep;
 50     while (p)
 51     
 52         if (!vis[p->d])
 53         
 54             dfs(p->d,dep+1);
 55             s++;
 56             a[s]=d;
 57             b[s]=dep;
 58         
 59         p=p->next;
 60     
 61 
 62 
 63 int main()
 64 
 65     int n,q,root,x,y,i,j,k,m,d;
 66     node *p;
 67     scanf("%d%d%d",&n,&q,&root);
 68     for (i=1;i<n;i++)
 69     
 70         scanf("%d%d",&x,&y);
 71         p=(node*) malloc (sizeof(node));
 72         p->d=y;
 73         p->next=e[x];
 74         e[x]=p;
 75 
 76         p=(node*) malloc (sizeof(node));
 77         p->d=x;
 78         p->next=e[y];
 79         e[y]=p;
 80     
 81     dfs(root,1);
 82 
 83     m=log(s)/log(2);
 84     er[0]=1;
 85     for (i=1;i<=m;i++)
 86         er[i]=er[i-1]<<1;
 87     for (i=1;i<=s;i++)
 88         f[i][0]=i;
 89 //        f[i][0]=b[i];
 90     for (i=1;i<=m;i++)   //2^i
 91         for (j=1,k=j+er[i-1];j<=s-er[i]+1;j++,k++)  //-er[i]+1
 92             if (b[ f[j][i-1] ] < b[ f[k][i-1] ])
 93                 f[j][i]=f[j][i-1];
 94             else
 95                 f[j][i]=f[k][i-1];
 96 //            f[j][i]=min(f[j][i-1],f[j+er[i-1]][i-1]);
 97 
 98     while (q--)
 99     
100         scanf("%d%d",&x,&y);
101         x=lef[x];
102         y=lef[y];
103         if (x>y)
104             swap(x,y);
105         d=log(y-x+1)/log(2);
106         j=y-er[d]+1;
107         if (b[ f[x][d] ] < b[ f[j][d] ])    //+1
108             printf("%d
",a[ f[x][d] ]);
109         else
110             printf("%d
",a[ f[j][d] ]);
111 //        printf("%d
",min(f[x][d],f[y-er[d]+1][d]));
112     
113     return 0;
114 
115 /*
116 8 100 1
117 1 2
118 1 3
119 2 4
120 2 5
121 3 6
122 5 7
123 6 8
124 
125 5 7
126 5
127 2 3
128 1
129 3 2
130 1
131 1 8
132 1
133 2 8
134 1
135 4 5
136 2
137 5 4
138 2
139 */

2.欧拉序+线段树

  1 /*
  2 在这里，对于一个数，选择最左边的
  3 选择任意一个都可以，[left_index,right_index]，深度都大于等于这个数的深度
  4 */
  5 #include <cstdio>
  6 #include <cstdlib>
  7 #include <cmath>
  8 #include <cstring>
  9 #include <time.h>
 10 #include <string>
 11 #include <set>
 12 #include <map>
 13 #include <list>
 14 #include <stack>
 15 #include <queue>
 16 #include <vector>
 17 #include <bitset>
 18 #include <ext/rope>
 19 #include <algorithm>
 20 #include <iostream>
 21 using namespace std;
 22 #define ll long long
 23 #define minv 1e-6
 24 #define inf 1e9
 25 #define pi 3.1415926536
 26 #define E  2.7182818284
 27 const ll mod=1e9+7;//998244353
 28 const int maxn=5e5+10;
 29 
 30 struct node
 31 
 32     int d;
 33     node *next;
 34 *e[maxn];
 35 
 36 int s=0;
 37 
 38 ///每条边走两遍，n-1条边，走2(n-1)个点
 39 int a[maxn<<1],b[maxn<<1],lef[maxn],f[maxn<<3];
 40 bool vis[maxn]=0;
 41 int num=0;
 42 
 43 void dfs(int d,int dep)
 44 
 45     node* p=e[d];
 46     vis[d]=1;
 47     s++;
 48     lef[d]=s;
 49     a[s]=d;
 50     b[s]=dep;
 51     while (p)
 52     
 53         if (!vis[p->d])
 54         
 55             dfs(p->d,dep+1);
 56             s++;
 57             a[s]=d;
 58             b[s]=dep;
 59         
 60         p=p->next;
 61     
 62 
 63 
 64 void build(int index,int l,int r)
 65 
 66     if (l==r)
 67         f[index]=++num;
 68     else
 69     
 70         int m=(l+r)>>1;
 71         build(index<<1,l,m);
 72         build(index<<1|1,m+1,r);
 73         if (b[f[index<<1]]<b[f[index<<1|1]])
 74             f[index]=f[index<<1];
 75         else
 76             f[index]=f[index<<1|1];
 77     
 78 
 79 
 80 int query(int index,int l,int r,int x,int y)
 81 
 82     if (x<=l && r<=y)
 83         return f[index];
 84     if (r<x || l>y)
 85         return 0;
 86     int m=(l+r)>>1;
 87     int p=query(index<<1,l,m,x,y);
 88     int q=query(index<<1|1,m+1,r,x,y);
 89     if (b[p]<b[q])
 90         return p;
 91     else
 92         return q;
 93 
 94 
 95 int main()
 96 
 97     int n,q,root,x,y,i,j,m,d;
 98     node *p;
 99     scanf("%d%d%d",&n,&q,&root);
100     for (i=1;i<n;i++)
101     
102         scanf("%d%d",&x,&y);
103         p=(node*) malloc (sizeof(node));
104         p->d=y;
105         p->next=e[x];
106         e[x]=p;
107 
108         p=(node*) malloc (sizeof(node));
109         p->d=x;
110         p->next=e[y];
111         e[y]=p;
112     
113     dfs(root,1);
114 
115     b[0]=n+1;
116     build(1,1,s);
117     while (q--)
118     
119         scanf("%d%d",&x,&y);
120         x=lef[x];
121         y=lef[y];
122         if (x>y)
123             swap(x,y);
124         printf("%d
",a[query(1,1,s,x,y)]);
125     
126     return 0;
127

3.离线dfs

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <time.h>
  6 #include <string>
  7 #include <set>
  8 #include <map>
  9 #include <list>
 10 #include <stack>
 11 #include <queue>
 12 #include <vector>
 13 #include <bitset>
 14 #include <ext/rope>
 15 #include <algorithm>
 16 #include <iostream>
 17 using namespace std;
 18 #define ll long long
 19 #define minv 1e-6
 20 #define inf 1e9
 21 #define pi 3.1415926536
 22 #define E  2.7182818284
 23 const ll mod=1e9+7;//998244353
 24 const int maxn=5e5+10;
 25 
 26 struct node
 27 
 28     int d;
 29     node *next;
 30 *e[maxn];
 31 struct rec
 32 
 33     int d,index;
 34     rec *next;
 35 *ask[maxn];
 36 bool vis[maxn]=0;
 37 
 38 int r[maxn],fa[maxn];
 39 
 40 int getfather(int d)
 41 
 42     if (fa[d]==d)
 43         return d;
 44     fa[d]=getfather(fa[d]);
 45     return fa[d];
 46 
 47 
 48 void merge(int x,int y)
 49 
 50     int s=getfather(x);
 51     int t=getfather(y);
 52     fa[t]=s;
 53 
 54 
 55 void dfs(int d)
 56 
 57     node *p;
 58     rec *v;
 59     vis[d]=1;
 60 
 61     p=e[d];
 62     while (p)
 63     
 64         if (!vis[p->d])
 65         
 66             dfs(p->d);
 67             merge(d,p->d);
 68         
 69         p=p->next;
 70     
 71 
 72     v=ask[d];
 73     while (v)
 74     
 75         if (vis[v->d])
 76             r[v->index]=getfather(v->d);
 77         v=v->next;
 78     
 79 
 80 
 81 int main()
 82 
 83     node *p;
 84     rec *v;
 85     int n,q,root,x,y,i;
 86     scanf("%d%d%d",&n,&q,&root);
 87     for (i=1;i<n;i++)
 88     
 89         scanf("%d%d",&x,&y);
 90         p=(node*) malloc (sizeof(node));
 91         p->d=y;
 92         p->next=e[x];
 93         e[x]=p;
 94 
 95         p=(node*) malloc (sizeof(node));
 96         p->d=x;
 97         p->next=e[y];
 98         e[y]=p;
 99     
100 
101     for (i=1;i<=q;i++)
102     
103         scanf("%d%d",&x,&y);
104         v=(rec*) malloc (sizeof(rec));
105         v->d=y;
106         v->index=i;
107         v->next=ask[x];
108         ask[x]=v;
109 
110         v=(rec*) malloc (sizeof(rec));
111         v->d=x;
112         v->index=i;
113         v->next=ask[y];
114         ask[y]=v;
115     
116 
117     for (i=1;i<=n;i++)
118         fa[i]=i;
119     dfs(root);
120     for (i=1;i<=q;i++)
121         printf("%d
",r[i]);
122     return 0;
123

hdu2586（lca欧拉序和st表）(代码片段)

什么是欧拉序，可以去这个大佬的博客（https://www.cnblogs.com/stxy-ferryman/p/7741970.html）巨详细因为欧拉序中的两点之间，就是两点遍历的过程，所以只要找遍历过程中对应的最小的深度就行了，这里用st表存，first存第一个u出现的地... 查看详情

蓝书4.1-4.4树状数组rmq问题线段树倍增求lca(代码片段)

这章的数据结构题很真实T1排队bzoj1699题目大意：求静态一些区间的最大值-最小值思路：ST表裸题1#include<iostream>2#include<cstdio>3#include<cstdlib>4#include<cstring>5#include<cmath>6#include<algorithm>7#inc 查看详情

uva11235frequentvalues线段树/rmq

　　vjudge上题目链接：UVA11235*******************************************************大白书上解释************************************************************　　题目大意：给出一个非降序排列的整数数组a1,a2,a3,...,an，你的任务是对于一系列询问(i,j)，回... 查看详情

poj2763(lca/rmq+线段树)

题目链接:http://poj.org/problem?id=2763 题意:第一行输入n,q,s分别为树的顶点个数,询问/修改个数,初始位置.接下来n-1行形如x,y,w的输入为点x,y之间连边且边权为w.接下来q行输入,若输入形式为1xy则为将点x的权值修改为y,若输入形式为0... 查看详情

欧拉序动态维护树直径(代码片段)

...1260601.html 一个月过去了，我还是没有学动态点分治...欧拉序保存了每个节点进入和返回的情况，$n$个结点的树，欧拉序列长度为$2n-1$。两个结点的LCA就是它们在欧拉序中出现的位置的区间中，深度最小的那个结点。对于边权... 查看详情

bzoj3772精神污染主席树+欧拉序

这道题的内存…………………真·精神污染………..这道题的思路很明了，我们就是要找每一个路径包含了多少其他路径那么就是找，有多少路径的左右端点都在这条路径上，对于每一条路径，我们随便选定一个端点作为第一关... 查看详情

lca--倍增法

一般来求LCA有3种方法1.倍增2.RMQ+欧拉序3.tarjan（离线）本文将倍增求lca这个算法是很常见很常见的也是较好理解的（我也不明白假期学长讲的时候我为什么死活都不明白　自闭qwq　对不起学长qwq　明明学长讲的是最好的qwq　... 查看详情

cs20dlca

...了。官方题解里面的代码求LCA是在线DFSRMQ的方法..先记录欧拉序，且记录某个点在序列里的第一个位置，每次询问a,b的LCA就是询问两者在欧拉序列里第一个位置之差中的那些点里面深度最小的LCA(a,b)=RMQ(dep,pos[a], 查看详情

树的经典问题和方法

...的经典问题和方法《算法竞赛入门经典（第2版）》392页欧拉序列。对有根树t进行dfs（深度优先遍历），无论是递归还是回溯，每次到达一个结点时都将深度记录下来，可以得到一个长度为2n-1的序列，称为t的欧拉序列f(类似于欧... 查看详情

51nod1766树上的最远点对（线段树，lca，rmq）

题意：n个点被n-1条边连接成了一颗树，给出a~b和c~d两个区间，表示点的标号请你求出两个区间内各选一点之间的最大距离，即你需要求出max｛dis(i,j)|a<=i<=b,c<=j<=d｝n<=100000len[i]<=100000思路：两年前张老师出的模拟赛里... 查看详情

[算法整理]树上求lca算法合集

...g2n),也不算难写。2#st表(RMQ)　　首先对一棵树进行dfs,得到欧拉序列，记录下每个节点的第一次出现位置。　　（先序遍历这棵树，访问到的节点(无论是从深的一层返回还是父节点访问)就加入到序列中，序列长度为2*n-1）　查看详情

hdu2586howfaraway？<<lca转rmq+st表求树上任两点最短距离裸题(代码片段)

此题还有LCA+tarjin离线查询做法，详见这里关于ST表解决RMQ问题，dp[i][j]表示从第i位开始长度为（1<<j）的区间的最值维护的时候采用倍增思想，维护dp[i][j+1]=opt(dp[i][j],dp[i+(1<<j)][j])查询的时候，两端点为l，r，则长度len=r-l... 查看详情

线段树＋rmq问题第二弹

线段树＋RMQ问题第二弹上篇文章讲到了基于SparseTable解决RMQ问题，不知道大家还有没有印象，今天我们会从线段树的方法对RMQ问题再一次讨论。正式介绍今天解决RMQ问题的方法之前，我先对RMQ问题的概念再... 查看详情

lca学习笔记

LCA学习笔记http://dongxicheng.org/structure/lca-rmq/http://blog.csdn.net/wendavidoi/article/details/50670052dfs序+st树上倍增Tarjan算法题目TBD模板TBD 查看详情

浅谈rmq

...是(Range)(Minimum/Maximum)(Query)，区间最值查询。我们可以用线段树维护，也可以使用笛卡尔树将其转化为求(lca)的问题。但是后者一般不常用，更为常用的，是家喻户晓的(st)算法。由于(RMQ)问题大多不是赤裸裸的(RMQ)，而是经过了伪... 查看详情

51nod.1766.树上最远点对(树的直径rmq线段树/st表)(代码片段)

题目链接(Description)给定一棵树。每次询问给定(asimb,csimd)两个下标区间，从这两个区间中各取一个点，使得这两个点距离最远。输出最远距离。(n,qleq10^5)。(Solution)一个集合直径的两端点，在被划分为两个集合后一定是两个集合直... 查看详情

rmq问题之st算法

...十分低效。这时我们往往使用ST算法解决这个问题。虽然线段树查看详情

[luogup1816]忠诚（rmq||线段树）

传送门其实我就是想练练rmq本以为学了线段树可以省点事不学rmq了但是后缀数组中用rmq貌似很方便所以还是学了吧，反正也不难 ——代码1#include<cstdio>2#defineN1000013#definemin(x,y)((x)<(y)?(x):(y))45intn,m;6inta[N],d[N][21]... 查看详情