题目链接 发现这道题可以用STL做，就犯了懒，学了学set的用法，不得不佩服c++的发明者啊 首先先感谢这位博主 set，顾名思义，就是数学上的集合——每个元素最多只出现一次，并且set中的元素已经从小到大排好序。 头文件：#include < set > 常用操作： begin() 返回set容器的第一个元素的地址 end() 返回set容器的最后一个元素地址 clear() 删除set容器中的所有的元素 empty() 判断set容器是否为空 max_size() 返回set容器可能包含的元素最大个数 size() 返回当前set容器中的元素个数 erase(it) 删除迭代器指针it处元素 insert(a) 插入某个元素
有了这个，便可以很容易的处理这道题目了，我们利用lower_bound寻找比当前插入元素的l大的r，即为不合法的元素，删去，依次处理就行了 细节：这个元素l&&r<查询出来的l，仍然是没有重叠的，即元素合法 需要注意的是end返回的是一个越界的地址，与lower_bound相似
#include <iostream> #include <cstdio> #include <set> using namespace std; struct node{//以r为第一关键字排序，显然 int lf,rt; bool operator<(const node&v)const{ if(rt==v.rt) return lf<v.lf; return rt<v.rt; } }; set<node> s;//定义set容器 int main() { int n; set<node>::iterator it; scanf("%d",&n); for(int i=1;i<=n;i++) { char a; cin>>a; if(a=='A') { int l,r; scanf("%d%d",&l,&r); int cnt=0; while(1) { it=s.lower_bound((node){0,l}); if(it!=s.end()&&r>=it->lf)//注意细节处理 { s.erase(it);//删去it地址的元素 cnt++; continue; } break; } s.insert((node){l,r});//插入新元素 printf("%d\n",cnt); } else printf("%d\n",s.size());//输出set容器中元素的个数 } return 0; }方法2：线段树 我们先将所有的操作读入进来，进行离线 cnt[i]表示加入i需要删除的前面的区间的个数 倒着进行处理，在线段树中维护最小值，先查询插入区间中的最小值 假设插入4时，它的区间中有5,6,那我们就将5的cnt++，因为4与5,6,同时矛盾时，5插入时4已删除，4对6已经没有影响，所以维护最小值
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int cnt[300001]; int st[300001*4]; int m[300001*4]; struct we{ char c; int l,r; }a[200100]; inline void push_down(int o) { m[(o<<1)]=min(m[o],m[(o<<1)]); st[(o<<1)]=min(st[(o<<1)],m[o<<1]); m[(o<<1)+1]=min(m[(o<<1)+1],m[o]); st[(o<<1)+1]=min(st[(o<<1)+1],m[(o<<1)+1]); } void query(int o,int l,int r,int ql,int qr,int sum) { if(ql<=l&&qr>=r) { m[o]=min(m[o],sum); st[o]=m[o]; return; } if(m[o]!=m[0]) push_down(o); int mid=(l+r)>>1; if(ql<=mid) query((o<<1),l,mid,ql,qr,sum); if(mid+1<=qr) query((o<<1)+1,mid+1,r,ql,qr,sum); st[o]=min(st[(o<<1)],st[(o<<1)|1]); } int ask(int o,int l,int r,int ql,int qr) { if(ql<=l&&qr>=r) return st[o]; if(m[o]!=m[0]) push_down(o); int mid=(l+r)>>1; int ans=m[0]; if(ql<=mid) ans=min(ans,ask((o<<1),l,mid,ql,qr)); if(mid+1<=qr) ans=min(ask((o<<1)+1,mid+1,r,ql,qr),ans); return ans; } int main() { memset(m,127,sizeof(m)); memset(st,127,sizeof(st)); int n; scanf("%d",&n); for(int i=1;i<=n;i++) { cin>>a[i].c; if(a[i].c=='A') cin>>a[i].l>>a[i].r; } for(int i=n;i>=1;i--) { if(a[i].c=='A') { int d=ask(1,1,100001,a[i].l,a[i].r); if(d!=m[0]) cnt[d]++; query(1,1,100001,a[i].l,a[i].r,i); } } int ans=0; for(int i=1;i<=n;i++) { if(a[i].c=='A') { ans=ans+1-cnt[i]; printf("%d\n",cnt[i]); } else printf("%d\n",ans); } return 0; }