qwq___qaq @ 2021-12-06 23:02:19
AC 4 个，WA 3 个，MLE 3 个，具体思路如下：
首先用堆维护最后贴上去的位置，然后用 2 棵红黑树分别标记起点和终点，如果当前位置贴的是队首；如果堆首的右端点已过，就弹出，直到堆为空或堆首可以选择为止。最后用平衡树统计答案。
by qwq___qaq @ 2021-12-06 23:02:26
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int res=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9'){
res=(res<<1)+(res<<3)+(ch^'0');
ch=getchar();
}
return res;
}
int n=read(),m=read(),a,b,minn=1e8,maxn;
bool vis[1005];
map<int,int> mp,vp;
priority_queue<int,vector<int>,less<int> > qaq;
set<int> s;
int main(){
for(int i=1;i<=m;++i)
a=read(),b=read(),mp[a]=i,vp[b]=i,minn=min(a,minn),maxn=max(maxn,b);
for(int i=minn;i<=maxn;++i){
if(mp[i])
qaq.push(mp[i]);
while(!qaq.empty()&&vis[qaq.top()])
qaq.pop();
if(!qaq.empty())
s.insert(qaq.top());
if(vp[i])
vis[vp[i]]=1;
}
printf("%d\n",s.size());
return 0;
}