JOI 10 本選 Bug Party ( Binary Search + MLE Persistent Segment Tree / AC Priority Queue )

Bug Party | Aizu Online Judge
很容易想到，如果固定最小值b，那麼我們必須由小到大拿進所有a，直到 sum( a ) ≤ b * cnt 不再成立。由於要快速( O( lg n ) 以下 ) 求出大於等於某個b值的最小的x個a值的總和，條件形式複雜，如果不加功夫用持久化線段樹亂搞，雖然時間複雜度是對的，但會MLE。

// RE and MLE
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 5;
const int MAXA = 1e5 + 5;
const int MAXB = 1e5 + 5;
const int MAXMEM = 1.5e5; // 実は少なくとも 3e6は欲しい
typedef long long ll;

struct itvt{
    static itvt mem[ MAXMEM ];
    int lb, rb;
    int cnt; ll sum;
    itvt *lc, *rc;
    itvt(): cnt(0), sum(0LL), lc(NULL), rc(NULL){}
    void pull(){
        cnt = lc->cnt + rc->cnt;
        sum = lc->sum + rc->sum;
    }
} itvt::mem[ MAXMEM ], *ptr = itvt::mem, *root[ MAXN ];

itvt* build(int lb, int rb){
    itvt *t = new( ptr++ ) itvt();
    t->lb = lb, t->rb = rb;
    if( lb == rb ) return t;
    int mid = ( lb + rb ) / 2;
    t->lc = build( lb, mid );
    t->rc = build( mid + 1, rb );
    return t;
}

itvt* clone(itvt *t){
    itvt *res = new( ptr++ )itvt();
    res->lb = t->lb, res->rb = t->rb;
    res->cnt = t->cnt, res->sum = t->sum;
    res->lc = t->lc, res->rc = t->rc;
    return res;
}

itvt *add(itvt *t, int x, int v){
    itvt *res = clone( t );
    if( t->lb == t->rb ){
        ++res->cnt;
        res->sum += v;
        return res;
    }
    int mid = ( t->lb + t->rb ) / 2;
    if( x <= mid ) res->lc = add( t->lc, x, v );
    else res->rc = add( t->rc, x, v );
    res->pull();
    return res;
}

typedef pair<ll, int> pli; // sum / count
pli qsum(itvt *t, int ql, int qr){
    if( ql <= t->lb && t->rb <= qr ) return pli( t->sum, t->cnt );
    int mid = ( t->lb + t->rb ) / 2;
    pli res = pli( 0LL, 0 );
    if( ql <= mid ){
        pli g = qsum( t->lc, ql, qr );
        res.first += g.first, res.second += g.second;
    }
    if( mid <  qr ){
        pli g = qsum( t->rc, ql, qr );
        res.first += g.first, res.second += g.second;
    }
    return res;
}

int n;

struct Ant{
    int a, b;
    Ant(int _a = 0, int _b = 0): a( _a ), b( _b ){}
} ant[ MAXN ], a_sorted_ant[ MAXN ];
bool cmpa(const Ant &x, const Ant &y){ return x.a < y.a; }
bool cmpb(const Ant &x, const Ant &y){ return x.b < y.b; }

void solve(){
    int ans = 0;
    for(int i = 0; i < n; ++i) a_sorted_ant[ i ] = ant[ i ];
    sort( a_sorted_ant, a_sorted_ant + n, cmpa );
    root[ 0 ] = build( 1, 100000 ); // 1 <= b <= 100000
    for(int i = 1; i <= n; ++i)
        root[ i ] = add( root[ i - 1 ], a_sorted_ant[ i - 1 ].b, a_sorted_ant[ i - 1 ].a ); 
    sort( ant, ant + n, cmpb );
    for(int i = 0; i < n; ++i){
        int b = ant[ i ].b;
        int lb = 0, rb = n; // finally will take how much
        int t = -1;
        while( lb <= rb ){
            int mid = ( lb + rb ) / 2;
            pli g = qsum( root[ mid ], b, 100000 );
            ll asum = g.first;
            int cnt = g.second;
            if( asum <= (ll)cnt * b )
                t = cnt, lb = mid + 1;
            else
                rb = mid - 1;
        }
        ans = max<int>( ans, t );
    }
    printf("%d\n", ans);
}

int main(){
    // printf("%d\n", (int)(sizeof(itvt))); = 40
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d%d", &ant[ i ].a, &ant[ i ].b);
    solve();
    return 0;
}

該注意到的是，如果從許可量大的開始取，那麼我們只需要在意現在準備取的那個元素的b，具體來說，假設要判斷取x個元素是否可行，我們可以先取排放量最大的x - 1個元素，接著在看這第x個的b來判斷是否取進之後是可行的，若不可行，就維護這x - 1個元素使得一路排放量最小。到這裡思路就很明顯了，二分搜這個x，利用priority queue來維護和判斷是否可行。O( n lg ^ 2 n )。
結論：雙重有序的題目如果無法有效的處理，除了要想想看雙向佇列和爬行，有時候是可以透過改變遍歷元素的方法，使得某一維度隱約地出現在遍歷的順序中，或許能因為排序過省略某些檢查，進而達到降低複雜度的效果。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 5;
const int MAXA = 1e5 + 5;
const int MAXB = 1e5 + 5;
typedef long long ll;

int n;

struct Ant{
    int a, b;
    Ant(int _a = 0, int _b = 0): a(_a), b(_b){}
} ant[ MAXN ];
bool cmpa(const Ant &x, const Ant &y){
    return x.b > y.b; // b: limit of take in
}

bool ok(int x){
    ll asum = 0LL;
    priority_queue<int> foo;
    for(int i = 0; i < x - 1; ++i)
        asum += ant[ i ].a,
        foo.push( ant[ i ].a );
    for(int i = x - 1; i < n; ++i){
        if( ( asum + ant[ i ].a ) <= (ll)x * ant[ i ].b )
            return true;
        if( foo.empty() ) continue; // OOPS, when x == 1
        if( ant[ i ].a > foo.top() ) continue;
        asum -= foo.top() - ant[ i ].a;
        foo.pop();
        foo.push( ant[ i ].a );
    }
    return false;
}

void solve(){
    sort( ant, ant + n, cmpa );
    int lb = 0, ub = n;
    int ans = -1;
    while( lb <= ub ){
        int mid = ( lb + ub ) / 2;
        if( ok( mid ) ) ans = mid, lb = mid + 1;
        else ub = mid - 1;
    }
    printf("%d\n", ans);
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d%d", &ant[ i ].a, &ant[ i ].b);
    solve();
    return 0;
}