发布于2018年9月13日 由itewqq[STL][降维] UVa 11020 Efficient Solutions 收获： 1 我以前一直疑惑set能不能边遍历边erase，现在看来是可以的，erase(it++)就可以 2 二维转一维的思想，经常使用。 //#include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; const int maxn=40000+50; const int mod=1e9+7; multiset > S; multiset >::iterator it; int main() { int t,cs=0,n,a,b; scanf("%d",&t); pair p; while(t--) { S.clear(); cs++; if(cs>1) puts("");//presentation error scanf("%d",&n); printf("Case #%d:\n",cs); for (int i=1;i<=n;i++) { scanf("%d%d",&p.first,&p.second); b=p.second; if(!S.empty()) { it=S.lower_bound(p); if(it==S.begin()||(--it)->second>b) { S.insert(p); it=S.upper_bound(p); while(it!=S.end()&&it->second>=b)S.erase(it++);//++ and erase } printf("%d\n",S.size()); } else { S.insert(p); printf("1\n"); } } } return 0; }
