F - I hate Shortest Path Problem
题目大意
给出一个 $(h+1) \times w$ 的二维矩阵，初始位置可以是第 $0$ 行的任意位置。
每一个格只能往右或下方向移动
每一行 $i$ 区间 $L_{i}$ 到 $R_{i}$ 的格子不能向下走，问到达每一行的最小可能步数
简要题解
$dp[i][j]$ 为到达 $(i,j)$ 位置的最小步数
注意从左侧走到某个格子总不会比从上方走来更好，除非无法从上方走来
$$ \begin{align} dp[i][j] & = dp[i-1][j]+1 & j \lt L[i-1] \ or \ R[i-1] \lt j \\ & = dp[i-1][L[i-1]-1]+1+(j-(L[i-1]-1)) & L[i-1] \le j \le R[i-1] \end{align} $$会发现 $dp$ 转移都是以区间为单位的，且对应操作都可以用线段树维护
复杂度
$T$：$O((h + w) \log (w))$
$S$：$O(w)$
代码实现
#include <bits/stdc++.h>
using namespace std;
/*
dp[i][j]=dp[i-1][j]+1; (j<L[i-1] or R[i-1]<j)
dp[i][j]=dp[i-1][L[i-1]-1]+1+(j-(L[i-1]-1)) (L[i-1]<=j<=R[i-1])
*/
const int M=2e5+5;
const int INF=0x3f3f3f3f;
struct SegT
{
struct TN
{
int mn,fi,add;
void app_add(int v)
{
add+=v;
mn+=v;
}
void app_set(int v) // arthimic
{
add=0;
fi=v;
mn=v;
}
}tn[M*4];
int P,L,R,V;
void push(int o,int l,int mi,int r)
{
if(tn[o].fi!=-1)
{
tn[o<<1].app_set(tn[o].fi);
tn[o<<1|1].app_set(tn[o].fi+mi-l+1);
tn[o].fi=-1;
}
if(tn[o].add)
{
tn[o<<1].app_add(tn[o].add);
tn[o<<1|1].app_add(tn[o].add);
tn[o].add=0;
}
}
void pull(int o)
{
tn[o].mn=min(tn[o<<1].mn,tn[o<<1|1].mn);
}
void build(int o,int l,int r)
{
tn[o].mn=tn[o].add=0;
tn[o].fi=-1;
if(l==r)
{
if(l==0) tn[o].mn=tn[o].add=INF;
return;
}
int mid=(l+r)>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
pull(o);
}
void add(int o,int l,int r)
{
if(L<=l&&r<=R)
{
tn[o].app_add(1);
return;
}
int mid=(l+r)>>1;
push(o,l,mid,r);
if(L<=mid) add(o<<1,l,mid);
if(mid<R) add(o<<1|1,mid+1,r);
pull(o);
}
void set(int o,int l,int r)
{
if(L<=l&&r<=R)
{
tn[o].app_set(V+l-L+1);
return;
}
int mid=(l+r)>>1;
push(o,l,mid,r);
if(L<=mid) set(o<<1,l,mid);
if(mid<R) set(o<<1|1,mid+1,r);
pull(o);
}
int query(int o,int l,int r)
{
if(l==r) return tn[o].mn;
int mid=(l+r)>>1;
push(o,l,mid,r);
if(P<=mid) return query(o<<1,l,mid);
else return query(o<<1|1,mid+1,r);
}
}segt;
int main()
{
int h,w; scanf("%d%d",&h,&w);
segt.build(1,0,w);
int l,r;
for(int i=0;i<h;i++)
{
scanf("%d%d",&l,&r);
if(l!=1)
{
segt.L=1; segt.R=l-1;
segt.add(1,0,w);
}
if(r!=w)
{
segt.L=r+1; segt.R=w;
segt.add(1,0,w);
}
segt.P=l-1;
segt.V=segt.query(1,0,w);
segt.L=l; segt.R=r;
segt.set(1,0,w);
int ans=segt.tn[1].mn;
printf("%d\n",ans>=INF ? -1 : ans);
}
return 0;
}
Next: [AtCoder] Beginner Contest 177