原题链接

题解

找出右端点大于等于当前区间的左端点且左端点小于等于当前区间的右端点的所有区间，由于查询前这样的区间具有单调性，所以可以用二分，但是怎么快速删除呢？
欸stl大法来了，用set存储区间，查找和删除和添加都是 \(logn\) 级的

code

#include<bits/stdc++.h>
using namespace std;

struct plan
{
    int l,r;
    bool operator<(const plan &b)const
    {
        if(b.r!=r) return r<b.r;
        //按右端点排序，为什么？我们用Lower bound是为了找出第一个大于等于当前区间的区间，按右端点排序后，一直到第一个it.l大于r之前的区间都是冲突区间，这样每个区间只会判断一次
        else return l<b.l;//这样使得右端点与当前区间左端点重合的区间一定小于查询区间，见下文
    }
};
set<plan> q;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        char op;
        cin>>op;
        if(op=='A')
        {
            int l,r;
            cin>>l>>r;
            auto it=q.lower_bound({0,l});//太核心了这里，查找第一个右端点大于等于当前区间左端点的区间
            int sum=0;
            if(it!=q.end())
            {
                while(it!=q.end()&&it->l<=r)//set里原本存着的区间一定不重合
                {
                    q.erase(it);
                    sum++;
                    it=q.lower_bound({0,l});
                }
            }
            q.insert({l,r});
            cout<<sum<<endl;
        }
        else cout<<q.size()<<endl;
    }
    return 0;
}