[SHOI 2009] 会场预约

[题目链接]

https://www.lydsy.com/JudgeOnline/problem.php?id=2028

[算法]

直接用std :: set维护即可

时间复杂度 : O(NlogN)

[代码]

#include<bits/stdc++.h>
using namespace std; int n; struct segment
{
int l , r;
friend bool operator < (segment a , segment b)
{
if (a.r == b.r) return a.l < b.l;
else return a.r < b.r;
}
} ; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
template <typename T> inline void read(T &x)
{
T f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
int main()
{ scanf("%d" , &n);
set< segment > S;
for (int i = ; i <= n; i++)
{
char type[];
scanf("%s" , &type);
if (type[] == 'B')
{
printf("%d\n" , (int)S.size());
continue;
} else
{
int ans = ;
int l , r;
scanf("%d%d" , &l , &r);
while (true)
{
set< segment > :: iterator it = S.lower_bound((segment){ , l});
if (it == S.end()) break;
segment tmp = (*it);
if (tmp.l <= r)
{
S.erase(it);
++ans;
} else break;
}
printf("%d\n" , ans);
S.insert((segment){l , r});
}
} return ; }
上一篇:P2161 [SHOI2009]会场预约[线段树/树状数组+二分/STL]


下一篇:bzoj 2028(会场预约)