题目描述
本题需要快速查询阴阳龙所在的横线竖线和斜线上距离最近的点,因此不难想到用平衡树维护每一条横线、竖线、斜率为±1的直线。将横坐标作为第一关键字,纵坐标作为第二关键字,编号作为第三关键字插入。遍历每一条直线阴阳龙坐标的前驱和后继,找到距离最小值和阴阳龙到边界的距离取较小者即为题干中的k。
由于需要维护的信息较少,故可以采用STL中的set(底层是红黑树实现的平衡树,但是需要开O2优化才能跑的飞起,否则大部分测试点都过不了)来维护。
由于坐标最大可到1e9,而点只有1e5,所以不能存储坐标系里所有的线,只用存储需要用到的线。由于每次旋转都会导致引入新的坐标,故不能离线离散化处理,故需要在外层再套一层平衡树来维护所有直线组成的集合。
由于同一条横线上的点纵坐标值相等,竖线上的点横坐标值相等,斜率为1的直线上的点(x,y)y-x的值相同,斜率为-1的直线上的点(x,y)x+y的值相同,故维护这四种值的顺序即可。
由于外层平衡树如果采用set,那么对内层平衡树的修改就十分不便(因为修改set中的元素的信息很麻烦),所以外层平衡树需要自己手写一个,这里采用了treap(原本写了fhq-treap结果最后一个测试点怎么改都过不了,splay就更不用说了,被卡的晕过去),即便如此还是在TLE边缘疯狂试探,提交起来一会AC一会TLE。
C++ 代码
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include<set>
#include<unordered_map>
#include<map>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
const int N=1e5+10,INF=1e9+100;
struct node{
int x,y,id;
bool operator<(const node& b) const{
if(x!=b.x)return x<b.x;
if(y!=b.y)return y<b.y;
return id<b.id;
}
}nd[N*10];
struct Tree{
int l,r;
int v,key,size;
set<node> s;//用set维护直线上的点
}tr[10*N];//利用treap维护不同 种类直线的直线
int root[4],idx;//行 列 斜率为1 斜率为-1 的集合的根节点
int get_node(int v){
idx++;
tr[idx].v=v;
tr[idx].key=rand();
tr[idx].size=1;
tr[idx].s.insert({-INF,-INF,-INF});//哨兵
tr[idx].s.insert({INF,INF,INF});
return idx;
}
void rotate_left(int& p)
{
int q=tr[p].r;
tr[p].r=tr[q].l,tr[q].l=p,p=q;
}
void rotate_right(int& p)
{
int q=tr[p].l;
tr[p].l=tr[q].r;tr[q].r=p,p=q;
}
void insert(int& p,int x)
{
if(!p){p=x;return;}
if(tr[x].v==tr[p].v)return;
if(tr[x].v<tr[p].v)
{
insert(tr[p].l,x);
if(tr[p].key<tr[tr[p].l].key)rotate_right(p);
}
else
{
insert(tr[p].r,x);
if(tr[p].key<tr[tr[p].r].key)rotate_left(p);
}
}
int find(int &root,int v){
int u=root;
while(u){
if(tr[u].v==v)return u;
else if(v<tr[u].v)u=tr[u].l;
else u=tr[u].r;
}
return u;
}
int n,m,p,q;
int get_k(int j,int x,int y){
if(j==0)return y;横线
if(j==1)return x;竖线
if(j==2)return y-x;//斜率为1的直线
return x+y;//斜率为-1的直线
}
void insert(int j,int k,int id){
int ptr=find(root[j],k);
if(!ptr){
ptr=get_node(k);
insert(root[j],ptr);
}
tr[ptr].s.insert(nd[id]);
}
PII ne[10];
map<PII,int> id;
PII rotate(int k,int x0,int y0,int x1,int y1){
int x=x1-x0,y=y1-y0;
int s=max(abs(x1-x0),abs(y1-y0));
x=x/s,y=y/s;
PII pos=ne[(id[{x,y}]+k)%8];
return {s*pos.first+x0,s*pos.second+y0};
}
node stk[15];int top;
int main(){
cin>>n>>m>>p>>q;
id[{1,0}]=0,id[{1,1}]=1,id[{0,1}]=2,id[{-1,1}]=3;
id[{-1,0}]=4;id[{-1,-1}]=5;id[{0,-1}]=6,id[{1,-1}]=7;
ne[0]={1,0},ne[1]={1,1},ne[2]={0,1},ne[3]={-1,1};
ne[4]={-1,0},ne[5]={-1,-1},ne[6]={0,-1},ne[7]={1,-1};
//预处理旋转后的坐标
for(int i=0;i<4;i++){
int t=get_node(INF);
insert(root[i],t);
t=get_node(-INF);
insert(root[i],t);
}
for(int i=1;i<=p;i++){
int x,y;
scanf("%d%d",&x,&y);
nd[i]={x,y,i};
for(int j=0;j<4;j++){
int k=get_k(j,x,y);
insert(j,k,i);
}
}
node u;
for(int i=0;i<q;i++){
int x,y,ch;
scanf("%d%d%d",&x,&y,&ch);
int d1=min(min(x-1,n-x),min(y-1,m-y)),d2=INF;
//d1:阴阳龙到边界的最短距离 d2:阴阳龙离最近员工的距离
int D,d;
for(int j=0;j<4;j++){
int k=get_k(j,x,y);
int ptr=find(root[j],k);
if(!ptr)continue;
auto u1=tr[ptr].s.lower_bound({x,y,-INF});
auto u2=tr[ptr].s.upper_bound({x,y,INF});
u1--;
int du1=max(abs(u1->x-x),abs(u1->y-y));
int du2=max(abs(u2->x-x),abs(u2->y-y));
d2=min(d2,min(du1,du2));
D=min(d2,d1);
if(du1<=D)stk[top++]=*u1;
if(du2<=D)stk[top++]=*u2;
}
if(!D||d1<d2){
top=0;
continue;
}
int k=0;
for(int j=0;j<top;j++){
u=stk[j];
d=max(abs(u.x-x),abs(u.y-y));
if(d==D)stk[k++]=stk[j];
}//将到阴阳龙距离大于D的点出栈
top=k;
while(top){
u=stk[--top];
PII t_old={u.x,u.y};
PII t_new=rotate(ch,x,y,u.x,u.y);
nd[u.id].x=t_new.first,nd[u.id].y=t_new.second;
for(int j=0;j<4;j++){
int k_old=get_k(j,t_old.first,t_old.second);
int p_old=find(root[j],k_old);
tr[p_old].s.erase({t_old.first,t_old.second,u.id});
int k_new=get_k(j,nd[u.id].x,nd[u.id].y);
insert(j,k_new,u.id);
}
}
}
LL ans=0;
for(int i=1;i<=p;i++){
ans^=((LL)i*nd[i].x+nd[i].y);
}
printf("%lld",ans);
}
请问treap为什么只用开10倍N?感觉坐标旋转后新加的点数不太好分析
雀食有点问题,能过属实侥幸了
可以模拟个内存池,最多同时存在4N个直线,set为空的时候就把那个节点的下标放进内存池,开新点就从内存池取点
请问ccfcsp有开o2优化吗?
估计有,我前两行代码就是手动开o2,结果ccf官网上没手动开反而比开了跑的快不少