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;
}