Code 備忘錄►Data Structure

TIOJ::IOI::1886 . 【IOI2015】Teams 一堆提姆

http://tioj.ck.tp.edu.tw/problems/1886

這題是IOI 2015，TOI又要考考古題了很討厭QAQ。

這題是資料結構題，除了持久化線段樹之外，還有另外一個小的詭異資料結構。

題目是這樣的，你有一堆人，每個人都可以跟一定範圍的人數的人合作，然後你有一些任務，每個任務都需要一定的人才能完成，你想要把這些人分組去完成任務，每個人只能做一個任務，問你有沒有辦法做完這些任務。

題目會變成，給你一堆區間，然後有一些任務會需要一定人數，直接把區間照左界排序，然後用貪心性質，也就是每次要找人去做某個任務的時候選則可以的人中右界最小的（這個很直觀）。因為題目有很多詢問，每個詢問複雜度就是O((n + m) log n)，n 是人數，m是該次詢問的任務數。

這樣很顯然在每筆詢問的m都很小的時候（所有詢問的m總和是定值，所以m愈小、詢問愈多），時間會爛掉。

比較有道理的作法是DP，而且是很有趣的DP，沒被捏都不知道，就是二分圖的Hall定理。

首先假設我們有一個任務需要K個人，我們可以新增一張二分圖，在集合X裡放入K個點，然後把這些點連到可以做這些任務的人（那個區間包含K），把這些人放進集合Y，只要這張二分圖的X可以完美匹配，我們就可以找到K個人完成這個任務。依照這樣，我們把每個任務都拆開放進X，並連到Y，然後只要找的到完美匹配就可以完成這些任務。
怎們樣的條件下一定可以完成呢？二分圖的Hall定理告訴我們，只要集合X的每個子集X’的大小，都小於等於X’所連到的集合Y的子集Y’的大小，那就一定存在完美匹配，反之則一定不行！！！！

也就是說，我們現在枚舉一些任務，把可以做這些任務的人都挑出來，只要人數大於任務需要的人數，就可以完成任務，只要任務序列的每個子序列都符合條件，都可以被完成，那就一定可以完成全部的任務。

於是我們就可以想到一個m（任務數量）平方的DP，去DP某個任務子序列，來確定任務是不是不可以被完成。因為Hall定理說只要一個子集不符合規定就不可能匹配，所以我們試著用DP去找最差的結果，如果最差的不符合規定就知道無法完成。
設DP[i]是以任務i為結尾的任務子序列，可以做這些任務的人數減掉這些任務需要的人數的最小值。
轉移就是j從0到i-1，取min(DP[j] + Z(j,i) - K_i)，其中K_i是做第i個任務需要的人，Z(j,i)是可以做i任務但是卻不能做j任務的人數，也就是左界在[K_j+1,K_i]之間，右界大於K_i的人，這個可以用持久化線段樹去查詢，這樣O（m^2 log n）就可以完成這個DP了，只要任何一個DP值小於0，代表無法完成任務。

持久化線段樹的作法就是開一個值域線段樹，然後你直接根據左界分成N個版本，每個版本 i 代表左界小於等於 K_i 的那些人，之後右界就當作單點插入，有點像找區間第K小時實作的持久化線段樹，可以參考一下。

以上作法還是不夠快，這時可以用一種作法，就是當 m < sqrt(n)使用第2種作法，反之使用第1種貪心法，這樣有機會（基本上可以AC了）通過。

另外一種比較穩定的解法，我們要先觀察剛剛的 m 平方DP，我們想一下當 i<jk，轉移到DP[l]時，i還是比j好。為什麼，我們看看下面的式子：
如果i比j好，代表 DP[i] + Z(i,k) <= DP[j] + Z(j,k)。
移項得到 DP[j] - DP[i] >= Z(j,k) - Z(i,k) = 左界在[K_i+1,K_j]中，右界大於K_k的人，這點我覺得式子寫出來就很直觀了，就不多做說明了。
因為後面那個東西，在k愈大的狀況，只會變小不會變大（左界固定，右界愈右邊符合的人當然愈少），所以這東西是有單調性的，也就是只要符合DP[i] + Z(i,k) <= DP[j] + Z(j,k)，對於所有d大於k，DP[i] + Z(i,d) <= DP[j] + Z(j,d) 也都會符合，這就是DP優化中的四邊形單調性。

於是我們DP時要維護一個資料結構Magic（我自己取的XD，簡稱MG），對於i<j，DP[j]一定DP[i]好，所以MG的最後一個就是我們要的最小值，在push任何一個值進去時，我們可以計算一個時間，代表最後一個值什麼時候會殺掉這個新的值，然後把他丟進heap裡，然後每次查詢前都先更新MG，也就是看看現在的時間（這題的狀況就是任務的人數，我們要按照小到大去做，而我們可以知道當人數超過某個值的時候，某些點可以把後面的點殺掉），把heap頂端（時間最小）的值拿出來，看看是不是已經死了，不是就把他殺掉。

實作MG可以用STL list，然後多開一個vector去存每一個位置的iterator，list是用來加速找前後的節點，vector是用來random accesses。

另外，計算死亡時間時，我們需要知道對於 i<j，哪個時間（座標）DP[j] - DP[i] 會大於等於 左界在[K_i+1,K_j]中，右界大於K_k的人，其中最小的k就是我們要的死亡時間，可以透過在兩顆線段樹上走來計算，或是直接二分搜k，用單顆線段樹去驗證答案，後者會多一個log但是還是可以接受。這樣就有一個O（m logn）的作法了。

我因為邊界問題WA了好久QAQ，一定要注意邊界、upper bound 還是 lowwer bound。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <bits/stdc++.h>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
using namespace std;
const int N = 500003, M = 200003, MX = N*40;
typedef pair<int,int> PII;
PII D[N];
int ST[N],st, DP[N], S[M];
struct Seg{
    static Seg ST[MX], *p;
    Seg *lc,*rc;
    int sz;
    Seg(){ }
    Seg(int l,int r):sz(0){
        if(l==r)return;
        int mid = (l+r)/2;
        lc = new(p++) Seg(l,mid);
        rc = new(p++) Seg(mid+1,r);
    }
    Seg* ins(int l,int r,int *X, int s){
        Seg *nw = new(p++) Seg(*this);
        nw->sz += s;
        if(l<r){
            int mid = (l+r)/2;
            int ts = (upper_bound(X,X+s,mid) - X);
            if(ts)nw->lc = lc->ins(l,mid,X,ts);
            if(ts<s)nw->rc = rc->ins(mid+1,r,X+ts,s-ts);
        }
        return nw;
    }
    int query(int l,int r,int x){
        if(x<=l)return sz;
        if(x>r)return 0;
        int mid = (l+r)/2;
        return lc->query(l,mid,x) + rc->query(mid+1,r,x);
    }
}*RT[N], Seg::ST[MX], *Seg::p = Seg::ST;
int query(Seg *lc, Seg *rc, int x,int n){
    return rc->query(1,n,x) - lc->query(1,n,x);
}
int s_query(Seg *lc, Seg *rc, int y, int n){
    // 這個函數有兩種實作方法。
    // 1.走訪線段樹的方法
    int l = 1, r = n;
    if(rc->sz - lc->sz < y)return 0;
    while(l<r){
        int mid = (l+r)/2;
        if(rc->rc->sz - lc->rc->sz <= y){
            y -= rc->rc->sz - lc->rc->sz;
            r = mid;
            lc = lc->lc;
            rc = rc->lc;
        }else{
            l = mid+1;
            lc = lc->rc;
            rc = rc->rc;
        }
    }
    return l+1;
    
    // 2.下面是2分搜的方法
    // int ans = l+1;
    // l = 0, r = n;
    // while(l<r-1){
    //     int mid = (l+r)/2;
    //     if(query(t1,t2,mid,n) > tmpy)l = mid;
    //     else r = mid;
    // }
    // return r;
}
struct Magic{
    vector<list<int>::iterator> P;
    list<int> IND;
    priority_queue<PII, vector<PII>,greater<PII>> dead;
    Magic(){
        IND.push_back(0);
        P.push_back(IND.begin());
    }
    void update(int x, int n){
        while(!dead.empty() && dead.top().first<=x){
            int tmp = dead.top().second;
            dead.pop();
            if(P[tmp] != IND.end()){
                if(next(P[tmp]) != IND.end()){
                    int pre = *prev(P[tmp]), nx = *next(P[tmp]);
                    dead.push(PII(s_query(RT[S[pre]], RT[S[nx]], DP[nx] - DP[pre], n), nx));
                }
                IND.erase(P[tmp]);
                P[tmp] = IND.end();
            }
        }
    }
    void push(int n){
        int now = P.size(), pre = IND.back();
        int ti = s_query(RT[S[pre]], RT[S[now]], DP[now] - DP[pre], n);
        IND.push_back(now);
        P.push_back(prev(IND.end()));
        dead.push(PII(ti, now));
    }
    int back(){
        return IND.back();
    }
};
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t,n,q,m;
    cin>>t;
    while(t--){
        Seg::p = Seg::ST;
        cin>>n;
        RT[0] = new(Seg::p++) Seg(1,n);
        F(n)cin>>D[i].first>>D[i].second;
        sort(D,D+n);
        int l = 0;
        st = 0;
        F(n){
            RT[i+1] = RT[i];
            while(l<n&&D[l].first<=i+1)ST[st++] = D[l].second,l++;
            if(st){
                RT[i+1] = RT[i+1]->ins(1,n,ST,st);
                st = 0;
            }
        }
        cin>>q;
        while(q--){
            cin>>m;
            F(m)cin>>S[i+1];
            sort(S+1,S+m+1);
            DP[0] = 0;
            Magic mg;
            bool ans = true;
            F(m){
                mg.update(S[i+1], n);
                DP[i+1] = DP[mg.back()] + query(RT[S[mg.back()]],RT[S[i+1]],S[i+1], n) - S[i+1];
                if(DP[i+1]<0){
                    ans = false;
                    break;
                }
                mg.push(n);
            }
            cout<<(ans?1:0)<<endl;
        }
    }
}