前言
和同学在用ACWING比赛的时候遇到了这道题目,然后当场敲了一棵平衡树,发现没有题解写这个这不废话吗?于是就来写一篇。
思路
考虑贪心,如果将给定的区间按$r$排序,那么当我们从前到后安排的时候,原来分组规划我们用$c$记录一下当前组最右的点,然后当我们把新的一个区间放入分组时,会出现两种情况:
- 新建一个区间,$c$为$r$
- 选择一个合法区间,$c$为$r$
根据贪心,显然如果可以选择后者则尽量选择后者。
合法状态是什么呢?显然是$c<r$
那么问题就变成了在一堆数里面找前驱,显然可以使用平衡树维护了(线段数二分也是可以的)。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct Tree
{
int ls;
int rs;
int val;
int dis;
int siz;
}tree[N];
int tot = 0;
inline void push_up(int p)
{
tree[p].siz = tree[tree[p].ls].siz + tree[tree[p].rs].siz + 1;
}
inline pair<int , int> split(int p , int k)
{
if(p == 0)
{
return make_pair(0 , 0);
}
if(tree[p].val < k)
{
pair<int , int> t = split(tree[p].rs , k);
tree[p].rs = t.first;
push_up(p);
return make_pair(p , t.second);
}
else
{
pair<int , int> t = split(tree[p].ls , k);
tree[p].ls = t.second;
push_up(p);
return make_pair(t.first , p);
}
}
inline int merge(int u , int v)
{
if(u == 0 || v == 0)
{
return u + v;
}
if(tree[u].dis < tree[v].dis)
{
tree[u].rs = merge(tree[u].rs , v);
push_up(u);
return u;
}
else
{
tree[v].ls = merge(u , tree[v].ls);
push_up(v);
return v;
}
}
int root;
inline void ins(int k)
{
tot++;
tree[tot].val = k;
tree[tot].dis = rand();
tree[tot].siz = 1;
pair<int , int> x = split(root , k);
root = merge(merge(x.first , tot) , x.second);
}
inline void del(int k)
{
pair<int , int> x = split(root , k);
pair<int , int> y = split(x.second , k + 1);
y.first = merge(tree[y.first].ls , tree[y.first].rs);
root = merge(x.first , merge(y.first , y.second));
}
inline int find_pa(int k)
{
pair<int , int> t = split(root , k);
int res = tree[t.first].siz + 1;
root = merge(t.first , t.second);
return res;
}
inline int find_num(int k)
{
int p = root;
while(p)
{
if(tree[tree[p].ls].siz + 1 == k)
{
return tree[p].val;
}
if(tree[tree[p].ls].siz >= k)
{
p = tree[p].ls;
}
else
{
k -= tree[tree[p].ls].siz + 1;
p = tree[p].rs;
}
}
}
inline int find_pre(int k)
{
return find_num(find_pa(k) - 1);
}
struct Node
{
int l;
int r;
}node[N];
bool cmp_Node(Node a , Node b)
{
return a.r < b.r;
}
signed main()
{
ios::sync_with_stdio(false);
int n;
cin >> n;
for(int i = 1 ; i <= n ; i++)
{
cin >> node[i].l >> node[i].r;
}
sort(node + 1 , node + n + 1 , cmp_Node);
ins(INT_MAX);
ins(INT_MIN);
int ans = 0;
for(int i = 1 ; i <= n ; i++)
{
int x = find_pre(node[i].l);
if(x == INT_MIN)
{
ins(node[i].r);
ans++;
}
else
{
del(x);
ins(node[i].r);
}
}
cout << ans;
return 0;
}
把这么简单的题目做成这样,果然我还是太菜了。。。
当事人在此,我俩成功打了半小时
%拜您