标签：sx return tx int 题解 单元格 Grid ABC365F now
## 题目大意
有一个网格图，对于 $i=1,2,\dots n$，第 $i$ 列的 $[L_i,U_i]$ 上的单元格是可到达的，形如下面这张图。
图中对于 $i=1,2,\dots7$，$[L_i,U_i]$ 分别为：
```
1 5
3 3
1 3
1 1
1 4
2 4
3 5
```
现有 $q$ 次询问，每次询问给定起点 $(sx,sy)$ 和终点 $(tx,ty)$。从起点出发，规定每次只能走到相邻的空单元格上，问最少走多少步能走到终点。
## Solve
首先考虑暴力怎么计算步数。假定起点在左，终点在右。贪心地，如果我当前单元格右侧是空的，直接向右走，否则走到右侧离他最近的空单元格。如此走到终点所在列之后再加上到终点的距离即可。$O(n)$ 暴力模拟之。
怎么优化？感觉要上一些数据结构，线段树不会，莫队感觉麻烦了，所以考虑分块。
对于一个起点，我一定是先一直水平向右走知道右侧没有空单元格，然后走到右侧空单元格的最上方或者最下方。所以对于每个块，我们维护如下信息：
- $sum_{i,0/1}$ 表示从第 $i$ 列空单元格的最下/上方开始，走到第 $i$ 列所在块的最右端所需最小步数。对于每一列都暴力模拟跑一遍即可，预处理总复杂度 $O(n\sqrt n)$。
- $p_{i,0/1}$ 表示从第 $i$ 列空单元格的最下/上方开始，走到第 $i$ 列所在块的最右端步数最小时，停在了第几行，处理 $sum$ 顺便记录下来即可。
- $mn_i$ 表示从第 $i$ 列所在块左端点到第 $i$ 列中，最上方的空单元格横坐标，即 $U$ 的最小值；$mx_i$ 表示从第 $i$ 列所在块左端点到第 $i$ 列中，最下方的空单元格横坐标，即 $L$ 的最大值。维护这些是为了方便求出一个单元格水平向右最多走到哪。
接下来考虑如何在询问时将相邻的块的信息拼接起来。
比如我们现在走到了第 $x$ 的块的右端点，横坐标为 $now$，我们需要找到第 $x+1$ 个块里，最左侧的第 $now$ 行不是空单元格的列。我们二分查找 $mn_{[l_{x+1},r_{x+1}]}$ 里第一个小于 $now$ 的位置 $p1$ 和 $mx_{[l_{x+1},r_{x+1}]}$ 里第一个大于 $now$ 的位置 $p2$，取 $\min$ 即可。
对于代价，若 $p1<p2$，令总代价加上 $sum_{p1,1}$，否则令总代价加上 $sum_{p2,0}$。即从第 $p1$ / $p2$ 列的最上/下方开始走到第 $x+1$ 块的最右端的代价。然后让 $now=p_{p1,1}$ / $p_{p2,0}$，继续下一块的拼接。
将整块拼接完后再特别处理一下终点所在散块的拼接，二分出第一个无法水平向右走到的位置，从那个位置开始暴力跑一遍代价即可。
询问总复杂度 $O(q\sqrt n\log_2n)$。显然可以调块长把 $\log$ 写到根号里，但本题不卡常。
## Code
```c++
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
short f=1;
int x=0;
char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
typedef long long ll;
const int N=2e5+10,M=500;
int n,q,a[N],b[N],sx,sy,tx,ty;
int m,len,l[M],r[M],p[N][2],pos[N],mn[N],mx[N];
ll sum[N][2];
inline ll calc(int x,int now,int y,int &lst)//从 (x,now) 走到第 y 列的最小代价，最终横坐标为 lst
{
ll res=0;
for(int i=x;i<y;i=-~i)
{
if(now>b[i+1]) res+=now-b[i+1],now=b[i+1];
if(now<a[i+1]) res+=a[i+1]-now,now=a[i+1];
}
return lst=now,res;
}
inline void pre(int u)//预处理第 u 块的信息
{
for(int i=r[u];i>=l[u];i--)
sum[i][0]=calc(i,a[i],r[u],p[i][0]),
sum[i][1]=calc(i,b[i],r[u],p[i][1]);
mn[l[u]]=b[l[u]];mx[l[u]]=a[l[u]];
for(int i=l[u]+1;i<=r[u];i=-~i)
mn[i]=min(b[i],mn[i-1]),mx[i]=max(a[i],mx[i-1]);
}
inline int lower(int l,int r,int x)//mn[l~r] 中第一个比 x 小的位置
{
if(mn[r]>=x) return r+1;
while(l<r)
{
int mid=l+r>>1;
if(mn[mid]<x) r=mid;
else l=-~mid;
}
return l;
}
inline int upper(int l,int r,int x)//mx[l~r] 中第一个比 x 大的位置
{
if(mx[r]<=x) return r+1;
while(l<r)
{
int mid=l+r>>1;
if(mx[mid]>x) r=mid;
else l=-~mid;
}
return l;
}
inline ll query()
{
int x=pos[sx],y=pos[tx],now;
if(x==y) return calc(sx,sy,tx,now)+abs(now-ty);
ll res=calc(sx,sy,r[x],now);//对于两边的散块，暴力跑代价
for(int i=x+1,p1,p2;i<y;i=-~i)
{
p1=upper(l[i],r[i],now),p2=lower(l[i],r[i],now);
if(min(p1,p2)>r[i]) continue;//如果能水平向右走到右端点
if(p1<p2) res+=sum[p1][0]+a[p1]-now,now=p[p1][0];
else res+=sum[p2][1]+now-b[p2],now=p[p2][1];
}
int p1=upper(l[y],tx,now),p2=lower(l[y],tx,now);//拼接终点所在散块
if(min(p1,p2)<=tx)
{
if(p1<p2) res+=a[p1]-now+calc(p1,a[p1],tx,now);
else res+=now-b[p2]+calc(p2,b[p2],tx,now);
}
return res+abs(now-ty);//加上同一列里走到终点横坐标的代价
}
signed main()
{
n=read();len=sqrt(n*1.0);m=n/len;
for(int i=1;i<=m;i=-~i)
l[i]=-~r[i-1],r[i]=r[i-1]+len;
if(n%len) m=-~m,l[m]=r[m-1]+1,r[m]=n;
for(int j=1;j<=m;j=-~j)
for(int i=l[j];i<=r[j];i=-~i)
a[i]=read(),b[i]=read(),pos[i]=j;
for(int i=1;i<=m;i=-~i) pre(i);
q=read();
while(q--)
{
sx=read();sy=read();tx=read();ty=read();
if(sx>tx) swap(sx,tx),swap(sy,ty);//默认从左往右走
printf("%lld\n",query()+tx-sx);//别忘了加上横向代价
}
return 0;
}
```
标签：sx,
return,
tx,
int,
题解,
单元格,
Grid,
ABC365F,
now
From： https://www.cnblogs.com/sorato/p/18343401