题目

Solution

假设当前输入的区间为 [ l , r ] [l,r] [l,r]，那么当区间 [ x , y ] [x,y] [x,y]满足 l ≤ y , x ≤ r l≤y,x≤r l≤y,x≤r时，两区间相交
我一直在想怎么同时维护左右端点，后来才发现，直接以右端点为关键字，把所有区间放进 s e t set set里，
从小到大枚举 ≥ l ≥l ≥l的 y y y，如果 y y y对应的 x ≤ r x≤r x≤r，那么直接删掉，否则， l ≤ r &lt; x ≤ y l≤r&lt;x≤y l≤r<x≤y，直接 b r e a k break break，这样就是正确的
为什么呢？
假设有一个 y ′ ≥ y y&#x27;≥y y′≥y，使得对应的 x ′ ≤ r x&#x27;≤r x′≤r
那么 y ≤ y ′ , x ′ &lt; x y≤y&#x27;,x&#x27;&lt;x y≤y′,x′<x， [ x , y ] [x,y] [x,y]与 [ x ′ , y ′ ] [x&#x27;,y&#x27;] [x′,y′]冲突，在做其中一个区间的时候，另一个肯定已经被删掉了，所以不存在这种情况
复杂度 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)，必须每次都 l o w e r lower lower_ b o u n d bound bound一下，因为 s e t set set的地址是不连续的

Code

#include<cstdio>
#include<set>
using namespace std;
inline char gc(){
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
	int x=0,fl=1;char ch=gc();
	for(;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
	for(;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
	return x*fl;
}
char pbuf[100000],*pp=pbuf;
inline void pc(char ch){if(pp==pbuf+100000)fwrite(pbuf,1,100000,stdout),pp=pbuf;*pp++=ch;}
inline void wri(int x){
	static char st[19];
	int tp=0;
	if(x<0)pc(45),x=-x;
	if(!x)pc(48);
	while(x)st[tp++]=x%10|48,x/=10;
	while(tp)pc(st[--tp]);
}
inline void wln(int x){wri(x),pc(10);}
inline void flush(){fwrite(pbuf,1,pp-pbuf,stdout);}
struct node{
	int l,r;
	bool operator <(node a)const{return r<a.r;}
}x;
int n,l,r,ans;
char ch;
set<node>s;
set<node>::iterator it;
int main(){
	n=rd();
	for (;n--;){
		do ch=gc();while(ch!='A' && ch!='B');
		if (ch=='A'){
			l=rd(),r=rd();
			ans=0;
			while (1){
				it=s.lower_bound((node){0,l});
				if (it!=s.end() && it->l<=r) s.erase(it),ans++;
				else break;
			}
			s.insert((node){l,r});
			wln(ans);
		}else wln(s.size());
	}
	flush();
}