The 2018 ICPC Asia Shenyang Regional Contest E. The Kouga Ninja Scrolls
题目链接
http://codeforces.com/gym/101955/problem/E
题目大意
有 $n$ 个忍者，第 $i$ 个忍者在坐标 $(x_i, y_i)$ 上且隶属于 $c_i$ 家族。有三种操作， $m$ 次询问。
- 将第 $k$ 号忍者的坐标移动到 $(x_0 + x, y_0 + y)$
- 将第 $k$ 号忍者的家族改为 $c$
- 询问编号为 $[l, r]$ 之间的忍者中，二者隶属于不同的家族且曼哈顿距离最大的点对的曼哈顿距离为多少
题目分析
题目询问点集中曼哈顿距离最大的点对，先考虑两点间的曼哈顿距离，则答案为 $|x_1 – x_2| + |y_1 – y_2|$，将绝对值展开，则发现曼哈顿距离为四种情况的最大值，即
$$max\{(x_1 + y_1) – (x_2 + y_2), (x_1 – y_1) – (x_2 – y_2),$$
$$(-x_1 + y_1) – (-x_2 + y_2), (-x_1 – y_1) – (-x_2 – y_2)\}$$
注意到后两种其实为前两种的相反数因此对于点集中最大的点对，只需要记录 $(x + y)$ 和 $(x – y)$ 的最大值和最小值即可，答案为各自的最大值减最小值取 $max$ 。
求区间的最大值最小值，可以使用线段树维护。考虑要求所属的家族不一样，可以记录最大的和最小的两个不同家族的值，最后求值的时候讨论一下即可。对于两种情况分别使用一个线段树维护，询问时取最大值即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1e5 + 5;
int n, m, t;
struct point {
long long x, y;
int c;
} p[maxn];
struct ex {
long long num[2];
long long c[2];
int init(long long x, int cc){
num[0] = x;
c[0] = cc;
num[1] = c[1] = 0;
return 0;
}
};
ex mergemax(ex x, ex y){
ex ret;
if(x.c[0] == y.c[0]){
ret.c[0] = x.c[0];
ret.num[0] = max(x.num[0], y.num[0]);
if(x.num[1] < y.num[1] and y.c[1]){
ret.c[1] = y.c[1];
ret.num[1] = y.num[1];
}else{
ret.c[1] = x.c[1];
ret.num[1] = x.num[1];
}
}else{
if(x.num[0] < y.num[0]){
ret.c[0] = y.c[0];
ret.num[0] = y.num[0];
if(x.num[0] < y.num[1] and y.c[1]){
ret.c[1] = y.c[1];
ret.num[1] = y.num[1];
}else{
ret.c[1] = x.c[0];
ret.num[1] = x.num[0];
}
}else{
ret.c[0] = x.c[0];
ret.num[0] = x.num[0];
if(x.num[1] < y.num[0] or !x.c[1]){
ret.c[1] = y.c[0];
ret.num[1] = y.num[0];
}else{
ret.c[1] = x.c[1];
ret.num[1] = x.num[1];
}
}
}
return ret;
}
ex mergemin(ex x, ex y){
ex ret;
if(x.c[0] == y.c[0]){
ret.c[0] = x.c[0];
ret.num[0] = min(x.num[0], y.num[0]);
if(x.num[1] > y.num[1] and y.c[1]){
ret.c[1] = y.c[1];
ret.num[1] = y.num[1];
}else{
ret.c[1] = x.c[1];
ret.num[1] = x.num[1];
}
}else{
if(x.num[0] > y.num[0]){
ret.c[0] = y.c[0];
ret.num[0] = y.num[0];
if(x.num[0] > y.num[1] and y.c[1]){
ret.c[1] = y.c[1];
ret.num[1] = y.num[1];
}else{
ret.c[1] = x.c[0];
ret.num[1] = x.num[0];
}
}else{
ret.c[0] = x.c[0];
ret.num[0] = x.num[0];
if(x.num[1] > y.num[0] or !x.c[1]){
ret.c[1] = y.c[0];
ret.num[1] = y.num[0];
}else{
ret.c[1] = x.c[1];
ret.num[1] = x.num[1];
}
}
}
return ret;
}
struct node {
int l, r;
int lc, rc;
ex maxx, minx;
};
struct sttree {
node tree[maxn * 4];
int tc;
int root;
int d;
long long cal(long long x, long long y){
if(d){
return x - y;
}else{
return x + y;
}
}
ex query_min(int pos, int l, int r){
int mid = (tree[pos].l + tree[pos].r) / 2;
if(tree[pos].l == l and r == tree[pos].r){
return tree[pos].minx;
}else{
if(r <= mid){
return query_min(tree[pos].lc, l, r);
}else if(l <= mid){
return mergemin(query_min(tree[pos].lc, l, mid), query_min(tree[pos].rc, mid + 1, r));
}else{
return query_min(tree[pos].rc, l, r);
}
}
}
ex query_max(int pos, int l, int r){
int mid = (tree[pos].l + tree[pos].r) / 2;
if(tree[pos].l == l and r == tree[pos].r){
return tree[pos].maxx;
}else{
if(r <= mid){
return query_max(tree[pos].lc, l, r);
}else if(l <= mid){
return mergemax(query_max(tree[pos].lc, l, mid), query_max(tree[pos].rc, mid + 1, r));
}else{
return query_max(tree[pos].rc, l, r);
}
}
}
int update_tree(int pos, int x){
int mid = (tree[pos].l + tree[pos].r) / 2;
if(tree[pos].l == tree[pos].r){
tree[pos].maxx.init(cal(p[tree[pos].l].x, p[tree[pos].l].y), p[tree[pos].l].c);
tree[pos].minx.init(cal(p[tree[pos].l].x, p[tree[pos].l].y), p[tree[pos].l].c);
}else{
if(x <= mid){
update_tree(tree[pos].lc, x);
}else{
update_tree(tree[pos].rc, x);
}
tree[pos].maxx = mergemax(tree[tree[pos].lc].maxx, tree[tree[pos].rc].maxx);
tree[pos].minx = mergemin(tree[tree[pos].lc].minx, tree[tree[pos].rc].minx);
}
return 0;
}
int init_tree(int l, int r){
int mid = (l + r) / 2;
int pos = ++tc;
tree[pos].l = l;
tree[pos].r = r;
if(l == r){
tree[pos].maxx.init(cal(p[l].x, p[l].y), p[l].c);
tree[pos].minx.init(cal(p[l].x, p[l].y), p[l].c);
}else{
tree[pos].lc = init_tree(l, mid);
tree[pos].rc = init_tree(mid + 1, r);
tree[pos].maxx = mergemax(tree[tree[pos].lc].maxx, tree[tree[pos].rc].maxx);
tree[pos].minx = mergemin(tree[tree[pos].lc].minx, tree[tree[pos].rc].minx);
}
return pos;
}
long long query(int l, int r){
long long ret = 0;
int i, j;
ex minx = query_min(root, l, r);
ex maxx = query_max(root, l, r);
for(i=0;i<=1;i++){
for(j=0;j<=1;j++){
if(maxx.c[i] and minx.c[j] and maxx.c[i] != minx.c[j]){
ret = max(ret, maxx.num[i] - minx.num[j]);
}
}
}
return ret;
}
int update(int x){
update_tree(root, x);
}
int init(int dd){
d = dd;
tc = 0;
root = init_tree(1, n);
return 0;
}
};
sttree f[2];
int read(){
int x;
scanf("%d", &x);
return x;
}
int main(){
int i, j;
long long x, y, c;
int tnum = 0;
int op;
int k;
t = read();
while(t--){
n = read();
m = read();
printf("Case #%d:\n", ++tnum);
for(i=1;i<=n;i++){
x = read();
y = read();
c = read();
p[i].x = x;
p[i].y = y;
p[i].c = c;
}
f[0].init(0);
f[1].init(1);
for(i=1;i<=m;i++){
op = read();
if(op == 1){
k = read();
x = read();
y = read();
p[k].x += x;
p[k].y += y;
f[0].update(k);
f[1].update(k);
}else if(op == 2){
k = read();
c = read();
p[k].c = c;
f[0].update(k);
f[1].update(k);
}else{
x = read();
y = read();
printf("%lld\n", max(f[0].query(x, y), f[1].query(x, y)));
}
}
}
return 0;
}