本文共 1822 字，大约阅读时间需要 6 分钟。
这题和上题一样，但要注意，这题专业反人类反STL，用map离散化TLE。。
#include #include #include #include #include #include #include #include #include #include #define LL __int64using namespace std;const int N=40050;const int root=1;int tree[N*4];struct Paper{ int begin,end;}paper[N/3];int sort_num[N],cnt;bool hash[N/3];void PushDown(int now){ if(tree[now]>0){ tree[now*2]=tree[now*2+1]=tree[now]; tree[now]=0; }}void update(int now,int l,int r,int u,int L,int R){ if(l<=L&&r>=R){ tree[now]=u; return ; } PushDown(now); int m=(L+R)/2; if(r<=m){ update(now*2,l,r,u,L,m); } else if(l>=m+1)update(now*2+1,l,r,u,m+1,R); else{ update(now*2,l,r,u,L,m); update(now*2+1,l,r,u,m+1,R); }}void query(int now,int l,int r){ if(tree[now]>0){ if(!hash[tree[now]]) cnt++; hash[tree[now]]=true; return ; } if(l==r) return ; int m=(l+r)/2; query(now*2,l,m); query(now*2+1,m+1,r);}int Bin(int key,int n,int X[]) { int l = 0 , r = n - 1; while (l <= r) { int m = (l + r) >> 1; if (X[m] == key) return m; if (X[m] < key) l = m + 1; else r = m - 1; } return -1; } int main(){ int T,n,tot,l,r; scanf("%d",&T); while(T--){ scanf("%d",&n); tot=0; for(int i=1;i<=n;i++){ scanf("%d%d",&paper[i].begin,&paper[i].end); sort_num[tot++]=paper[i].begin; sort_num[tot++]=paper[i].end; } sort(sort_num,sort_num+tot); int cnum=1,m=0; for(int i=0;i 0 ; i --) { if (sort_num[i] != sort_num[i-1] + 1) sort_num[m ++] = sort_num[i-1] + 1; } sort(sort_num,sort_num+m); memset(tree,0,sizeof(tree)); for(int i=1;i<=n;i++){ l=Bin(paper[i].begin , m , sort_num),r=Bin(paper[i].end , m , sort_num); l++,r++; update(root,l,r,i,1,m); } memset(hash,false,sizeof(hash)); cnt=0; query(root,1,m); printf("%d\n",cnt); } return 0;}
转载于:https://www.cnblogs.com/jie-dcai/p/4316480.html