[模拟赛]世界杯

题意

有\(n(n\le 10^5)\)支球队，每两个球队有\(k(k\le 5)\)个属性。

当一个球队的某一项属性大于另一个球队，则这个球队有可能会战胜另外的球队。

每次会在剩余未被淘汰的球队里随机选出两个球队进行比赛。

问有可能获得冠军的球队有多少个？

分析

当两个球队互相可战胜的时候，发现如果另一个球队能战胜其中一个队伍，那么这个球队能战胜这两个队伍。

我们给互相可战胜的球队连一条边。

最终发现整张图变成若干个联通块，每个联通快有明确的强弱关系。

这样子最终答案就是最强的联通块的大小。

考虑加点。

每次增加一个点，我们就把这个点向与他战胜关系不确定的联通块连边，这样子我们就可以把几个联通块缩成一个块。

暴力统计？

\(O(n^2k)\)，不可接受。

平衡树。

可以把所有的块丢进set里面。

反向定义小于号，只要大于就返回true，只有明确小于才返回false。

这样子我们只要正反比较两次如果都为true就说明两个块的关系是不清楚的。

每次加点，我们用upper_bound查询出第一个不是明确大于当前块的联通块，如果这个联通块也大于当前块，那么这两个块的强弱关系不清楚，我们可以合并。

一直合并到下一个块是明确小于当前块的为止。

然后插入当前块。

这样子我们就能\(O(knlogn)\)处理问题了。

代码

#include

#include

#include

#include

#include

#include

#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 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::iterator it=S.upper_bound(qwq);

while(1){

if(it==S.end()|| !(*it

qwq+=*it;

S.erase(it++);

}

S.insert(qwq);

printf("%d ",S.begin()->sz);

}

return 0;

}