【题解】P2161[SHOI2009]会场预约(set)

【题解】[P2161 SHOI2009]会场预约

题目很像[【题解】APIO2009]会议中心

\(set\)大法好啊！

然后我们有个小\(trick\)(炒鸡帅)，就是如何优雅地判断线段交？

struct E{

          int l,r;

          E(int a,int b){l=a,r=b;}

          inline bool operator <(const E&a)const{return r<a.l;}

};

真的太帅了！！我思维不行啊！！别人太强了！

众所周知，只要知道一个小于号，就知道所有的逻辑运算了：

"a==b" -> "!(a<b)&&!(b<a)"
"a> b" -> "!(a<b)&&!a==b"

其他以此类推。

那么我们这样重载运算符之后，我们发现：

"a==b" -> "(a.l<=b.l&&a.r>=b.l)||(b.l<=a.l&&b.r>=a.l)"
"a> b" -> "a.l>b.r"

所以当\(a=b\)时，就是两线段相交，\(a<b\)表示\(a\)完全在\(b\)左边。\(a>b\)表示\(b\)完全在\(a\)右边。

所以直接把所有线段放入\(set\)这个很牛逼的\(stl\)，然后直接跑即可，加入的时候把\(set\)里所有和待加入元素"相等"的元素删掉。每个线段都只会操作一次，\(O(n\log n)\)

我们这样做的理由就是利用了\(set\)的"=="号的性质，利用\(stl\)的一部分性质解决自己的问题，真的太强了。

#include<bits/stdc++.h>

using namespace std;  typedef long long ll;

template < class ccf > inline ccf qr(ccf ret){      ret=0;

      register char c=getchar();

      while(c<48||c>57) c=getchar();

      while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();

      return ret;

}inline int qr(){return qr(1);}

struct E{

      int l,r;

      E(int a,int b){l=a,r=b;}

      inline bool operator <(const E&a)const{return r<a.l;}

};int n;set< E > s;

int main(){

      for(register int t=qr(),k;t;--t){

	    register char c=getchar();

	    while(c!='A'&&c!='B') c=getchar();

	    if(c=='A'){

		  register int t1,t2,t3=0;

		  t1=qr();t2=qr();

		  register E now(t1,t2);

		  for(register auto f=s.find(now);f!=s.end();f=s.find(now))

			++t3,s.erase(f);

		  s.insert(now);

		  printf("%d\n",t3);

	    }

	    else k=s.size(),printf("%d\n",k);

      }

      return 0;

}

巴特西

【题解】P2161[SHOI2009]会场预约(set)

【题解】[P2161 SHOI2009]会场预约

最新文章

热门文章