旅行计划

  1 #include <cmath>
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <string>
  6 #include <cstdlib>
  7 #include <vector>
  8 #include <algorithm>
  9 #define mp make_pair
 10 #define fi first
 11 #define se second
 12 
 13 using namespace std;
 14 
 15 typedef pair<int,int> PII;
 16 const int MAXN=100005;
 17 const int INF=1000000000;
 18 
 19 struct Point{
 20     int x,y,num;
 21     friend bool operator < (const Point &a,const Point &b)
 22     {
 23         if (a.x!=b.x) return a.x<b.x;
 24         return a.y<b.y;
 25     }
 26 }pnt[MAXN];
 27 
 28 struct E{
 29     int a,b,w;
 30     E(void){}
 31     E(int _a,int _b,int _w):a(_a),b(_b),w(_w){}
 32     friend bool operator < (const E &a,const E &b)
 33     {
 34         return a.w<b.w;
 35     }
 36 }e[MAXN*4];
 37 int en;
 38 
 39 struct G{
 40     int to,next,d;
 41 }g[MAXN*2];
 42 int gn,start[MAXN];
 43 
 44 inline void Add(int a,int b,int d)
 45 {
 46     gn++,g[gn].to=b,g[gn].d=d,g[gn].next=start[a],start[a]=gn;
 47 }
 48 
 49 int n,m;
 50 int fa[MAXN];
 51 int ffa[20][MAXN];
 52 int dis[20][MAXN];
 53 int a[MAXN],b[MAXN];
 54 PII c[MAXN];
 55 int Log[MAXN];
 56 int dep[MAXN];
 57 
 58 inline void Update(int x,PII v)
 59 {
 60     for (int i=x;i<=n;i+=i&(-i)) c[i]=min(c[i],v);
 61 }
 62 
 63 inline PII Query(int x)
 64 {
 65     PII res=mp(INF,-1);
 66     for (int i=x;i;i-=i&(-i)) res=min(res,c[i]);
 67     return res;
 68 }
 69 
 70 int getfa(int x)
 71 {
 72     if (fa[x]!=x) fa[x]=getfa(fa[x]);
 73     return fa[x];
 74 }
 75 
 76 void merge(int x,int y)
 77 {
 78     fa[getfa(x)]=getfa(y);
 79 }
 80 
 81 inline int LCA(int p,int q)
 82 {
 83     if (dep[p]<dep[q]) swap(p,q);
 84     int x=dep[p]-dep[q];
 85     for (int i=0;i<=Log[x];i++)
 86         if (x&(1<<i)) p=ffa[i][p];
 87     for (int i=Log[n];i>=0;i--)
 88         if (ffa[i][p]!=ffa[i][q]) p=ffa[i][p],q=ffa[i][q];
 89     if (p==q) return p;
 90     return ffa[0][p];
 91 }
 92 
 93 inline int Query(int p,int q)
 94 {
 95     int x=dep[p]-dep[q];
 96     int res=0;
 97     for (int i=0;i<=Log[x];i++)
 98         if (x&(1<<i)) res=max(res,dis[i][p]),p=ffa[i][p];
 99     return res;
100 }
101 
102 void Init()
103 {
104     scanf("%d",&n);
105     for (int i=1;i<=n;i++)
106     {
107         scanf("%d%d",&pnt[i].x,&pnt[i].y);
108         pnt[i].num=i;
109     }
110 }
111 
112 void BuildMST()
113 {
114     for (int dir=1;dir<=4;dir++)
115     {
116         if (dir==2||dir==4)
117             for (int i=1;i<=n;i++) swap(pnt[i].x,pnt[i].y);
118         if (dir==3)
119             for (int i=1;i<=n;i++) pnt[i].x=-pnt[i].x;
120         sort(pnt+1,pnt+n+1);
121         for (int i=1;i<=n;i++) a[i]=b[i]=pnt[i].x-pnt[i].y;
122         sort(b+1,b+n+1);
123         int nq=unique(b+1,b+n+1)-(b+1);
124         for (int i=1;i<=n;i++)
125         {
126             a[i]=lower_bound(b+1,b+nq+1,a[i])-b;
127             c[i]=mp(INF,-1);
128         }
129         for (int i=n;i;i--)
130         {
131             int now=Query(a[i]).se;
132             if (now!=-1) e[++en]=E(pnt[i].num,pnt[now].num,pnt[now].x+pnt[now].y-pnt[i].x-pnt[i].y);
133             Update(a[i],mp(pnt[i].x+pnt[i].y,i));
134         }
135     }
136     for (int i=1;i<=n;i++) fa[i]=i;
137     sort(e+1,e+en+1);
138     for (int i=1;i<=en;i++)
139     {
140         if (getfa(e[i].a)==getfa(e[i].b)) continue;
141         merge(e[i].a,e[i].b);
142         Add(e[i].a,e[i].b,e[i].w);
143         Add(e[i].b,e[i].a,e[i].w);
144     }
145 }
146 
147 void BuildTree()
148 {
149     static int qu[MAXN];
150     static bool vis[MAXN];
151     int head=0,tail=1;
152     qu[0]=1;
153     vis[1]=true;
154     while (head!=tail)
155     {
156         int p=qu[head++];
157         for (int i=start[p];i;i=g[i].next)
158         {
159             int v=g[i].to,d=g[i].d;
160             if (vis[v]) continue;
161             vis[v]=true;
162             dep[v]=dep[p]+1;
163             dis[0][v]=d;
164             ffa[0][v]=p;
165             qu[tail++]=v;
166         }
167     }
168     Log[0]=-1;
169     for (int i=1;i<=n;i++) Log[i]=Log[i>>1]+1;
170     for (int i=1;i<=Log[n];i++)
171         for (int j=1;j<=n;j++)
172         {
173             ffa[i][j]=ffa[i-1][ffa[i-1][j]];
174             dis[i][j]=max(dis[i-1][j],dis[i-1][ffa[i-1][j]]);
175         }
176 }
177 
178 void Solve()
179 {
180     scanf("%d",&m);
181     while (m--)
182     {
183         int p,q,lca;
184         scanf("%d%d",&p,&q);
185         lca=LCA(p,q);
186         printf("%d
",max(Query(p,lca),Query(q,lca)));
187     }
188 }
189 
190 int main()
191 {
192     freopen ("plan.in","r",stdin);
193     freopen ("plan.out","w",stdout);
194     Init();
195     BuildMST();
196     BuildTree();
197     Solve();
198     return 0;
199 }

***考试的时候有一种预感这个和树有关系，可素我不会写树哇，于是乎我就开始另辟蹊径（==胡乱打代码），算每一个点到另一个点的最小值并保存这个点的位置，把这个点当做下一次起点，直到它可以一直绕到终点。。为了防止绕不到我还固定如果绕不到就直接求起点和终点的距离。。。可素可素。。。爆零了，(╥╯^╰╥)

***果然题解是和树有关，还是我当初唯一听懂的树剖（emmm可能是听懂了吧。。反正当初没在意代码，能听懂意思我就很开心了。。于是乎现在悲催了），接下来附上当初我对树剖的理解叭

对于每个点记录他的深度是多少

表示处于链最顶端是谁

会经过Log n

步骤

1.比较深度，（每个点为根树的大小）

2.看这两个点所在顶端是否一样

不一样

深度较大的点指向他链顶端的父亲

那就是求自己点和父亲点的链数量

随便挑一个点作为父亲

3.移位

移到他所在链的顶端的父亲的点

在移到父亲的点

直到俩父亲点在同一个链上面

上面的点为答案

由大到小成为一个链

有的倒霉孩子就一个点一个连

预处理完毕

进行查询

求最近公共祖先

说明当初脑子还是正常的吧。。。我可能老了。。记忆力不好了。。。。假如这道题不是树剖。我写的这坨会不会很尴尬。。。