題目傳送門

嗯，這道題的標簽是STL，因為這個STL用的確實太妙了

---

這道題目要求維護一堆區(qū)間，而一個重要的操作是要刪除所有與新區(qū)間沖突的區(qū)間

雖然可以用\(Splay\)來操作，但用STL里的set也絕對不虛
其中最精妙的當屬這個重載運算符
它的意思是當兩個區(qū)間相交時，這兩個區(qū)間相等

struct zzz {int l, r;bool operator < (const zzz &y) const { return r < y.l; } }; set <zzz> q;

重載完運算符，再憑借set的find函數(shù)，就可以很容易的通過此題

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <set> #define LL long long using namespace std; LL read() {LL k = 0; char c = getchar();while(c < '0' || c > '9') c = getchar();while(c >= '0' && c <= '9')k = k * 10 + c - 48, c= getchar();return k; } char read_c() {char c = getchar();while(c != 'A' && c != 'B') c = getchar();return c; } struct zzz {int l, r;bool operator < (const zzz &y) const { return r < y.l; } }; set <zzz> q; int main() {int m = read();while(m--) {char opt = read_c();if(opt == 'A') {int l = read(), r = read(), cnt = 0;zzz k = (zzz){l, r};set<zzz> :: iterator it = q.find(k);//將相交的區(qū)間全都刪去while(it != q.end()) {++cnt; q.erase(it);it = q.find(k);}q.insert(k);printf("%d\n", cnt);}else printf("%d\n", q.size());}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/wxl-Ezio/p/11011374.html

總結(jié)

以上是生活随笔為你收集整理的SHOI2009 会场预约的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。