USACO08OPEN Cow Neighborhoods

发表于 | 分类于 |
字数统计: 770 字

题目地址

题解

这个绝对值很难搞啊。
拆开来试试看？

发现前两个是相反数，中间俩也是。
原式或。
这时候发现两个式子里面都是只与下标有关值的差，就设。
原式或。
我怎么知道取哪个?
不知道，就让他们都满足。
即使。
之后就是乱搞了，维护一下差即可，用并查集合并可行部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <set>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
int n,C,x[100005],y[100005],xx[100005],yy[100005],rk[100005];
int par[100005],cnt[100005],ans1=0,ans2=0,S=0,ans,loc;
int que[100005],f,r;

struct Tr{
    Tr *ch[2];
    int r,v,id;
    int cmp(int w,int z) const {
        if(w==v&&z==id)return -1;
        return w>v||(w==v&&z>id);
    }
};
Tr tree[400005],*root=NULL;
void rorate_tr(Tr* &tr,int d){
    Tr *k=tr->ch[d^1];
    tr->ch[d^1]=k->ch[d];
    k->ch[d]=tr,tr=k;
}
void insert_tr(Tr* &tr,int _v,int _id){
    if(tr==NULL){
        S++,tr=&tree[S],tr->v=_v,tr->id=_id;
        tr->ch[0]=tr->ch[1]=NULL,tr->r=rand();
        return ;
    }
    int d=tr->cmp(_v,_id);
    insert_tr(tr->ch[d],_v,_id);
    if(tr->ch[d]->r>tr->r)rorate_tr(tr,d^1);
}
void delete_tr(Tr* &tr,int _v,int _id){
    int d=tr->cmp(_v,_id);
    if(d==-1){
        if(tr->ch[0]==NULL)tr=tr->ch[1];
        else if(tr->ch[1]==NULL)tr=tr->ch[0];
        else{
            int d_=(tr->ch[0]->r>tr->ch[1]->r);
            rorate_tr(tr,d_),delete_tr(tr->ch[d_],_v,_id);
        }
    }else delete_tr(tr->ch[d],_v,_id);
} 
void previous(Tr *tr,int _v){
    if(tr==NULL)return ;
    if(_v>=tr->v)
        ans=tr->v,loc=tr->id,previous(tr->ch[1],_v);
    else previous(tr->ch[0],_v);
}
void success(Tr *tr,int _v){
    if(tr==NULL)return ;
    if(_v<tr->v)
        ans=tr->v,loc=tr->id,success(tr->ch[0],_v);
    else success(tr->ch[1],_v);
}

int Find(int k){
    if(k==par[k])return k;
    return (par[k]=(Find(par[k])));
}
void Unite(int u,int v){
    if(Find(u)==Find(v))return;
    par[Find(u)]=Find(v);
}
bool cmp(int ia,int ib){
    return xx[ia]<xx[ib]||(xx[ia]==xx[ib]&&yy[ia]<yy[ib]);
}
void init(){
    srand(21451);
    n=read(),C=read();
    for(int i=1;i<=n;i++)
        x[i]=read(),y[i]=read(),xx[i]=x[i]+y[i],yy[i]=x[i]-y[i],rk[i]=par[i]=i;
    sort(rk+1,rk+1+n,cmp);
}
void solve(){
    f=r=0,que[r++]=rk[1],insert_tr(root,yy[rk[1]],rk[1]);
    for(int i=2;i<=n;i++){
        int index=rk[i];
        while(r>f&&xx[index]-xx[que[f]]>C)
            delete_tr(root,yy[que[f]],que[f]),f++;
        ans=-INF,success(root,yy[index]);//查后缀
        if(ans>-INF&&ans-yy[index]<=C)Unite(loc,index);
        ans=INF,previous(root,yy[index]);//查前缀
        if(ans<INF&&yy[index]-ans<=C)Unite(loc,index);
        insert_tr(root,yy[index],index);
        que[r++]=index;
    }
    for(int i=1;i<=n;i++)cnt[Find(i)]++;
    for(int i=1;i<=n;i++)ans1+=(cnt[i]!=0),ans2=max(ans2,cnt[i]);
    printf("%d %d\n",ans1,ans2);
}
int main(){
    init();
    solve();
    return 0;
}