【信息学做题日记】天大的BUG+有些懵懵的AC掉一道线段树，还是太菜了

#include <bits/stdc++.h>

using  namespace  std;

const  int MAX_NUM = 1e5 + 5;
typedef  long  long ll;
struct pos {
    int x, y;
} p[MAX_NUM + 5];

struct line {
    int l, r;
    ll v;
};

//int n;
ll dis(pos a, pos b) {
    return abs(a.x - b.x) + abs(a.y - b.y);
}

int n;
struct SegmentTree {
    vector<line> t;
    vector<ll> dist;
    bool opt;

    SegmentTree( bool b, ll v) : t(8 * MAX_NUM), dist(MAX_NUM + 1, v), opt(b) {};

    void push_up(int u) {
        if (opt) {
            t[u].v = t[u << 1].v + t[u << 1 | 1].v;
        } else {
            t[u].v = min(t[u << 1].v, t[u << 1 | 1].v);
        }
    };

    void modify(int u, int x) {
        if (x <= 1 || x > n) {
            return;
        }
        if (t[u].l == x && t[u].r == x) {
            t[u].v = dist[x];
        } else {
            int mid = (t[u].l + t[u].r) >> 1;
            if (x <= mid) {
                modify(u << 1, x);
            } else {
                modify(u << 1 | 1, x);
            }
            push_up(u);
        }
    }

    ll query(int u, int l, int r) {
        if (t[u].l >= l && t[u].r <= r) {
            return t[u].v;
        } else {
            ll cnt = opt ? 0 : 0x7f7f7f7f7f7f7f7f;
            int mid = (t[u].l + t[u].r) >> 1;
            if (l <= mid) {
                ll s = query(u << 1, l, r);
                cnt = opt ? s : min(s, cnt);
            }
            if (r > mid) {
                ll s = query(u << 1 | 1, l, r);
                cnt = opt ? s + cnt : min(s, cnt);
            }
            return cnt;
        }
    }
} sum(true, 0), least(false, 0x7f7f7f7f7f7f7f7f);


void build(int u, int l, int r) {
    sum.t[u].l = l;
    sum.t[u].r = r;
    least.t[u].l = l;
    least.t[u].r = r;
    if (l == r) {
        sum.t[u].v = sum.dist[l];
        least.t[u].v = least.dist[l];
        return;
    }

    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    sum.t[u].v = sum.t[u << 1].v + sum.t[u << 1 | 1].v;
    least.t[u].v = min(least.t[u << 1].v, least.t[u << 1 | 1].v);
}

ll min_num(int u) {
    if (u == 1 || u == n) {
        return 0;
    }
    return dis(p[u - 1], p[u + 1]) - sum.dist[u] - sum.dist[u + 1];
}

void best_coder() {
    int m;
    cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        cin >> p[i].x >> p[i].y;
    }


    for (int i = 2; i <= n; ++i) {
        sum.dist[i] = dis(p[i - 1], p[i]);
    }
    for (int i = 2; i < n; ++i) {
        least.dist[i] = min_num(i);
    }

    build(1, 1, n);
    while (m--) {
        char c;
        cin >> c;
        if (c == 'U') {
            int u;
            cin >> u;

            cin >> p[u].x >> p[u].y;
            sum.dist[u] = dis(p[u], p[u - 1]);
            sum.dist[u + 1] = dis(p[u], p[u + 1]);
            least.dist[u - 1] = min_num(u - 1);
            least.dist[u] = min_num(u);
            least.dist[u + 1] = min_num(u + 1);
            sum.modify(1, u);
            sum.modify(1, u + 1);
            least.modify(1, u - 1);
            least.modify(1, u);
            least.modify(1, u + 1);

        } else {
            int l, r;
            cin >> l >> r;
            cout << sum.query(1, l + 1, r) + least.query(1, l + 1, r - 1) << '\n';
        }
    }

}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
//    freopen("4.in", "r", stdin);
//    freopen("4.out", "w", stdout);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}