$O(nlogn)$
- 将N头牛的结束吃草时间从小到大排序
- 遍历排序后的每头牛
2.1 查找 结束被吃时间 比当前牛的 开始吃草时间 更 早 的畜栏中,结束被吃时间 最 晚 的畜栏
2.2 如果有满足条件的畜栏,则更新畜栏的结束被吃时间为 当前牛的结束吃草时间
2.3 如果没有,则新开辟畜栏,结束被吃时间为 当前牛的结束吃草时间
其中,查找比x更小的数中最大数即找前驱,用平衡树实现
平衡树每个节点代表一个畜栏,排序key为畜栏的结束被吃时间,初始时只包含左右哨兵
开辟畜栏时,向平衡树插入新节点,值为当前牛的结束吃草时间
更新畜栏时,删除原畜栏后,重新插入
C 代码
#include<stdio.h>
#define N 50010
#define INF 1e9
int x[N], y[N], map[N];
int n;
int group[N];
int groupIdx;
int belongsTo[N];
void sort(int st, int ed){
if(st >= ed) return;
int l = st - 1, r = ed + 1;
int mid = y[(st + ed) / 2];
while(l < r){
do l++; while(y[l] < mid);
do r--; while(y[r] > mid);
if(l < r){
int t = y[l];
y[l] = y[r];
y[r] = t;
t = x[l];
x[l] = x[r];
x[r] = t;
t = map[l];
map[l] = map[r];
map[r] = t;
}
}
sort(st, r), sort(r + 1, ed);
}
struct _n{
int s[2], v, gid, p, size;
}tr[N];
int root, idx;
void pushUp(int x){
tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1;
}
void rotate(int x){
int y = tr[x].p, z = tr[y].p;
int k = tr[y].s[1] == x;
tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
tr[tr[x].s[k ^ 1]].p = y, tr[y].s[k] = tr[x].s[k ^ 1];
tr[y].p = x, tr[x].s[k ^ 1] = y;
pushUp(y), pushUp(x);
}
void splay(int x, int u){
while(tr[x].p != u){
int y = tr[x].p, z = tr[y].p;
if(z != u){
if((tr[z].s[1] == y) ^ (tr[y].s[1] == x)) rotate(x);
else rotate(y);
}
rotate(x);
}
if(!u) root = x;
}
void insert(int v, int gid){
int u = root, p = 0;
while(u) p = u, u = tr[u].s[v > tr[u].v]; // while(u && tr[u].v != v)
u = ++idx;
if(p) tr[p].s[v > tr[p].v] = u;
tr[u].p = p, tr[u].v = v, tr[u].gid = gid, tr[u].size = 1;
splay(u, 0);
}
int getV(int v){
int u = root;
// 只有v严格大于才去右侧查找,即使相等也去左侧,这样查到的结果一定严格小于v或等于v的第一个值
while(tr[u].s[v > tr[u].v]) u = tr[u].s[v > tr[u].v];
splay(u, 0);
return u;
}
int getPre(int v){ // 相等不算前驱。
int u = getV(v);
if(tr[u].v < v) return u; // tr[u].v < v,
int pre = tr[u].s[0];
while(tr[pre].s[1]) pre = tr[pre].s[1];
return pre;
}
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d%d", &x[i], &y[i]), map[i] = i;
sort(0, n - 1);
insert(-INF, 0), insert(INF, 0);
groupIdx = 1;
for(int i = 0; i < n; i++){
int pre = getPre(x[i]); // 端点不允许重合,所以查找不相等的前驱
// printf("x[i]: %d 'pre is %d\n", x[i], tr[pre].v);
if(tr[pre].v == -INF) {
belongsTo[map[i]] = groupIdx;
insert(y[i], groupIdx++);
}
else{
int gid = tr[pre].gid;
splay(pre, 0);
int ppre = tr[pre].s[0];
while(tr[ppre].s[1]) ppre = tr[ppre].s[1];
int pnext = tr[pre].s[1];
while(tr[pnext].s[0]) pnext = tr[pnext].s[0];
// printf("x[i]: %d, pre: %d, pre.gid: %d, ppre: %d, pnext: %d\n", x[i], tr[pre].v, tr[pre].gid,
// tr[ppre].v, tr[pnext].v);
splay(ppre, 0), splay(pnext, ppre);
tr[pnext].s[0] = 0;
pushUp(pnext), pushUp(ppre);
insert(y[i], gid);
belongsTo[map[i]] = gid;
}
}
printf("%d\n", groupIdx - 1);
for(int i = 0; i < n; i++) printf("%d\n", belongsTo[i]);
return 0;
}