M_sea

洛谷2906 牛的街区Cow Neighborhoods
Luogu分析毒瘤题。两个点$(x_1,y_1),(x_2,y_2)$的曼哈顿距离可以转为$max\left\{|...
扫描右侧二维码阅读全文
26
2018/10

洛谷2906 牛的街区Cow Neighborhoods

Luogu

分析

毒瘤题。

两个点$(x_1,y_1),(x_2,y_2)$的曼哈顿距离可以转为$max\left\{|(x_1+y_1)-(x_2+y_2)|,|(x_1-y_1)-(x_2-y_2)|\right\}$

就是说,把点对坐标转化为$(x+y,x-y)$,那么曼哈顿距离就转化为了$max\left\{|x_1-x_2|,|y_1-y_2|\right\}$

然后维护$x$的单调队列,然后用平衡树维护$y$坐标,求前驱后继,若≤$c$就用并查集合并。

最后求答案就好了。

细节见代码。

代码

哪位大佬可以帮我卡到最优解啊qwq

#include <bits/stdc++.h>
#define re register
typedef long long LL;
using namespace std;

inline int read() {
    int X=0,w=0; char c=getchar();
    while (!isdigit(c)) { if (c=='-') w=1; c=getchar(); }
    while (isdigit(c)) X=X*10+c-48,c=getchar();
    return w?-X:X;
}

const int MAXN=100000+10;
const LL INF=1e18+7;

struct Union_Find_Set {
    int sz[MAXN],root[MAXN];
    inline void init(const int n) {
        for (re int i=0;i<=n;++i) sz[i]=1,root[i]=i;
    }
    inline int find(const int x) {
        return root[x]==x?x:root[x]=find(root[x]);
    }
    inline void merge(int a,int b) {
        a=find(a),b=find(b);
        if (a==b) return;
        if (sz[a]>sz[b]) root[b]=a,sz[a]+=sz[b],sz[b]=0;
        else root[a]=b,sz[b]+=sz[a],sz[a]=0;
    }
    inline void Print(int n) {
        re LL ans1=0,ans2=0;
        for (re int i=1;i<=n;++i) ans1+=(root[i]==i),ans2=max(ans2,(LL)sz[i]);
        printf("%lld %lld\n",ans1,ans2);
    }
};

struct Point {
    LL x,y; int id;
    bool operator <(const Point& rhs) const {
        return y<rhs.y;
    }
};

inline int cmp(const Point& a,const Point& b) {
    return a.x<b.x;
}

Union_Find_Set S;
multiset<Point> T;
Point a[MAXN];

int main() {
    re int n=read(),c=read(); S.init(n);
    for (re int i=1;i<=n;++i) {
        LL x=read(),y=read();
        a[i].x=x+y,a[i].y=x-y,a[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    T.insert((Point){0,-INF,0});
    T.insert((Point){0,INF,0});
    int pre=1; T.insert(a[1]);
    multiset<Point>::iterator it;
    for (re int i=2;i<=n;++i) {
        while (a[i].x-a[pre].x>c) T.erase(T.find(a[pre++]));
        it=T.lower_bound(a[i]);
        Point j=*it;
        if (j.y-a[i].y<=c) S.merge(j.id,a[i].id);
        j=*(--it);
        if (a[i].y-j.y<=c) S.merge(j.id,a[i].id);
        T.insert(a[i]);
    }
    S.Print(n);
    return 0;
}
最后修改:2018 年 11 月 09 日 05 : 56 PM

发表评论