2018-2019 ACM-ICPC, Asia Seoul Regional Contest A - Circuits

問題ページ
長方形のx座標は何も関係がなくて結局区間の問題になる．区間の端点以外に線を引くことで得をすることはない．よって「 個の区間が与えられる．区間の端点のから2点を選ぶ．この2点の少なくとも一方を含む区間の個数を最大化しろ．」という問題に帰着できる．

1点を決め打ったときに残りの1点をどこにするのが最適か考える．決めた1点を含まない区間のみについて考えたとき，最も多くの区間が被覆している点を求められればよい．各点について何個の区間に被覆されるか？を遅延セグ木で保持しておくことで高速に求められる．

決め打つ1点の位置を0から順番に1ずつ増やしていく．区間の左端に来た場合，その区間から-1する．(決め打っている1点に被覆していく区間の数) + (seg木のmax) が答えの候補になるのでchmaxする．区間の右端に来た場合，その区間に+1する．

#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;  
  
  
template <typename Monoid>  
struct lazysegtree {  
    using T = typename Monoid::T;  
    using E = typename Monoid::E;  
    int n, height;  
    vector<T> dat;  
    vector<E> lazy;  
  
    lazysegtree() {}  
    lazysegtree(int n_) {  
        n = 1, height = 0;  
        while(n < n_) { n *= 2; height++; }  
        dat.assign(n*2, Monoid::dt());  
        lazy.assign(n*2, Monoid::de());  
    }  
    void build(vector<T> v) {  
        REP(i, v.size()) dat[i+n] = v[i];  
        for(int i=n-1; i>0; --i) dat[i] = Monoid::f(dat[i*2], dat[i*2+1]);  
    }  
  
    inline T reflect(int k) { return lazy[k]==Monoid::de()?dat[k]:Monoid::g(dat[k], lazy[k]); }  
    inline void eval(int k) {  
        if(lazy[k] == Monoid::de()) return;  
        lazy[2*k]   = Monoid::h(lazy[k*2],   lazy[k]);  
        lazy[2*k+1] = Monoid::h(lazy[k*2+1], lazy[k]);  
        dat[k] = reflect(k);  
        lazy[k] = Monoid::de();  
    }  
    inline void thrust(int k) { for(int i=height;i;--i) eval(k>>i); }  
    inline void recalc(int k) { while(k>>=1) dat[k] = Monoid::f(reflect(k*2), reflect(k*2+1)); }  
  
    void update(int a, int b, E x) {  
        thrust(a+=n);  
        thrust(b+=n-1);  
        for(int l=a, r=b+1; l<r; l>>=1,r>>=1) {  
            if(l&1) lazy[l] = Monoid::h(lazy[l], x), ++l;  
            if(r&1) --r, lazy[r] = Monoid::h(lazy[r], x);  
        }  
        recalc(a);  
        recalc(b);  
    }  
    T query(int a, int b) {  
        thrust(a+=n);  
        thrust(b+=n-1);  
        T vl=Monoid::dt(), vr=Monoid::dt();  
        for(int l=a, r=b+1; l<r; l>>=1,r>>=1) {  
            if(l&1) vl=Monoid::f(vl, reflect(l++));  
            if(r&1) vr=Monoid::f(reflect(--r), vr);  
        }  
        return Monoid::f(vl, vr);  
    }  
  
    friend ostream &operator <<(ostream& out,const lazysegtree<Monoid>& seg) {  
        out << "---------------------" << endl;  
        int cnt = 1;  
        for(int i=1; i<=seg.n; i*=2) {  
            REP(j, i) {  
                out << "(" << seg.dat[cnt] << "," << seg.lazy[cnt] << ") ";  
                cnt++;  
            }  
            out << endl;  
        }  
        out << "---------------------" << endl;  
        return out;  
    }  
};  
  
struct node {  
    ll sum, max, min, len;  
    node() : sum(0), max(-INF), min(INF), len(0) {}  
    node(ll a, ll b, ll c, ll d) : sum(a), max(b), min(c), len(d) {}  
};  
struct linear_exp {  
    using T = node;  
    using E = PII;  
    static T dt() { return node(); }  
    static constexpr E de() { return PII(1, 0); }  
    static T f(const T &a, const T &b) {  
        node ret;  
        ret.sum = a.sum + b.sum;  
        ret.min = min(a.min, b.min);  
        ret.max = max(a.max, b.max);  
        ret.len = a.len + b.len;  
        return ret;  
    }  
    static T g(const T &a, const E &b) {  
        node ret;  
        ret.sum = b.first*a.sum+b.second*a.len;  
        ret.min = b.first*a.min+b.second;  
        ret.max = b.first*a.max+b.second;  
        ret.len = a.len;  
        return ret;  
    }  
    static E h(const E &a, const E &b) {  
        return PII(b.first*a.first, b.first*a.second+b.second);  
    }  
};  
  
int main() {  
    ios::sync_with_stdio(false);  
    cin.tie(0);  
   
    ll n;  
    cin >> n;  
    vector<ll> sx(n), sy(n), gx(n), gy(n), vs;  
    REP(i, n) {  
        cin >> sx[i] >> gy[i] >> gx[i] >> sy[i];  
        vs.push_back(sy[i]);  
        vs.push_back(gy[i]);  
    }  
    sort(vs.begin(), vs.end());  
    vs.erase(unique(vs.begin(), vs.end()), vs.end());  
   
    REP(i, n) {  
        sy[i] = lower_bound(vs.begin(), vs.end(), sy[i]) - vs.begin();  
        gy[i] = lower_bound(vs.begin(), vs.end(), gy[i]) - vs.begin();  
    }  
   
    lazysegtree<linear_exp> seg(vs.size());  
    vector<node> init(vs.size());  
    REP(i, vs.size()) init[i].len = 1, init[i].max = 0;  
    REP(i, n) {  
        init[sy[i]].max++;  
        if (gy[i]+1 < vs.size()) init[gy[i]+1].max--;  
    }  
    FOR(i, 1, vs.size()) init[i].max += init[i-1].max;  
    seg.build(init);  
   
    vector<vector<ll>> add(vs.size()), del(vs.size());  
    REP(i, n) {  
        add[sy[i]].push_back(i);  
        del[gy[i]].push_back(i);  
    }  
   
    ll cnt = 0, ans = 0;  
    REP(i, vs.size()) {  
        for (auto j : add[i]) {  
            seg.update(sy[j], gy[j] + 1, PII(1, -1));  
            cnt++;  
        }  
   
        if(i+1 < vs.size()) chmax(ans, cnt + seg.query(i+1, vs.size()).max);  
   
        for (auto j : del[i]) {  
            seg.update(sy[j], gy[j] + 1, PII(1, 1));  
            cnt--;  
        }  
    }  
   
    cout << ans << endl;  
}