# AtCoder ABC177 F - I hate Shortest Path Problem

Warning:
All updates in original text Published in original text Better eating experience!

## meaning of the title

For a grid of \ ((H + 1) \times W \), each position can go one grid to the right (not the rightmost column), and the \ (I \) row can go down except for the grid from \ (A_i \) to \ (B_i \).
You can start from any grid in line \ (1 \), and for each \ (i \in [2, n + 1] \), find the minimum number of steps to any grid in line \ (i \).
Where \ (H, W \le 2 \times 10^5 \), \ (1 \le A_i \le B_i \le W \)

## thinking

### Greedy thought

It is easy to find that except for line \ (1 \), each grid must go down as far as possible, that is, only go to the right when you can't go down.
Then the preliminary idea is to carry out DP.

### DP

Next, use \ ((i, j) \) to represent the grid in row \ (i \) and column \ (j \).

$$f(i, j)$$ represents the minimum number of steps from any grid in the first row to \ ((i, j) \).
Then there are three cases for \ (f(i, j) \):

1. If there is a baffle on it \ (f(i, j) = \inf \), it can be proved that this has no effect on the answer.
2. If there is no baffle on the top and left (i.e. \ ((i - 1, j - 1) \)), then \ (f(i, j) = f(i - 1, j) + 1 \)
3. If there is no baffle above and there is baffle on the left, then \ (f (I, J) = \ min {k = 1} ^ J F (I - 1, K) + 1 \)

Among them, the contribution from left to right focuses on the third transfer.

The above transfer is:

$f(i, j) = \begin{cases} 0&(i=1)\\ \inf&(A_{i - 1} \le j \le B_{i - 1})\\ f(i - 1, j) + 1&(B_{i - 1} < j - 1 \;\texttt{or}\; A_{i - 1} > j)\\ \min_{k = 1}^j f(i - 1, k) + 1&(B_{i - 1} = j - 1) \end{cases}$

### Data structure optimization

However, the complexity of DP above is \ (O(HW) \), which is certainly unacceptable in this problem. At this time, we can use segment tree optimization.

We maintain each \ (f(i, \cdots) \) with a segment tree and directly \ (O(\log H) \). (similar to the idea of knapsack, change it directly on the original line segment tree)

For the first transition, interval assignment / interval plus \ (\ inf \).
For the second transition, add \ (1 \) to the interval.
For the third transition, another segment tree needs to be maintained with the value of \ (f(i, j) + W - j \). At this time, the third transfer is maintained with the value of the second segment tree.

## code

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 2e5 + 5;
const int INF = 0x3f3f3f3f;

typedef long long LL;

int a[N], b[N];
int n, m;

struct SegTree {
LL t[N << 2], ladd[N << 2];
inline void lazy_down(int x) {
t[x << 1 | 1] += ladd[x];
}
void modify_add(int ql, int qr, LL qadd, int x = 1, int l = 1, int r = m) {
int mid = l + ((r - l) >> 1);
lazy_down(x);
if(qr > mid) modify_add(ql, qr, qadd, x << 1 | 1, mid + 1, r);
t[x] = min(t[x << 1], t[x << 1 | 1]);
}
LL query_min(int ql, int qr, int x = 1, int l = 1, int r = m) {
if(ql <= l && r <= qr) return t[x];
int mid = l + ((r - l) >> 1);
lazy_down(x);
if(qr <= mid) return query_min(ql, qr, x << 1, l, mid);
else if(ql > mid) return query_min(ql, qr, x << 1 | 1, mid + 1, r);
else return min(query_min(ql, qr, x << 1, l, mid), query_min(ql, qr, x << 1 | 1, mid + 1, r));
}
};

SegTree ans1; // f[][i]
SegTree ans2; // f[][i] + m - i

int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]);
for(int i = 1; i <= m; i++) ans2.modify_add(i, i, m - i);
for(int i = 1; i <= n; i++) {
LL tmp = ans2.query_min(1, b[i] + 1) - ((LL)m - b[i] - 1);
ans1.modify_add(b[i] + 1, b[i] + 1, min(tmp - ans1.query_min(b[i] + 1, b[i] + 1), 0LL));
ans2.modify_add(b[i] + 1, b[i] + 1, min(tmp + m - (b[i] + 1) - ans2.query_min(b[i] + 1, b[i] + 1), 0LL));
{"ft_lang_label":"__label__en","ft_lang_prob":0.5620122,"math_prob":0.99957913,"size":3926,"snap":"2023-40-2023-50","text_gpt3_token_len":1405,"char_repetition_ratio":0.10836308,"word_repetition_ratio":0.13463892,"special_character_ratio":0.4228222,"punctuation_ratio":0.19553666,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9993604,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-10-03T20:58:33Z\",\"WARC-Record-ID\":\"<urn:uuid:a5a47a9b-3f5c-4e0d-bb44-1d308fb69a67>\",\"Content-Length\":\"13846\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:8cbcf34d-7a8c-4df3-af51-bdf8ac2ac5c2>\",\"WARC-Concurrent-To\":\"<urn:uuid:d5dd8c45-35d2-4a8b-80b1-633c72cc739f>\",\"WARC-IP-Address\":\"178.238.237.47\",\"WARC-Target-URI\":\"https://www.fatalerrors.org/a/atcoder-abc177-f-i-hate-shortest-path-problem.html\",\"WARC-Payload-Digest\":\"sha1:KB7VNJEYZXW4LWKX7MMDZFOPO3VYXAXW\",\"WARC-Block-Digest\":\"sha1:NJ2UEPK7AUJZTVRMZKHJNFI6JK46GTXI\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-40/CC-MAIN-2023-40_segments_1695233511220.71_warc_CC-MAIN-20231003192425-20231003222425-00803.warc.gz\"}"}