既见君子

同济医学生的起落落落落人生记录

BZOJ 2648 SJY摆棋子

带插入的kdtree,在bz上面交一直T,然后本机跑数据感觉是15s以内出答案,不知所措,到后来把自己的程序和某个标程改得一模一样还是过不了,大概是rp问题吧,还是弃疗算了。但是这种kdtree的写法让插入非常轻松,感觉写法非常优美所以就粘过来好啦。

//本题似乎是因为数据水才可以过的(但是我没过),否则要类似替罪羊树的写法不平衡了之后需要重构。

//update:某yyr大爷让我不要放弃,maya终于在最后找到了错误的地方,说起来也非常蠢,就是build里面还没有nth_element就给T[mid].d赋值了。吸取教训吸取教训,然而本机确实跑的过阿嘤嘤嘤。现在的代码就是A过的啦。

code:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1000000+5;
const int maxk=3;
int k=2,which;
int Read(){
        int y=0,f=1;
        char c=getchar();
        while(isspace(c)) c=getchar();
        if(c=='-'){
                f=-1;
                c=getchar();
        }
        while(c<='9'&&c>='0'){
                y=10*y+c-'0';
                c=getchar();
        }
        return f*y;
}
struct Point{
        int l,r,p[maxk],min[maxk],max[maxk],d;
} T[maxn],op;
bool cmp(const Point &a,const Point &b){
    return a.p[which]<b.p[which];
}
void mymin(int &x,int y){if(y<x) x=y;}
void mymax(int &x,int y){if(y>x) x=y;}
void update(int a,int b){
        for(int i=1;i<=k;++i) mymin(T[a].min[i],T[b].min[i]),mymax(T[a].max[i],T[b].max[i]);
}
int dis(int a,int b){
        int ret=0;
        for(int i=1;i<=k;++i) ret+=abs(T[b].p[i]-T[a].p[i]);
        return ret;
}
int ans,root;
double f[3];
const int inf=0x3f3f3f3f;
int value(int a,int b){
        int ret=0;
        for(int i=1;i<=k;++i){
                if(T[b].p[i]<T[a].min[i]) ret+=T[a].min[i]-T[b].p[i];
                if(T[b].p[i]>T[a].max[i]) ret+=T[b].p[i]-T[a].max[i];
        }
        return ret;
}
double sqr(const double &v){
        return v*v;
}
int build(int L,int R){
        if(L>R) return 0;
        int mid=(L+R)>>1;
        which=1;
        for(int i=1;i<=k;++i){
                f[i]=0;
                double ave=0;
                for(int j=L;j<=R;++j) ave+=T[j].p[i];
                ave/=(R-L+1);
                for(int j=L;j<=R;++j) f[i]+=sqr(T[j].p[i]-ave);
        }
        if(f[2]>f[1]) which=2;
        nth_element(T+L,T+mid,T+R+1,cmp);
        T[mid].d=which;
        T[mid].l=build(L,mid-1);if(T[mid].l) update(mid,T[mid].l);
        T[mid].r=build(mid+1,R);if(T[mid].r) update(mid,T[mid].r);
        return mid;
}
void query(int now,int q){
        int tmpdis=dis(now,q);if(tmpdis<ans) ans=tmpdis;
        int dl=T[now].l?value(T[now].l,q):inf;
        int dr=T[now].r?value(T[now].r,q):inf;
        if(dl<dr){
                if(ans>dl) query(T[now].l,q);
                if(ans>dr) query(T[now].r,q);
        }
        else {
                if(ans>dr) query(T[now].r,q);
                if(ans>dl) query(T[now].l,q);
        }
}
void insert(int q){
        int now=root;
        for(;;){
                update(now,q);
                int d=T[now].d;
                if(T[q].p[d]<=T[now].p[d]){
                        if(!T[now].l){
                                T[now].l=q;
                                T[q].d=1;
                                return ;
                        }
                        else now=T[now].l;
                }
                else {
                        if(!T[now].r){
                                T[now].r=q;
                                T[q].d=1;
                                return ;
                        }
                        else now=T[now].r;
                }
        }
}
int main(){
//        freopen("2648.in","r",stdin);
//        freopen("2648.out","w",stdout);
        int n,m,len;
        scanf("%d%d",&n,&m);
        len=n;
        int tmp;
        for(int i=1;i<=n;++i) 
                for(int j=1;j<=k;++j)
                        T[i].p[j]=Read(),T[i].min[j]=T[i].max[j]=T[i].p[j];
        root=build(1,n);
        for(int i=1;i<=m;++i){
                tmp=Read();
                len++;for(int j=1;j<=k;++j) T[len].p[j]=Read(),T[len].min[j]=T[len].max[j]=T[len].p[j];
                if(tmp==1){
                        insert(len);
                }
                else {
                        ans=inf;
                        query(root,len);
                        printf("%d\n",ans);
                }
        }
        return 0;
}

评论
热度(3)
©既见君子
Powered by LOFTER