线段树+区间离散化

校赛1007

题意 给你一个n(n<1e5)，表示n个比赛直播，然后n个区间，l,r(0<=l,r<=1e9)，表示比赛开始的时间和结束的时间，要同时把所有比赛看完，问最少要借多少台电脑（自己有一台电脑） 其实就是求区间重叠的最大值由于区间太大，所以离散化处理

思路：线段树区间更新 + 离散化

以区间的端点作为标记离散化，离散化后映射到线段树，将重复的端点去掉，然后重新排序，对每个区间二分确定映射后的区间，这里注意二分的时候左端点和右端点二分的判断条件是不同的

AC代码：

#include "iostream"
#include "string.h"
#include "stack"
#include "queue"
#include "string"
#include "vector"
#include "set"
#include "map"
#include "algorithm"
#include "stdio.h"
#include "math.h"
#define ll long long
#define ull unsigned ll
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define len (Tr[rt].r-Tr[rt].l+1)
#define mem(a) memset(a,0,sizeof(a))
using namespace std;

struct Qu{
    ll l,r;
};
Qu Q[500000];
struct Node{
    int l,r;
    int maxn,lazy;
};
Node Tr[200000<<2];
int cnt;

void Push_up(int rt){
    Tr[rt].maxn=max(Tr[rt<<1].maxn,Tr[rt<<1|1].maxn);
}
void Push_down(int rt){
    Tr[rt<<1].lazy+=Tr[rt].lazy;
    Tr[rt<<1|1].lazy+=Tr[rt].lazy;
    Tr[rt<<1].maxn+=Tr[rt].lazy;
    Tr[rt<<1|1].maxn+=Tr[rt].lazy;
    Tr[rt].lazy=0;
}
void Build(int l,int r,int rt){
    Tr[rt].l=l,Tr[rt].r=r;
    if(l==r) return;
    int mid=l+r>>1;
    Build(lson);
    Build(rson);
}
void Add(int l,int r,int rt){
    if(Tr[rt].l==l && Tr[rt].r==r){
        Tr[rt].lazy++;
        Tr[rt].maxn++;
        return;
    }
    if(Tr[rt].lazy) Push_down(rt);
    int mid=Tr[rt].l+Tr[rt].r>>1;
    if(r<=mid) Add(l,r,rt<<1);
    else if(l>mid) Add(l,r,rt<<1|1);
    else Add(lson),Add(rson);
    Push_up(rt);
}
int fun(ll *a,ll s,int f){
    int l=1,r=cnt,ans=0;
    while(l<=r){
        int mid=l+r>>1;
        if(a[mid]<=s) ans=mid,l=mid+1;
        else r=mid-1;
    }
    if(!f) return ans+1; //左端点返回ans+1
    else return ans;     //右端点返回ans
}
ll a[250000];
int main(){
    int n,q,l,r;
    while(scanf("%d",&q)!=EOF){
        mem(Tr);
        ll K=1000000005;
        cnt=0;
        for(int i=0; i<q; i++){
            scanf("%lld%lld",&Q[i].l,&Q[i].r);
            a[cnt++]=Q[i].l,a[cnt++]=Q[i].r;
        }
        sort(a,a+cnt);
        int k=cnt;
        for(int i=1; i<k; i++) if(a[i-1]==a[i]) a[i-1]=K++,cnt--;
        sort(a,a+k);
        Build(1,cnt,1);
        for(int i=0; i<q; i++){
            l=fun(a,Q[i].l,0);
            r=fun(a,Q[i].r,1); //cout<<l<<" "<<r<<endl;
            Add(l,r,1);
        }
        printf("%d
",Tr[1].maxn-1);
    }
    return 0;
}