题意
有\(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;
}