【离散化】【扫描线】CH Round #59

//上图绿色扫描线右侧少画了一条扫描线。

很多区间把数轴分成了很多段，看哪个点的(区间覆盖数*该点权值)最大。

显然在某个区间的右端点的答案是最优的。

排序后用扫描线从左到右扫描，维护每个点的覆盖数，就是遇到左端点时cnt++，右端点时更新ans、cnt--。

若某个点既有左端点，又有右端点，就把左端点放在前面。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6 #define N 100001
 7 ll ans;
 8 int t1,t2,m,cnt,n;
 9 struct Node{int v;bool dir;Node(const int &a,const bool &b){v=a;dir=b;}Node(){}}a[N<<1];
10 bool operator < (const Node &a,const Node &b){return a.v!=b.v?a.v<b.v:a.dir<b.dir;}
11 int main()
12 {
13     scanf("%d",&n);
14     for(int i=1;i<=n;i++)
15       {
16           scanf("%d%d",&t1,&t2);
17           a[++m]=Node(t1,0); a[++m]=Node(t2,1);
18       }
19     sort(a+1,a+m+1);
20     for(int i=1;i<=m;i++)
21       {
22           if(!a[i].dir) cnt++;
23           else
24             {
25                 ans=max(ans,(ll)cnt*(ll)a[i].v);
26                 cnt--;
27             }
28       }
29     cout<<ans<<endl;
30     return 0;
31 }