题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2501
一开始觉得这题不是线段树随便搞，后来看了眼数据范围就放弃了
先离散化，记录一下是左端点还是右端点
然后按照下标从小到大排序，如果下标相同左端点在前 （因为边界也算覆盖）
然后对排序完的点集从小到大扫，now记录目前被几个线段覆盖，碰到左端点就+1，碰到右端点就-1，ans取最大的now就行
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<bits/stdc++.h> #define MAXN 50050 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct node{ int p; bool f; friend bool operator < (node a,node b){ if(a.p==b.p)return a.f<b.f; return a.p<b.p; } }a[MAXN*2]; int n; int main(){ n=rd(); for(int i=0; i<n; i++){ a[i*2].p=rd(),a[i*2].f=0; a[i*2+1].p=rd(),a[i*2+1].f=1; } sort(a,a+2*n); int ans=0,now=0; for(int i=0; i<2*n; i++){ if(a[i].f)now--; else now++; ans=max(ans,now); } printf("%d\n",ans); return 0; } |
