D

讀錯題了。

考慮相鄰兩個集合僅有一個數不同，不妨設這個數為 \(x_i\)，那么對于一個給定的 \(x\) 序列，如果 \(S_1\) 給定，那么這個序列就給定了。

設 \(A_i,B_i\) 分別為 \(S_i\) 是否含有 \(i\)，序列 \(i\) 中包含 \(i\) 的集合個數。顯然我們有 \(A_i+B_i=n\)，所以對對于固定的 \(x\)，答案為 \(n^m\)，而 \(x\) 序列的選取有 \(m^{n-1}\) 種，所以答案應該為 \(n^m\times m^{n-1}\)

E

思維題。

考慮如何判 -1，只需要把 \(A,B\) 排個序，然后看 \(A,B\) 的每一位是否都滿足 \(A_i\ge B_i\)，如果不滿足，那么就是 -1。

我們要對上面的判定條件進行轉化，設 \(cnt_t\) 表示滿足 \(B_i\le t\) 的 \(i\) 的個數減去 \(A_i\le t\) 的 \(i\) 的個數。那么只需要保證對于所有的 \(t\)，\(cnt_t\ge 0\) 即可。

現在考慮答案是多少。如果 \(A_i<B_i\) 的 \(i\) 的個數為 \(n\)，那么答案就是 \(n\)。否則，我們要從里面選出一個集合，滿足集合的大小最小，而且集合中要包含所有不合法的 \(i\)，那么我們的答案就認為是這個集合的大小。

只需要讓這個集合內的數滿足 \(cnt_t\ge 0\) 即可。每次我們找到這個集合內最小的不滿足條件的 \(t\)，然后找到一個 \(A_i,B_i\) 滿足 \(B_i<t\)，如果有多個，顯然選一個 \(A_i\) 最大的是最優的。

模擬貪心即可，思維難度主要在轉化判定條件上。

int n,a[N],b[N],ans,sum;
map<int,int> Map;
priority_queue<int> q;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q1;

int main(){
    read(n);rep(i,1,n) read(a[i]),read(b[i]);
    ans=n;
    rep(i,1,n){
        if(a[i]<b[i]){
            ans--;Map[a[i]]--;Map[b[i]]++;  
        }
        q1.push(mp(b[i],a[i]));
    }
    for(P x:Map){
        sum+=x.second;
        while(q1.size()&&q1.top().fi<=x.fi){
            q.push(q1.top().se);q1.pop();
        }
        while(sum<0){
            if(q.empty()||q.top()<=x.fi){
                puts("-1");return 0;
            }
            int now=q.top();q.pop();
            sum++;Map[now]--;ans--;
        }
    }
    printf("%d\n",ans);
    return 0;
}