IOI 15 Teams ( Persistent Segment Tree + Stack Monotonicity )

PEG Judge - IOI '15 - Teams
就是一個蛋疼。。改天補說明。
這個問題有兩種解法，一種是霍爾定理+DP，似乎code比較短也比較好寫，但我對二分匹配完全沒概念Orz。。
只能用持久化線段樹去很直觀的搞，雖然說這就是想定解。
首先因為每個學生的屬性是二維的，我們試試看把它們放到二維直角座標系上觀察，再點上所有隊伍人數( k, k )，因為某個學生 ( x, y ) 可分配於某個任務 ( k, k )，當且僅當 x ≤ k ≤ y，在座標系上的意義是當學生的位置在任務( k, k )的左上方區域( 0 ~ k, k ~ ∞ )。如果將 k升序排序，會發現由左到右考慮每個 k，選取學生的時候儘量選取可行的點中 y值最低的那些一定是最好的。但如果要支持刪除最小 k個點，很難做到，所以需要再想一下，因為每次都會盡量取小的取上去，將整個掃描線提升，如果沒取完就會產生階梯，並且每個階梯的右上角是呈現嚴格遞減。我們每次只關心這個階梯要提升到什麼高度，或許取一些些而已，那麼這一層就會提升一些，或許不夠用，那麼就要取完這一層的，再提升到上一個層。分析一下會發現，這個操作均攤下來整體會是線性的，因為有多少層只取決於有多少點而已。這提示我們可以利用單調性，以堆疊紀錄每個階梯的右上角。所以對於每個( k, k )和當前堆疊頂的右上角( a, b )，會需要知道有多少點在某個矩形 ( a ~ k, k ~ b )，還有要將當前的層提升到多高，也就是矩形內第 k高的點的 y值。這些操作都是持久化線段樹能做到的，就不再贅述。比較需要注意的是當有若干個點存在於同一個 y時，該怎麼維護。這裏是將可用的點連同最低線一起押入堆疊裡面。
整體來說這題非常困難，需要注意很多細節，實作有很多部分需要縝密考慮。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
const int MAXQ = 2e5 + 5;
const int MAXS = 2e5 + 5;

struct itvt{
    int cnt;
    int lb, rb;
    itvt *lc, *rc;
    itvt(int _l = -1, int _r = -1, int _c = 0): lb(_l), rb(_r), cnt(_c){
        lc = rc = NULL;
    }
    void pull(){ cnt = lc->cnt + rc->cnt; }
    int getCnt(int ql, int qr){
        if( ql <= lb && rb <= qr ) return cnt;
        int res = 0;
        int mid = lb + rb >> 1;
        if( ql <= mid ) res += lc->getCnt( ql, qr );
        if( mid <  qr ) res += rc->getCnt( ql, qr );
        return res;
    }
} *root[ MAXN ];

int getCnt(itvt *tl, itvt *tr, int ql, int qr){
    return tr->getCnt( ql, qr ) - tl->getCnt( ql, qr );
}

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

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

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

int kth(itvt *tl, itvt *tr, int k){
    if( tl->lb == tl->rb ) return tl->lb;
    int mid = tl->lb + tl->rb >> 1;
    int lcnt = tr->lc->cnt - tl->lc->cnt;
    if( k <= lcnt ) return kth( tl->lc, tr->lc, k );
    return kth( tl->rc, tr->rc, k - lcnt );
}

int n;
struct Student{
    int a, b;
    Student(int _a = -1, int _b = -1): a(_a), b(_b){}
    bool operator < (const Student &oth) const{
        if( a != oth.a ) return a < oth.a;
        return b < oth.b;
    }
} stu[ MAXN ];
int q;
int m;
int k[ MAXN ]; 

struct Corner{
    int x, y, cnt;
    Corner(int _x = -1, int _y = -1, int _c = 0): x(_x), y(_y), cnt(_c){}
};

vector<int> ys[ MAXN ];

void solve(){
    sort( k, k + m );
    stack< Corner > stk;
    stk.push( Corner( 0, n, 0 ) );
    for(int i = 0; i < m; ++i){
        while( !stk.empty() && stk.top().y < k[ i ] ) stk.pop();
        int sum = k[ i ], st = k[ i ] - 1, ed = -1; // ( ed, 
        while( !stk.empty() ){
            int tmp = getCnt( root[ stk.top().x ], root[ k[ i ] ], st + 1, stk.top().y ) + stk.top().cnt;
            if( sum > tmp ) sum -= tmp;
            else{
                ed = stk.top().y;
                break;
            }
            st = stk.top().y;
            stk.pop();
        }
        if( ed == -1 ){
            puts("0");
            return;
        }
        int s = kth( root[ stk.top().x ], root[ k[ i ] ], getCnt( root[ stk.top().x ], root[ k[ i ] ], 0, st ) + sum );
        s = min( s, ed );
        int ncnt = getCnt( root[ stk.top().x ], root[ k[ i ] ], st + 1, s ) - sum;
        stk.push( Corner( k[ i ], s, ncnt ) );
    }
    puts("1");
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d%d", &stu[ i ].a, &stu[ i ].b);
    for(int i = 0; i < n; ++i)
        ys[ stu[ i ].a ].push_back( stu[ i ].b );
    root[ 0 ] = buildItvt( 0, n );
    for(int i = 1; i <= n; ++i){
        root[ i ] = clone( root[ i - 1 ] );
        for(int j = 0; j < ys[ i ].size(); ++j)
            root[ i ] = add( root[ i ], ys[ i ][ j ] );
    }
    scanf("%d", &q);
    while( q-- ){
        scanf("%d", &m);
        int ksum = 0;
        for(int i = 0; i < m; ++i){
            scanf("%d", &k[ i ]);
            ksum += k[ i ];
        }
        if( ksum > n ){
            puts("0");
            continue;
        }
        solve();
    }
    return 0;
}