(Аналіз Аллена Чена)

Побачивши, що нам потрібно оновити координати точки та запитати мінімальний час подорожі для підмаршруту, ми одразу бачимо, що ця проблема включає запити діапазону та оновлення. Добре відомою структурою даних, яка може бути використана для вирішення цієї проблеми, є дерево сегментів, яке дозволяє обробляти такі операції в логарифмічному часі.

По-перше, давайте подбаємо про мінімальний час у дорозі, ігноруючи той факт, що корови можуть проскочити контрольно-пропускний пункт по дорозі. Для цього ми розглядаємо кожні 2 послідовні контрольні точки як один вузол у дереві сегментів (назвемо це дерево «dist»).

Потім ми просто зберігаємо відстань між кожними 2 послідовними точками в кожному вузлі. Далі нам потрібно врахувати той факт, що корови можуть пропускати рівно одну контрольну точку на шляху. Скажімо, нам потрібно знайти мінімальний час у дорозі між контрольними точками ~C_i~ та ~C_j~, а також пропускаємо контрольну точку ~C_k~, де ~i<k<j~. Давайте також визначимо ~G(a,b)~ як відстань між контрольними точками ~a~ і ~b~. Отже, час без пропуску контрольної точки дорівнює: </p>

~D_1=G(C_i,C_{i+1}) +G(C_{i+1},C_{i+2})~+ … +~G(C_{j-1},C_j)~. тоді як час пропуску контрольної точки дорівнює:

~D_2=G(C_i,C_{i+1})+G(C_{i+1},C_{i+2})~+ … +~G(C_{k-2},C_{k-1})~ + ~G(C_{k-1},C_{k+1})~+ … +~G(C_{j-1},C_j)~.

Якщо ми візьмемо різницю: ~D1-D2=G(C{k-1},Ck) + G(Ck,C{k+1})-G(C{k-1},C{k+1})

Зверніть увагу, що якщо ми максимізуємо значення ~D_1-D_2~ , тоді ми отримаємо мінімальне ~D_2~ , оскільки ~D_1~ ​​є фіксованим значенням незалежно від будь-якої контрольної точки, яку ми пропускаємо. Таким чином, ми можемо використовувати друге дерево сегментів (назвемо його Δ) і розглядати кожні 3 послідовні контрольні точки як один вузол.

У кожному вузлі Δ нам потрібно лише зберегти ~D_1-D_2~, оскільки ми можемо отримати ~D_2~, взявши: ~D_1~ мінус найкраще значення Δ. Таким чином, ми можемо виконати запит максимального діапазону для delta та запит суми діапазону для dist, щоб отримати нашу остаточну відповідь, виконуючи необхідні оновлення.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<utility>

using namespace std;

typedef pair<int, int> pii;

const int maxn = 1 << 17;
int n, q;
pii mat[maxn];
int delta[2 * maxn];
int dist[2 * maxn];

int qa, qb;
int getd(int a, int b) {
    return abs(mat[a].first - mat[b].first) + abs(mat[a].second - mat[b].second);
}

void build(int rt, int a, int b) {
    if (a > b) return;
    if (a == b) {
        if (a < n - 1) delta[rt] = getd(a, a + 1) + getd(a + 1, a + 2) - getd(a, a + 2);
        else delta[rt] = 0;
        if (a < n) dist[rt] = getd(a, a + 1);
        else dist[rt] = 0;
        return;
    }
    int mid = (a + b) / 2;
    build(rt * 2, a, mid);
    build(rt * 2 + 1, mid + 1, b);
    delta[rt] = max(delta[rt * 2], delta[rt * 2 + 1]);
    dist[rt] = dist[rt * 2] + dist[rt * 2 + 1];
}

int query_dist(int rt, int a, int b) {
    if (a > qb || b < qa) return 0;
    if (qa <= a && b <= qb) return dist[rt];
    int mid = (a + b) / 2;
    return query_dist(rt * 2, a, mid) + query_dist(rt * 2 + 1, mid + 1, b);
}

int query_delta(int rt, int a, int b) {
    if (a > qb || b < qa) return 0;
    if (qa <= a && b <= qb) return delta[rt];
    int mid = (a + b) / 2;
    return max(query_delta(rt * 2, a, mid), query_delta(rt * 2 + 1, mid + 1, b));
}

void update_dist(int rt, int a, int b) {
    if (a > qb || b < qa) return;
    if (qa <= a && b <= qb) {
        if (a >= 1 && a < n) dist[rt] = getd(a, a + 1);
        else dist[rt] = 0;
        return;
    }
    int mid = (a + b) / 2;
    update_dist(rt * 2, a, mid);
    update_dist(rt * 2 + 1, mid + 1, b);
    dist[rt] = dist[rt * 2] + dist[rt * 2 + 1];
}

void update_delta(int rt, int a, int b) {
    if (a > qb || b < qa) return;
    if (qa <= a && b <= qb) {
        if (a >= 1 && a < n - 1) delta[rt] = getd(a, a + 1) + getd(a + 1, a + 2) - getd(a, a + 2);
        else delta[rt] = 0;
        return;
    }
    int mid = (a + b) / 2;
    update_delta(rt * 2, a, mid);
    update_delta(rt * 2 + 1, mid + 1, b);
    delta[rt] = max(delta[rt * 2], delta[rt * 2 + 1]);
}

int main() {
    freopen("marathon.in", "r", stdin);
    freopen("marathon.out", "w", stdout);
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &mat[i].first, &mat[i].second);
    }
    build(1, 1, n);
    for (int i = 0; i < q; i++) {
        char c[2];
        scanf("%s", c);
        if (c[0] == 'Q') {
            scanf("%d%d", &qa, &qb);
            qb--;
            int tot = query_dist(1, 1, n);
            qb--;
            int del = query_delta(1, 1, n);
            printf("%d\n", tot - del);
        }
        else {
            int ix, pa, pb;
            scanf("%d%d%d", &ix, &pa, &pb);
            mat[ix].first = pa;
            mat[ix].second = pb;
            for (int j = ix - 1; j <= ix; j++) {
                qa = j; qb = j;
                update_dist(1, 1, n);
            }
            for (int j = ix - 2; j <= ix; j++) {
                qa = j; qb = j;
                update_delta(1, 1, n);
            }
        }
    }
}