題意
有\(n(n\le 10^5)\)支球隊，每兩個球隊有\(k(k\le 5)\)個屬性。
當一個球隊的某一項屬性大于另一個球隊，則這個球隊有可能會戰勝另外的球隊。
每次會在剩餘未被淘汰的球隊裡随機選出兩個球隊進行比賽。
問有可能獲得冠軍的球隊有多少個？
分析
當兩個球隊互相可戰勝的時候，發現如果另一個球隊能戰勝其中一個隊伍，那麼這個球隊能戰勝這兩個隊伍。
我們給互相可戰勝的球隊連一條邊。
最終發現整張圖變成若幹個聯通塊，每個聯通快有明确的強弱關系。
這樣子最終答案就是最強的聯通塊的大小。
考慮加點。
每次增加一個點，我們就把這個點向與他戰勝關系不确定的聯通塊連邊，這樣子我們就可以把幾個聯通塊縮成一個塊。
暴力統計？
\(O(n^2k)\)，不可接受。
平衡樹。
可以把所有的塊丢進set裡面。
反向定義小于号，隻要大于就傳回true，隻有明确小于才傳回false。
這樣子我們隻要正反比較兩次如果都為true就說明兩個塊的關系是不清楚的。
每次加點，我們用upper_bound查詢出第一個不是明确大于目前塊的聯通塊，如果這個聯通塊也大于目前塊，那麼這兩個塊的強弱關系不清楚，我們可以合并。
一直合并到下一個塊是明确小于目前塊的為止。
然後插入目前塊。
這樣子我們就能\(O(knlogn)\)處理問題了。
代碼
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
#define file "s"
#define ll long long
using namespace std;
const int N=2009,inf=(1<<31)-1;
const int Maxn=N*(N-1)/2;
int read(){
char c;int num,f=1;
while(c=getchar(),!isdigit(c))if(c==\'-\')f=-1;num=c-\'0\';
while(c=getchar(), isdigit(c))num=num*10+c-\'0\';
return f*num;
}
int k;
struct Ub{
int sz,mx[10],mn[10];
Ub& operator +=(const Ub& rhs){
sz+=rhs.sz;
for(int i=1;i<=k;i++)
mx[i]=max(mx[i],rhs.mx[i]),mn[i]=min(mn[i],rhs.mn[i]);
return *this;
}
};
bool operator <(const Ub a,const Ub b){
for(int i=1;i<=k;i++)
if(a.mx[i]>b.mn[i])
return true;
return false;
}
set <Ub> S;
int main()
{
freopen(file".in","r",stdin);
freopen(file".out","w",stdout);
int n=read();k=read();
while(n--){
Ub qwq;
qwq.sz=1;
for(int i=1;i<=k;i++)
qwq.mn[i]=qwq.mx[i]=read();
set<Ub>::iterator it=S.upper_bound(qwq);
while(1){
if(it==S.end()|| !(*it<qwq) )break;
qwq+=*it;
S.erase(it++);
}
S.insert(qwq);
printf("%d ",S.begin()->sz);
}
return 0;
}