2018-2019 ACM-ICPC, Asia Shenyang Regional Contest E.The Kouga Ninja Scrolls 曼哈顿距离转换契比雪夫距离 + 线段树单点修改
线段树   发布于 2019-08-27   446人围观  0条评论
线段树   发表于 2019-08-27   446人围观  0条评论

题目大意

有n个人,他们分别位于(x,y),属于家族c。

现在有三种操作:

1.编号为k的人位置变换到(x+xk,y+yk)。

2.编号为k的人转投到家族c。

3.查询编号区间l----r之间的所有人中两个最远的不同家族的人之间的曼哈顿距离是多少。

题解

如果会曼哈顿距离转化为契比雪夫距离的话,这题思路并不难,可能就是写起来麻烦,极度锻炼思维和代码能力的一道线段树题目。

首先我们看一下曼哈顿距离去掉绝对值之后,一共只有四种情况:

1.x - x' + y - y'

2.x - x' + y' - y

3.x' - x + y - y'

4.x' - x + y' - y;

根据这四种情况,我们变换坐标(x,y)---->(x+y,x-y),从而把横纵坐标分离开计算距离,两个维度上的坐标是分别独立的,取最大值就是上面所说的契比雪夫距离。

然后我们维护的就是一个区间的x+y,x-y的最大、次大、最小、次小。注意:维护的时候最大、次大不能来自同一个家族,最小和次小同理。

查询的时候,我们把区间l---r之间的八个值全部取出,对于同类的(分为x+y和x-y两类值),列出所有的大值减去小值的情况,取所有结果的最大值即可。(注意如果大值和小值来自同一家族,那么这样是不能取的)

前两个修改操作,其实也就是个单点修改,没什么好说的,主要就是push_up函数细节多一(hen)些(duo),需要考虑的东西多一(hen)些(duo)

还是不多说废话了,直接上代码吧(354行啊……)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
	ll val;
	int id;
	bool operator > (const node &b) const{
		return this->val > b.val;
	}
	bool operator < (const node &b) const{
		return this->val < b.val;
	}
	bool operator == (const node &b) const{
		return this->val == b.val && this->id == b.id;
	}
};
const ll INF = 1e17;
const int maxn = 2e5+5;
int n,m,t;
struct tree{
	int l,r;
	node k[10];
}tr[maxn<<3],root;//root用来询问的答案区间的八个维护值
template <class T>
T max(T &a, T &b){
	return (a > b) ? a : b;
}
template <class T>
T min(T &a,T &b){
	return (a < b) ? a : b;
}
ll x[maxn],y[maxn],c[maxn];
bool t1,t2;
void push_up_1(int now){
	if(c[tr[now<<1].k[1].id] != c[tr[now<<1|1].k[1].id]){
		if(tr[now<<1].k[1] > tr[now<<1|1].k[1]){
			tr[now].k[1] = tr[now<<1].k[1];
			tr[now].k[2] = max(tr[now<<1].k[2],tr[now<<1|1].k[1]);
		}
		else{
			tr[now].k[1] = tr[now<<1|1].k[1];
			tr[now].k[2] = max(tr[now<<1|1].k[2],tr[now<<1].k[1]);
		}
	}
	else{
		tr[now].k[1] = max(tr[now<<1].k[1],tr[now<<1|1].k[1]);
		t1 = (tr[now<<1].k[2].id != -1 && c[tr[now].k[1].id] != c[tr[now<<1].k[2].id]);
		t2 = (tr[now<<1|1].k[2].id != -1 && c[tr[now].k[1].id] != c[tr[now<<1|1].k[2].id]);
		if(!t1 && t2)
			tr[now].k[2] = tr[now<<1|1].k[2];
		else if(t1 && !t2)
			tr[now].k[2] = tr[now<<1].k[2];
		else if(t1 && t2)
			tr[now].k[2] = max(tr[now<<1].k[2],tr[now<<1|1].k[2]);
		else tr[now].k[2].val = -INF,tr[now].k[2].id = -1;
	}
	return;
}
void push_up_2(int now){
	if(c[tr[now<<1].k[3].id] != c[tr[now<<1|1].k[3].id]){
		if(tr[now<<1].k[3] > tr[now<<1|1].k[3]){
			tr[now].k[3] = tr[now<<1].k[3];
			tr[now].k[4] = max(tr[now<<1].k[4],tr[now<<1|1].k[3]);
		}
		else{
			tr[now].k[3] = tr[now<<1|1].k[3];
			tr[now].k[4] = max(tr[now<<1|1].k[4],tr[now<<1].k[3]);
		}
	}
	else{
		tr[now].k[3] = max(tr[now<<1].k[3],tr[now<<1|1].k[3]);
		t1 = (tr[now<<1].k[4].id != -1 && c[tr[now].k[3].id] != c[tr[now<<1].k[4].id]);
		t2 = (tr[now<<1|1].k[4].id != -1 && c[tr[now].k[3].id] != c[tr[now<<1|1].k[4].id]);
		if(!t1 && t2)
			tr[now].k[4] = tr[now<<1|1].k[4];
		else if(t1 && !t2)
			tr[now].k[4] = tr[now<<1].k[4];
		else if(t1 && t2)
			tr[now].k[4] = max(tr[now<<1].k[4],tr[now<<1|1].k[4]);
		else tr[now].k[4].val = -INF,tr[now].k[4].id = -1;
	}
	return;
}
void push_up_3(int now){
	if(c[tr[now<<1].k[5].id] != c[tr[now<<1|1].k[5].id]){
		if(tr[now<<1].k[5] < tr[now<<1|1].k[5]){
			tr[now].k[5] = tr[now<<1].k[5];
			tr[now].k[6] = min(tr[now<<1].k[6],tr[now<<1|1].k[5]);
		}
		else{
			tr[now].k[5] = tr[now<<1|1].k[5];
			tr[now].k[6] = min(tr[now<<1|1].k[6],tr[now<<1].k[5]);
		}
	}
	else{
		tr[now].k[5] = min(tr[now<<1].k[5],tr[now<<1|1].k[5]);
		t1 = (tr[now<<1].k[6].id != -1 && c[tr[now].k[5].id] != c[tr[now<<1].k[6].id]);
		t2 = (tr[now<<1|1].k[6].id != -1 && c[tr[now].k[5].id] != c[tr[now<<1|1].k[6].id]);
		if(!t1 && t2)
			tr[now].k[6] = tr[now<<1|1].k[6];
		else if(t1 && !t2)
			tr[now].k[6] = tr[now<<1].k[6];
		else if(t1 && t2)
			tr[now].k[6] = min(tr[now<<1].k[6],tr[now<<1|1].k[6]);
		else tr[now].k[6].val = INF,tr[now].k[6].id = -1;
	}
	return;
}
void push_up_4(int now){
	if(c[tr[now<<1].k[7].id] != c[tr[now<<1|1].k[7].id]){
		if(tr[now<<1].k[7] < tr[now<<1|1].k[7]){
			tr[now].k[7] = tr[now<<1].k[7];
			tr[now].k[8] = min(tr[now<<1].k[8],tr[now<<1|1].k[7]);
		}
		else{
			tr[now].k[7] = tr[now<<1|1].k[7];
			tr[now].k[8] = min(tr[now<<1|1].k[8],tr[now<<1].k[7]);
		}
	}
	else{
		tr[now].k[7] = min(tr[now<<1].k[7],tr[now<<1|1].k[7]);
		t1 = (tr[now<<1].k[8].id != -1 && c[tr[now].k[7].id] != c[tr[now<<1].k[8].id]);
		t2 = (tr[now<<1|1].k[8].id != -1 && c[tr[now].k[7].id] != c[tr[now<<1|1].k[8].id]);
		if(!t1 && t2)
			tr[now].k[8] = tr[now<<1|1].k[8];
		else if(t1 && !t2)
			tr[now].k[8] = tr[now<<1].k[8];
		else if(t1 && t2)
			tr[now].k[8] = min(tr[now<<1].k[8],tr[now<<1|1].k[8]);
		else tr[now].k[8].val = INF,tr[now].k[8].id = -1;
	}
	return;
}
void push_up(int now){
	push_up_1(now);
	push_up_2(now);
	push_up_3(now);
	push_up_4(now);
	return;
}
void build(int now,int l,int r){
	tr[now].l = l;
	tr[now].r = r;
	for(int i = 1;i <= 4;++i){
		tr[now].k[i].val = -INF;
		tr[now].k[i+4].val = INF;
		tr[now].k[i].id = tr[now].k[i+4].id = -1;
	}
	if(l == r){
		tr[now].k[1].id = tr[now].k[5].id = l;
		tr[now].k[3].id = tr[now].k[7].id = l;
		tr[now].k[1].val = tr[now].k[5].val = x[l] + y[l];
		tr[now].k[3].val = tr[now].k[7].val = x[l] - y[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(now<<1,l,mid);
	build(now<<1|1,mid+1,r);
	push_up(now);
	return;
}
void update(int now,int pos){
	if(tr[now].l == tr[now].r){
		tr[now].k[1].val = (x[tr[now].l]+y[tr[now].l]);
		tr[now].k[5].val = (x[tr[now].l]+y[tr[now].l]);
		tr[now].k[3].val = (x[tr[now].l]-y[tr[now].l]);
		tr[now].k[7].val = (x[tr[now].l]-y[tr[now].l]);
		return;
	}
	int mid = (tr[now].l + tr[now].r) >> 1;
	if(pos <= mid)update(now<<1,pos);
	else update(now<<1|1,pos);
	push_up(now);
}
void merge_1(int now){
	if(root.k[1].id == -1){
		root.k[1] = tr[now].k[1];
		root.k[2] = tr[now].k[2];
	}
	else{
		if(c[root.k[1].id] == c[tr[now].k[1].id]){
			root.k[1] = max(root.k[1],tr[now].k[1]);
			if(tr[now].k[2].id != -1 && c[root.k[1].id] != c[tr[now].k[2].id])
				root.k[2] = max(root.k[2],tr[now].k[2]);
		}
		else{
			if(root.k[1] > tr[now].k[1]){
				root.k[2] = max(root.k[2],tr[now].k[1]);
			}
			else{
				root.k[2] = max(root.k[1],tr[now].k[2]);
				root.k[1] = tr[now].k[1];
			}
		}
	}
	return;
}
void merge_2(int now){
	if(root.k[3].id == -1){
		root.k[3] = tr[now].k[3];
		root.k[4] = tr[now].k[4];
	}
	else{
		if(c[root.k[3].id] == c[tr[now].k[3].id]){
			root.k[3] = max(root.k[3],tr[now].k[3]);
			if(tr[now].k[4].id != -1 && c[root.k[3].id] != c[tr[now].k[4].id])
				root.k[4] = max(root.k[4],tr[now].k[4]);
		}
		else{
			if(root.k[3] > tr[now].k[3]){
				root.k[4] = max(root.k[4],tr[now].k[3]);
			}
			else{
				root.k[4] = max(root.k[3],tr[now].k[4]);
				root.k[3] = tr[now].k[3];
			}
		}
	}
	return;
}
void merge_3(int now){
	if(root.k[5].id == -1){
		root.k[5] = tr[now].k[5];
		root.k[6] = tr[now].k[6];
	}
	else{
		if(c[root.k[5].id] == c[tr[now].k[5].id]){
			root.k[5] = min(root.k[5],tr[now].k[5]);
			if(tr[now].k[6].id != -1 && c[root.k[5].id] != c[tr[now].k[6].id])
				root.k[6] = min(root.k[6],tr[now].k[6]);
		}
		else{
			if(root.k[5] < tr[now].k[5]){
				root.k[6] = min(tr[now].k[5],root.k[6]);
			}
			else{
				root.k[6] = min(root.k[5],tr[now].k[6]);
				root.k[5] = tr[now].k[5];
			}
		}
	}
	return;
}
void merge_4(int now){
	if(root.k[7].id == -1){
		root.k[7] = tr[now].k[7];
		root.k[8] = tr[now].k[8];
	}
	else{
		if(c[root.k[7].id] == c[tr[now].k[7].id]){
			root.k[7] = min(root.k[7],tr[now].k[7]);
			if(tr[now].k[8].id != -1 && c[root.k[7].id] != c[tr[now].k[8].id])
				root.k[8] = min(root.k[8],tr[now].k[8]);
		}
		else{
			if(root.k[7] < tr[now].k[7]){
				root.k[8] = min(tr[now].k[7],root.k[8]);
			}
			else{
				root.k[8] = min(root.k[7],tr[now].k[8]);
				root.k[7] = tr[now].k[7];
			}
		}
	}
	return;
}
void query(int now,int l,int r){
	if(tr[now].l >= l && tr[now].r <= r){
		merge_1(now);
		merge_2(now);
		merge_3(now);
		merge_4(now);
		return;
	}
	int mid = (tr[now].l + tr[now].r) >> 1;
	if(l <= mid)query(now<<1,l,r);
	if(r > mid)query(now<<1|1,l,r);
	return;
}
int lq,rq,opt;
ll xx,yy,clp;
void init(int l,int r){
	root.l = l;root.r = r;
	for(int i = 1;i <= 4;++i){
		root.k[i].id = root.k[i+4].id = -1;
		root.k[i].val = -INF;
		root.k[i+4].val = INF;
	}
	return;
}
ll ans;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> t;
	int cas = 0;
	while(t--){
		cas++;
		cin >> n >> m;
		for(int i = 1;i <= n;++i){
			cin >> x[i] >> y[i] >> c[i];
		}
		build(1,1,n);
		cout << "Case #" << cas << ":\n";
		while(m--){
			cin >> opt;
			if(opt == 1){
				cin >> lq;
				cin >> xx >> yy;
				x[lq] += xx;
				y[lq] += yy;
				update(1,lq);
			}
			else if(opt == 2){
				cin >> lq;
				cin >> clp;
				c[lq] = clp;
				update(1,lq);
			}
			else{
				cin >> lq >> rq;
				init(lq,rq);
				query(1,lq,rq);
				ans = 0;
				if(root.k[1].id != -1){
					if(root.k[5].id != -1 && c[root.k[1].id] != c[root.k[5].id])
						ans = max(ans,root.k[1].val - root.k[5].val);
					if(root.k[6].id != -1 && c[root.k[1].id] != c[root.k[6].id])
						ans = max(ans,root.k[1].val - root.k[6].val);
				}
				if(root.k[2].id != -1){
					if(root.k[5].id != -1 && c[root.k[5].id] != c[root.k[2].id])
						ans = max(ans,root.k[2].val - root.k[5].val);
					if(root.k[6].id != -1 && c[root.k[6].id] != c[root.k[2].id])
						ans = max(ans,root.k[2].val - root.k[6].val);
				}
				if(root.k[3].id != -1){
					if(root.k[7].id = -1 && c[root.k[3].id] != c[root.k[7].id])
						ans = max(ans,root.k[3].val - root.k[7].val);
					if(root.k[8].id != -1 && c[root.k[3].id] != c[root.k[8].id])
						ans = max(ans,root.k[3].val - root.k[8].val);
				}
				if(root.k[4].id != -1){
					if(root.k[7].id != -1 && c[root.k[7].id] != c[root.k[4].id])
						ans = max(ans,root.k[4].val - root.k[7].val);
					if(root.k[8].id != -1 && c[root.k[8].id] != c[root.k[4].id])
						ans = max(ans,root.k[4].val - root.k[8].val);
				}
				cout << ans << "\n";
			}
		}
	}
	return 0;
}


上一篇: 2018-2019 ACM-ICPC, Asia Shenyang Regional Contest K. Let the Flames Begin 经典约瑟夫问题 + 思维

下一篇: Suffix Array 后缀数组DA算法模板(带ST表)

立即登录,发表评论
没有帐号?立即注册
0 条评论