meizi

[l,r]有一条线段，a[l],a[l+1]......,a[r]全部加一，求max{a[i]}......

所以可以用前缀和差分，[l,r]有一条线段,b[l]++,b[r]--,ans=max{sum[i]}......

因为l,r比较大，所以要离散化......

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int n;
 6 int tmp[4000005], a[2000005], b[2000005], s[4000005];
 7 int main(){
 8     
 9     int n;
10     scanf("%d", &n);
11     for(int i = 1; i <= n; i ++){
12         scanf("%d%d", &a[i], &b[i]);
13         tmp[2 * i - 1] = a[i]; tmp[2 * i] = b[i];
14     }
15     sort(tmp + 1, tmp + 2 * n + 1);
16     for(int i = 1; i <= n; i ++){
17         a[i] = lower_bound(tmp + 1, tmp + 2 * n + 1, a[i]) - tmp;
18         b[i] = lower_bound(tmp + 1, tmp + 2 * n + 1, b[i]) - tmp;
19         s[a[i]] ++; s[b[i] + 1] --;
20     }
21     for(int i = 1; i <= 2 * n; i ++) s[i] += s[i - 1];
22     int ans = 0;
23     for(int i = 1; i <= 2 * n; i ++) ans = max(ans, s[i]);
24     printf("%d
", ans);
25     
26     return 0;
27 }

也可以用枚举，然后不断算的方法

一开始想的是按右端点排序，从前往后做，把算过的线段的右端点记录，每次排序，然后用lower_bound查找可以连接上的最靠后的右端点，最差的，复杂度是O(n^2logn)......

所以要寻找一种有单调性的方式......

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 const int maxn=2e5+7;
 7 int n,size,ans=1,head=1;
 8 int rr[maxn];
 9 struct Node{
10     int l,r;
11 }node[maxn];
12 bool cmp(Node a,Node b){
13     return a.r<b.r;
14 }
15 int main(){
16     cin>>n;
17     for(int i=1;i<=n;i++) cin>>node[i].l>>node[i].r;
18     sort(node+1,node+n+1,cmp);
19     rr[ans]=node[1].r;
20     for(int i=2;i<=n;i++){
21         int t=ans;
22         t=lower_bound(rr+1,rr+ans+1,node[i].l)-rr-1;
23         if(t==0){
24             ans++;rr[ans]=node[i].r;
25         }
26         else{
27             rr[t]=node[i].r;
28             sort(rr+1,rr+ans+1);
29         }
30     } 
31     cout<<ans<<endl;
32     return 0;
33 }

采用以左端点排序，从左向右做，因为左端点有单调性，肯定变得越来越优，所以可以将已经计算过的线段的右端点加入一个堆中，每次弹出最小的，即最优的点，不行的话就加一个杯子

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<queue>
 6 using namespace std;
 7 const int maxn=2e5+7;
 8 int n,size,ans=1,head=1;
 9 int rr[maxn];
10 priority_queue<int,vector<int>,greater<int>>q;
11 struct Node{
12     int l,r;
13 }node[maxn];
14 bool cmp(Node a,Node b){
15     return a.l<b.l;
16 }
17 int main(){
18     cin>>n;
19     for(int i=1;i<=n;i++) cin>>node[i].l>>node[i].r;
20     sort(node+1,node+n+1,cmp);
21     q.push(node[1].r);
22     for(int i=2;i<=n;i++){
23         int ri=q.top();
24         if(node[i].l<=ri){
25             ans++;q.push(node[i].r);
26         } 
27         else{
28             q.pop();q.push(node[i].r);
29         }
30     }
31     cout<<ans<<endl;
32     return 0;
33 }

lower_bound是大于等于这个值

upper_bound是大于这个值