离散化 去掉重复点 排序 二分查找
#include#include #include #define maxn 40005using namespace std;int pp[maxn][2];int x[2*maxn],f[2*maxn];int d[2*maxn];int main(){ int t; scanf("%d",&t); while (t--) { memset(f, 0 ,sizeof(0)); int n; scanf("%d",&n); for(int i= 0; i < n; i++) { scanf("%d%d",&pp[i][0],&pp[i][1]); x[i] = pp[i][0]; x[2*i+1] = pp[i][1]; } sort(x, x+2*n); d[0] = x[0]; int cc = 1; for(int i = 1; i < 2*n; i++) { if(x[i] != d[cc-1]) { d[cc++] = x[i]; } } for(int i = 0; i < n; i++) { int ri = lower_bound(d, d+cc, pp[i][0])-d; int le = lower_bound(d, d+cc, pp[i][1])-d; for(int j = ri; j <= le; j++) f[j] = i; } sort(f, f+cc); int ans = 1; for(int i = 1; i < cc; i++) { if(f[i] != f[i-1]) ans++; } printf("%d\n",ans); } return 0;}