Codeforces Round #613 (Div. 2) E. Delete a Segment

問題ページ
区間 が与えられたとき，数列 の区間 に+1した数列を考える．そのまま数列をつくるとMLEなので，座標圧縮しておく．区間が交差しているかどうかを考えたいとき， と隣接していると結構大変なので，各端点を2倍して としておくと交差しない区間の間には必ず隙間が存在するようになって，場合分けが楽になる．

区間を削除しない場合の答えは数列 において 0,1以上 と並んでいる場所の個数となる．区間を削除することは，数列 の区間 を-1することと等価である．この操作によって 0,1 以上と並んでいる場所の個数がどのように増減するか？

• 番目が 1,2以上 と並んでいる場合：1増加
• 左端(番目)が 0,1 と並んでいる場合：1減少
• 右端(番目)が 1,1以上 と並んでいる場合：1増加

1,2以上 と並んでいる場所を記録して累積和を取っておくことで，各区間を削除したときの答えの増減を で求めることができる．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
void solve() {  
    ll n;  
    cin >> n;  
    vector<ll> vs;  
    vector<PII> v(n);  
    REP(i, n) {  
        cin >> v[i].first >> v[i].second;  
        vs.push_back(v[i].first);  
        vs.push_back(v[i].second);  
    }  
    vs.push_back(-INF); vs.push_back(INF);  
    sort(ALL(vs));  
    vs.erase(unique(ALL(vs)), vs.end());  
    const ll m = vs.size()*3;  
  
    REP(i, n) {  
        ll l = lower_bound(ALL(vs), v[i].first) - vs.begin();  
        ll r = lower_bound(ALL(vs), v[i].second) - vs.begin();  
        v[i] = PII(l*2, r*2);  
    }  
    vector<ll> ts(m);  
    REP(i, n) ts[v[i].first]++, ts[v[i].second+1]--;  
    FOR(i, 1, m) ts[i] += ts[i-1];  
  
    ll num = 0;  
    REP(i, m-1) if(ts[i] == 0 && ts[i+1] >= 1) num++;  
    vector<ll> pos(m);  
    REP(i, m-1) if(ts[i] == 1 && ts[i+1] >= 2) pos[i] = 1;  
    FOR(i, 1, m) pos[i] += pos[i-1];  
  
    ll ret = 0;  
    REP(i, n) {  
        ll l, r;  
        tie(l, r) = v[i];  
  
        // [l,r) の 1,2以上 の個数  
        ll cnt = pos[r-1] - pos[l-1];  
        // 左端が 0,1 なら1減る  
        if(ts[l-1]==0 && ts[l]==1) cnt--;  
        // 右端が 1,1以上 なら1増える  
        if(ts[r]==1 && ts[r+1]>=1) cnt++;  
          
        chmax(ret, num + cnt);  
    }  
    cout << ret << endl;  
}  
  
int main(void) {  
    ll t;  
    cin >> t;  
    while(t--) solve();  
  
    return 0;  
}