【BZOJ2648】SJY摆棋子 – 徐亦轲的博客

蒯了一遍模板发现好多机房神犇都切过这道题了

多年没刷题都跟不上节奏了现在才会kdt

建树的方法挺鬼畜的每次换一维选最中间的点切开再往两边建树

然后插入和二叉搜索树差不多

查询就是一路往下查剪剪枝

复杂度特别鬼畜主要是看剪枝

// <2648.cpp> - 12/27/16 19:14:13
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=1000010;
const int INF=1e9;
#define fi01() for(int i=0;i<=1;i++)
bool K;
struct T{
	int a[2],mn[2],mx[2],l,r;
    T(int x=0,int y=0){a[0]=x;a[1]=y;l=r=0;}
    bool operator <(const T b) const{return a[K]<b.a[K];}
}t[MAXN],S;
int n,root;
void update(int x){
    fi01(){
        if(t[x].l){
            t[x].mn[i]=min(t[x].mn[i],t[t[x].l].mn[i]);
            t[x].mx[i]=max(t[x].mx[i],t[t[x].l].mx[i]);
        }
        if(t[x].r){
            t[x].mn[i]=min(t[x].mn[i],t[t[x].r].mn[i]);
            t[x].mx[i]=max(t[x].mx[i],t[t[x].r].mx[i]);
        }
    }
}
int build(int l,int r,bool p){
    K=p;
    int m=l+r>>1;
    nth_element(t+l,t+m,t+r+1);
    fi01()t[m].mn[i]=t[m].mx[i]=t[m].a[i];
    if(l<m)t[m].l=build(l,m-1,p^1);
    if(r>m)t[m].r=build(m+1,r,p^1);
    update(m);
    return m;
}
int ans;
inline int gd(T &b){return abs(S.a[0]-b.a[0])+abs(S.a[1]-b.a[1]);}
inline int get(int k){
    if(!k)return INF;
    int g=0;
    fi01()g+=max(0,t[k].mn[i]-S.a[i])+max(0,S.a[i]-t[k].mx[i]);
    return g;
}
void query(int k){
    ans=min(ans,gd(t[k]));
    int dl=get(t[k].l),dr=get(t[k].r);
    if(dl<dr){
        if(dl<ans)query(t[k].l);
        if(dr<ans)query(t[k].r);
    }else{
        if(dr<ans)query(t[k].r);
        if(dl<ans)query(t[k].l);
    }
}
void insert(int k,bool p){
    K=p;
    if(S<t[k]){
        if(t[k].l)insert(t[k].l,p^1);
        else{
            t[t[k].l=++n]=S;
            fi01()t[n].mn[i]=t[n].mx[i]=t[n].a[i];
        }
    }else{
        if(t[k].r)insert(t[k].r,p^1);
        else{
            t[t[k].r=++n]=S;
            fi01()t[n].mn[i]=t[n].mx[i]=t[n].a[i];
        }
    }
    update(k);
}
int main(){
    n=gi();int m=gi();
    for(int i=1;i<=n;i++)t[i].a[0]=gi(),t[i].a[1]=gi();
    root=build(1,n,0);
    while(m--){
        int op=gi(),x=gi(),y=gi();
        S=T(x,y);
        if(op==1)insert(root,0);
        else{
            ans=INF;
            query(root);
            printf("%d\n",ans);
        }
    }
    return 0;
}

100

101

102

103

104

// <2648.cpp> - 12/27/16 19:14:13

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=1000010;

const int INF=1e9;

#define fi01() for(int i=0;i<=1;i++)

bool K;

struct T{

int a[2],mn[2],mx[2],l,r;

T(int x=0,int y=0){a[0]=x;a[1]=y;l=r=0;}

bool operator <(const T b) const{return a[K]<b.a[K];}

}t[MAXN],S;

int n,root;

void update(int x){

fi01(){

if(t[x].l){

t[x].mn[i]=min(t[x].mn[i],t[t[x].l].mn[i]);

t[x].mx[i]=max(t[x].mx[i],t[t[x].l].mx[i]);

}

if(t[x].r){

t[x].mn[i]=min(t[x].mn[i],t[t[x].r].mn[i]);

t[x].mx[i]=max(t[x].mx[i],t[t[x].r].mx[i]);

}

int build(int l,int r,bool p){

K=p;

int m=l+r>>1;

nth_element(t+l,t+m,t+r+1);

fi01()t[m].mn[i]=t[m].mx[i]=t[m].a[i];

if(l<m)t[m].l=build(l,m-1,p^1);

if(r>m)t[m].r=build(m+1,r,p^1);

update(m);

return m;

}

int ans;

inline int gd(T &b){return abs(S.a[0]-b.a[0])+abs(S.a[1]-b.a[1]);}

inline int get(int k){

if(!k)return INF;

int g=0;

fi01()g+=max(0,t[k].mn[i]-S.a[i])+max(0,S.a[i]-t[k].mx[i]);

return g;

}

void query(int k){

ans=min(ans,gd(t[k]));

int dl=get(t[k].l),dr=get(t[k].r);

if(dl<dr){

if(dl<ans)query(t[k].l);

if(dr<ans)query(t[k].r);

}else{

if(dr<ans)query(t[k].r);

if(dl<ans)query(t[k].l);

}

void insert(int k,bool p){

K=p;

if(S<t[k]){

if(t[k].l)insert(t[k].l,p^1);

else{

t[t[k].l=++n]=S;

fi01()t[n].mn[i]=t[n].mx[i]=t[n].a[i];

}

}else{

if(t[k].r)insert(t[k].r,p^1);

else{

t[t[k].r=++n]=S;

fi01()t[n].mn[i]=t[n].mx[i]=t[n].a[i];

}

update(k);

}

int main(){

n=gi();int m=gi();

for(int i=1;i<=n;i++)t[i].a[0]=gi(),t[i].a[1]=gi();

root=build(1,n,0);

while(m--){

int op=gi(),x=gi(),y=gi();

S=T(x,y);

if(op==1)insert(root,0);

else{

ans=INF;

query(root);

printf("%d\n",ans);

}

return 0;

}

2 评论

最旧