记录编号	437213	评测结果	AAAAAAAAAA
题目名称	马拉松	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.549 s
提交时间	2017-08-13 20:06:05	内存使用	4.01 MiB

# include <bits/stdc++.h>
# define MAXN 100023

using namespace std;

inline int gn() {
    int k = 0, f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for (; isdigit(c); c = getchar()) k = k * 10 + c - '0';
    return k * f;
}

struct point {
    int x, y;
    point() {;}
    point(int b, int a) {
        x = a, y = b;
    }
} p[MAXN];

inline int dis(point a, point b) {
    return abs(a.x - b.x) + abs(a.y - b.y);
}

inline int cab(int i) {
    return dis(p[i], p[i + 1]) + dis(p[i], p[i - 1]) - dis(p[i - 1], p[i + 1]);
}

struct zkw {
    int M, c[MAXN << 2];
    bool type; // max: 0 sum 1
    zkw() {;}
    zkw(int n, bool t) {
        for (M = 1; M <= n + 1; M <<= 1);
        type = t;
    }
    inline void ins(int x, int p) {
        c[x += M] = p;
        for(x >>= 1; x; x >>= 1) {
            if(type) c[x] = c[x << 1] + c[x << 1 | 1];
            else c[x] = max(c[x << 1], c[x << 1 | 1]);
        }
    }
    inline int que(int l, int r) {
        int ans = 0;
        for (l += M - 1, r += M + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
            if(~l & 1) {
                if(!type) ans = max(ans, c[l + 1]);
                else ans += c[l + 1];
            }
            if(r & 1) {
                if(!type) ans = max(ans, c[r - 1]);
                else ans += c[r - 1];
            }
        }
        return ans;
    }
};

int main() {
    freopen("marathona.in", "r", stdin);
    freopen("marathona.out", "w", stdout);
    int n = gn(), q = gn();
    zkw mx(n, 0), sm(n, 1);
    for(int i = 1; i <= n; i++) {
        p[i] = point(gn(), gn());
        if(i ^ 1) sm.ins(i - 1, dis(p[i - 1], p[i]));
    }
    for(int i = 2; i < n; i++) {
        mx.ins(i, cab(i));
    }
    while(q--) {
        char op = getchar();
        while(!isalpha(op)) op = getchar();
        if(op == 'Q') {
            int l = gn(), r = gn();
            printf("%d\n", sm.que(l, r - 1) - mx.que(l + 1, r - 1));
        }
        else if(op == 'U') {
            int i = gn();
            p[i] = point(gn(), gn());
            if (i ^ n) sm.ins(i, dis(p[i], p[i + 1])), mx.ins(i, cab(i));;
            if (i ^ 1) sm.ins(i - 1, dis(p[i - 1], p[i])), mx.ins(i - 1, cab(i - 1));
            if (i ^ (n - 1)) mx.ins(i + 1, cab(i + 1));
        }
    }
}