laekov

英语阅读题。做完去翻译题面然后写英语作业了。

就维护一下区间里的距离和and忽略一个点的收益的最大值。完了。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

struct seg {

int l, r;

int s, v;

seg *ls, *rs;

};

const int maxn = 100009;

int n, m, x[maxn], y[maxn], d[maxn], v[maxn];

seg *rt, *sp;

inline void upDis(int i) {

if (i < n)

d[i] = abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i]);

else

d[i] = 0;

}

inline void upVal(int i) {

if (i > 1 && i < n)

v[i] = d[i - 1] + d[i] - abs(x[i + 1] - x[i - 1]) - abs(y[i + 1] - y[i - 1]);

else

v[i] = 0;

}

#define mid(p) ((p->l+p->r)>>1)

inline seg* sgtBuild(int l, int r) {

seg *p = sp ++;

p-> l = l;

p-> r = r;

if (l + 1 == r) {

p-> s = d[l];

p-> v = v[l];

}

else {

p-> ls = sgtBuild(l, mid(p));

p-> rs = sgtBuild(mid(p), r);

p-> s = p-> ls-> s + p-> rs-> s;

p-> v = max(p-> ls-> v, p-> rs-> v);

}

return p;

}

inline void sgtUpd(seg* p, int l, int r) {

if (l >= r || l >= p-> r || r <= p-> l)

return;

else if (p-> l + 1 == p-> r) {

p-> s = d[p-> l];

p-> v = v[p-> l];

}

else {

if (r <= mid(p))

sgtUpd(p-> ls, l, r);

else if (l >= mid(p))

sgtUpd(p-> rs, l, r);

else {

sgtUpd(p-> ls, l, mid(p));

sgtUpd(p-> rs, mid(p), r);

}

p-> s = p-> ls-> s + p-> rs-> s;

p-> v = max(p-> ls-> v, p-> rs-> v);

}

}

inline int sgtSum(seg* p, int l, int r) {

if (l >= r || l >= p-> r || r <= p-> l)

return 0;

else if (p-> l == l && p-> r == r)

return p-> s;

else if (r <= mid(p))

return sgtSum(p-> ls, l, r);

else if (l >= mid(p))

return sgtSum(p-> rs, l, r);

else

return sgtSum(p-> ls, l, mid(p)) + sgtSum(p-> rs, mid(p), r);

}

inline int sgtMax(seg* p, int l, int r) {

if (l >= r || l >= p-> r || r <= p-> l)

return 0;

else if (p-> l == l && p-> r == r)

return p-> v;

else if (r <= mid(p))

return sgtMax(p-> ls, l, r);

else if (l >= mid(p))

return sgtMax(p-> rs, l, r);

else

return max(sgtMax(p-> ls, l, mid(p)), sgtMax(p-> rs, mid(p), r));

}

int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif

scanf("%d%d", &n, &m);

for (int i = 1; i <= n; ++ i)

scanf("%d%d", x + i, y + i);

for (int i = 1; i <= n; ++ i) {

upDis(i);

upVal(i);

}

sp = new seg[n * 3];

rt = sgtBuild(1, n + 1);

while (m --) {

char opt;

int a, b, c;

do

opt = getchar();

while (opt != 'U' && opt != 'Q');

if (opt == 'U') {

scanf("%d%d%d", &a, &b, &c);

x[a] = b;

y[a] = c;

upDis(a - 1);

upDis(a);

upVal(a - 1);

upVal(a);

upVal(a + 1);

sgtUpd(rt, a - 1, a + 2);

}

else {

scanf("%d%d", &a, &b);

int d = sgtSum(rt, a, b);

int v = sgtMax(rt, a + 1, b);

printf("%d\n", d - v);

}

}

}