gym/101955/problem/E - The Kouga Ninja Scrolls 线段数 维护 切比雪夫距离 2018沈阳icpc
2024-09-01 04:46:38
思路：
这道题要把给定的每个坐标利用切比雪夫坐标表示，这样两个点的距离就是max（dx，dy），而不是一开始的dx + dy，有利于线段树的维护，又由于询问的是区间的最大差值，限制是两个点是属于不同门派的，所以我们可以维护每个区间的最大，次大值，最小次小值。
#include <algorithm>
#include <iterator>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cassert> using namespace std;
#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 bll;
typedef pair<ll ,ll > pll;
typedef pair<int ,int > pii;
typedef pair<int,pii> p3;
typedef pair<ll,int>pli;
//priority_queue<int> q;//这是一个大根堆q
//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
#define fi first
#define se second
//#define endl '\n' #define OKC ios::sync_with_stdio(false);cin.tie(0)
#define FT(A,B,C) for(int A=B;A <= C;++A) //用来压行
#define REP(i , j , k) for(int i = j ; i < k ; ++i)
#define max3(a,b,c) max(max(a,b), c);
#define min3(a,b,c) min(min(a,b), c);
//priority_queue<int ,vector<int>, greater<int> >que; const ll mos = 0x7FFFFFFF; //
const ll nmos = 0x80000000; //-2147483648
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f; //
const int mod = ;
const double esp = 1e-;
const double PI=acos(-1.0);
const double PHI=0.61803399; //黄金分割点
const double tPHI=0.38196601; template<typename T>
inline T read(T&x){
x=;int f=;char ch=getchar();
while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x=f?-x:x;
}
/*-----------------------showtime----------------------*/ const int maxn = 5e5+;
int n,m;
struct node{
ll x,y,c;
}a[maxn]; struct Tree{
///p[0] x轴 1,2 第一第二大,3,4第一第二小
///p[1] y轴
pli p[][];
} t[maxn<<]; void pushup34(int rt,int id){
pli tmp[];
tmp[] = t[rt<<].p[id][];
tmp[] = t[rt<<].p[id][];
tmp[] = t[rt<<|].p[id][];
tmp[] = t[rt<<|].p[id][]; t[rt].p[id][] = {inff,};
t[rt].p[id][] = {inff,};
for(int i=; i<=; i++){
if(t[rt].p[id][].fi > tmp[i].fi && tmp[i].se){
t[rt].p[id][] = tmp[i];
}
} for(int i=; i<=; i++){
if(t[rt].p[id][].fi > tmp[i].fi && tmp[i].se != t[rt].p[id][].se){
t[rt].p[id][] = tmp[i];
}
} }
void pushup12(int rt,int id){
pli tmp[];
tmp[] = t[rt<<].p[id][];
tmp[] = t[rt<<].p[id][];
tmp[] = t[rt<<|].p[id][];
tmp[] = t[rt<<|].p[id][]; t[rt].p[id][] = {-inff,};
t[rt].p[id][] = {-inff,};
for(int i=; i<=; i++){
if(t[rt].p[id][].fi < tmp[i].fi && tmp[i].se){ t[rt].p[id][] = tmp[i];
}
} for(int i=; i<=; i++){
if(t[rt].p[id][].fi < tmp[i].fi && tmp[i].se != t[rt].p[id][].se){
t[rt].p[id][] = tmp[i];
}
}
}
void build(int l,int r,int rt){
if(l == r){ t[rt].p[][].fi = a[l].x; t[rt].p[][].se = a[l].c;
t[rt].p[][] = {-inff,};
t[rt].p[][].fi = a[l].x; t[rt].p[][].se = a[l].c;
t[rt].p[][] = {inff,}; /*-----------------------*/
t[rt].p[][].fi = a[l].y; t[rt].p[][].se = a[l].c;
t[rt].p[][] = {-inff,};
t[rt].p[][].fi = a[l].y; t[rt].p[][].se = a[l].c;
t[rt].p[][] = {inff,}; return;
}
int mid = (l + r) >> ;
build(l,mid,rt<<);
build(mid+,r,rt<<|);
pushup12(rt, ); pushup34(rt, ); pushup12(rt, ); pushup34(rt, );
} void update(int k,int c,int dx,int dy,int l,int r,int rt){
if(l == r){
a[l].x += 1ll*dx;
a[l].y += 1ll*dy;
a[l].c = c;
t[rt].p[][].fi = a[l].x; t[rt].p[][].se = a[l].c;
t[rt].p[][] = {-inff,};
t[rt].p[][].fi = a[l].x; t[rt].p[][].se = a[l].c;
t[rt].p[][] = {inff,}; //-----------------------------------//
t[rt].p[][].fi = a[l].y; t[rt].p[][].se = a[l].c;
t[rt].p[][] = {-inff,};
t[rt].p[][].fi = a[l].y; t[rt].p[][].se = a[l].c;
t[rt].p[][] = {inff,}; return;
}
int mid = (l + r) >> ;
if(k <= mid) update(k,c,dx,dy,l,mid,rt<<);
else update(k,c,dx,dy,mid+,r,rt<<|);
pushup12(rt, ); pushup34(rt, ); pushup12(rt, ); pushup34(rt, );
} void query(int L,int R,int l,int r,int rt,pli &b1,pli &b2,pli &s1, pli &s2,int id){
if( L <= l && r <= R){ for(int i=; i<=; i++) {
if(b1.fi < t[rt].p[id][i].fi)
{
if(b1.se != t[rt].p[id][i].se)
b2 = b1;
b1 = t[rt].p[id][i];
}
}
for(int i=; i<=; i++){
if(b2.fi < t[rt].p[id][i].fi && b1.se != t[rt].p[id][i].se){
b2 = t[rt].p[id][i];
}
} for(int i=; i<=; i++) {
if(s1.fi > t[rt].p[id][i].fi){
if(s1.se != t[rt].p[id][i].se)
s2 = s1;
s1 = t[rt].p[id][i];
}
}
for(int i=; i<=; i++){
if(s2.fi > t[rt].p[id][i].fi && s1.se != t[rt].p[id][i].se){
s2 = t[rt].p[id][i];
}
}
return ;
} int mid = (l + r) >> ;
if(mid >= L) query(L, R, l, mid, rt<<, b1,b2,s1,s2,id);
if(mid < R) query(L, R, mid+, r,rt<<|, b1,b2,s1,s2,id); }
int main(){
int T; scanf("%d", &T);
for(int cas=; cas<=T; cas++){
printf("Case #%d:\n", cas);
scanf("%d%d", &n, &m);
for(int i=; i<=n; i++){
int x,y,c;
scanf("%d%d%d", &x, &y, &c);
a[i].x = x + y, a[i].y = x - y;
a[i].c = c;
} build(,n,); while(m --) {
int op; scanf("%d", &op);
if(op == ){
int k,x,y;
scanf("%d%d%d", &k, &x, &y);
update(k,a[k].c,x+y, x-y,,n,);
}
else if(op == ){
int k,c;
scanf("%d%d", &k, &c);
update(k,c,,,,n,);
}
else {
int l,r;
scanf("%d%d", &l, &r); pli q[];
q[] = q[] = {-inff, };
q[] = q[] = {inff, }; query(l,r,,n,,q[],q[],q[],q[],);
ll res = -inff;
for(int i=; i<=; i++){
for(int j=; j<=; j++){
if(q[i].se != q[j].se && q[i].se && q[j].se){
res = max(res, abs(q[i].fi - q[j].fi));
}
}
} pli e[];
e[] = e[] = {-inff, };
e[] = e[] = {inff, };
query(l,r,,n,,e[],e[],e[],e[],); for(int i=; i<=; i++){
for(int j=; j<=; j++){
if(e[i].se != e[j].se && e[i].se && e[j].se){
res = max(res, abs(e[i].fi - e[j].fi));
}
}
} if(res <= -inff) res = ;
printf("%lld\n", res);
}
}
} return ;
}
最新文章
- 使用T-SQL找出执行时间过长的作业
- react+redux官方实例TODO从最简单的入门（3）-- 删
- php 简单分页类
- hibernate操作数据库例子
- Spring Mvc 返回机制
- codevs 4919 线段树练习4
- 国内的一些开源镜像站汇总,EPEL源
- apache的一些基本配置
- 转：完善eclipse+pdt作php开发中的代码提示能力
- 在PHP语言中使用JSON
- IT之光
- linux nginx常见问题及优化，压力测试，tomcat服务器优化
- Vue.js——60分钟组件快速入门
- Javascript DOM(2)
- C#4并行计算
- Docker安装管理界面portainer
- git常用命令以及如何与fork别人的仓库保持同步
- 并查集 牛客练习赛41 C抓捕盗窃犯
- mysql自增主键
- java基础-day8