# tioj 1941 直升機抓寶

https://tioj.ck.tp.edu.tw/problems/1941

* n^2的作法是對[s,t]加1後，再做$dp[i]=max(dp[i], dp[i-1])$，也就是在做前綴最大值，所以也會發現最後出來的dp表一定是非嚴格遞增
* 建一個bit（在此做區間修改和單點查詢），先對寶貝的區間[s,t]都加1（對bit做差分），然後因為是原dp陣列是遞增，所以從t之後開始二分搜最後一個比dp[t]還小的位置，對[t+1, 二分搜結果]區間都加1，來維持非嚴格遞增。
* 答案就是query(n-1)（單純對bit差分就是在單點查詢）
* $O(n\log n\log n)$ （每次二分搜都要query一次bit）

#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define rep(X, a,b) for(int X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
using namespace std;
typedef pair<long long,long long> pll;
typedef pair<int,int> pii;
typedef long long ll;

ll bit[800010]={0}, n;

void upd(ll pos, ll x){
    pos++;
    while(pos<=n){
        bit[pos]+=x;
        pos+=pos&(-pos);
    }
}

ll get(ll pos){
    pos++;
    ll res=0;
    while(pos>0){
        res+=bit[pos];
        pos-=pos&(-pos);
    }
    return res;
    }

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    vector<pll> rg(n);
    rep(i,0,n) cin>>rg[i].F>>rg[i].S;
    rep(i,0,n){
        upd(rg[i].F, 1);
        upd(rg[i].S+1, -1);
        ll cur=get(rg[i].S);
        ll l=rg[i].S, r=n;
        while(l<r-1){
            int mid=(l+r)>>1;
            if(get(mid)>=cur) r=mid;
            else l=mid;
        }
        upd(rg[i].S+1, 1);
        upd(l+1, -1);
        //cout<<rg[i]<<l<<" "<<get(n-1)<<NL;
    }
    cout<<get(n-1)<<NL;
}