BZOJ传送门 luogu免权限地址 Set求大于x的最小值的模板题。注意set.lower_bound()如果找不到就会返回set.end()
#include<cstdio> #include<algorithm> #include<cstring> #include<set> #define ms(i,j) memset(i,j, sizeof i); using namespace std; int n; struct qj { int l, r; bool Operator <(const qj &b) const { if (r<b.r) return true; if (r>b.r) return false; return l<b.l; }};set<qj> s; char inpu(){ char ans = getchar(); while ((ans!='A')&&(ans!='B')) ans = getchar(); return ans;}int main() { scanf("%d", &n); for (int i=1;i<=n;i++) { char type = inpu(); if (type=='A') { int cnt = 0; int l,r; scanf("%d%d", &l, &r); qj a = (qj){l,r}; while (true) { set<qj>::iterator it = s.lower_bound((qj){0,l});//找第一个比a大的qj int xl = it->l, xr = it->r; if (it!=s.end())//set里还有元素 { if (!(a.r < it->l))//有覆盖 { s.erase(it); cnt++; continue; } } s.insert(a); break; } PRintf("%d/n", cnt); } else printf("%d/n", s.size()); } return 0; }新闻热点
疑难解答
