当前位置： 移动技术网 > IT编程>开发语言>C/C++ > bzoj2648 SJY摆棋子

bzoj2648 SJY摆棋子

2019年06月14日  | 移动技术网IT编程  | 我要评论

疯狂炒作团台词,走进李元芳,鳌江到温州动车

题目链接

思路

\(kd-tree\)模板题

代码

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
#define ls tr[rt].ch[0]
#define rs tr[rt].ch[1]
const int n = 1000000 + 100,inf = 1e9;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int ch[2],d[2],mx[2],mn[2];
}tr[n],tmp,a[n];
int n,m;
int ans,root;
int fx;
bool cmp(const node &a,const node &b) {
    return a.d[fx] < b.d[fx];
}
void up(int rt) {
    for(int i = 0;i <= 1;++i) {
        if(ls) tr[rt].mn[i] = min(tr[rt].mn[i],tr[ls].mn[i]),
            tr[rt].mx[i] = max(tr[rt].mx[i],tr[ls].mx[i]);
        if(rs) tr[rt].mn[i] = min(tr[rt].mn[i],tr[rs].mn[i]),
            tr[rt].mx[i] = max(tr[rt].mx[i],tr[rs].mx[i]);
    }
}
int build(int l,int r,int now) {
    fx = now;
    int mid = (l + r) >> 1;
    nth_element(a + l,a + mid,a + r + 1,cmp);
    tr[mid] = a[mid];
    int rt = mid;
    for(int i = 0;i <= 1;++i) tr[mid].mn[i] = tr[mid].mx[i] = tr[mid].d[i];
        if(l < mid) ls = build(l,mid - 1,now ^ 1);
        if(r > mid) rs = build(mid + 1,r,now ^ 1);
        up(mid);
        return mid;
}
void insert(int rt,int now) {
    if(tmp.d[now] >= tr[rt].d[now]) {
        if(rs) insert(rs,now ^ 1);
        else {
            rs = ++n;
            tr[n] = tmp;
            for(int i = 0;i <= 1;++i) tr[n].mn[i] = tr[n].mx[i] = tr[n].d[i];
        }
    }
    else {
        if(ls) insert(ls,now ^ 1);
        else {
            ls = ++n;
            tr[n] = tmp;
            for(int i = 0;i <= 1;++i) tr[n].mn[i] = tr[n].mx[i] = tr[n].d[i];
        }
    }
    up(rt);
}
int dis(const node &a,const node &b) {
    return abs(a.d[0] - b.d[0]) + abs(a.d[1] - b.d[1]);
}
int get(node a,node b) {
    int ret = 0;
    for(int i = 0;i <= 1;++i) ret += max(0,a.mn[i] - b.d[i]);
    for(int i = 0;i <= 1;++i) ret += max(0,b.d[i] - a.mx[i]);
    return ret;
}
void query(int rt,int now) {
    int d = dis(tr[rt],tmp),dl = inf,dr = inf;
    ans = min(ans,d);
    if(ls) dl = get(tr[ls],tmp);
    if(rs) dr = get(tr[rs],tmp);
    if(dl < dr) {
        if(dl < ans) query(ls,now ^ 1);
        if(dr < ans) query(rs,now ^ 1);
    }
    else {
        if(dr < ans) query(rs,now ^ 1);
        if(dl < ans) query(ls,now ^ 1);
    }
}
int query(int x,int y) {
    tmp.d[0] = x;tmp.d[1] = y;
    ans = inf;
    query(root,0);
    return ans;
}
void insert(int x,int y) {
    tmp.d[0] = x;tmp.d[1] = y;
    insert(root,0);
}
int main() {
    // freopen("2648/17.in","r",stdin);
    n = read(),m = read();
    for(int i = 1;i <= n;++i) {
        a[i].d[0] = read();a[i].d[1] = read();
    }
    root = build(1,n,0);
    for(int i = 1;i <= m;++i) {
        int opt = read(),x = read(),y = read();
        if(opt == 1) insert(x,y);
        else printf("%d\n",query(x,y));
    }
    return 0;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网