英语阅读题。做完去翻译题面然后写英语作业了。
就维护一下区间里的距离和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);
}
}
}