题解：CF878C Tournament

· · 题解

更好的阅读体验

简单题。

我们只关心，假设现在已经维护出一个可能成为冠军的集合，在加入一个人后，情况会如何变化。

我们维护若干个集合，若只一个集合中的元素，集合内的所有元素均有可能成为冠军。

我们考虑一种偏序关系。对于集合 S, T，如果对于任意一个项目，都有 S 的最小值大于 T 的最大值，则 T 无法成为冠军。

更进一步地，假设目前冠军集合 S 和另外一个集合 T，由于 S 是目前的冠军，因此不存在 T 偏序 S 的情况；如果此时不存在 S 偏序 T，则我们可以将 T 并入 S，T 中的元素也可能成为冠军。具体的构造就是取 T 超出 S 的一个项目，先将 S 中的元素击败，又根据只考虑集合 T，所有元素均有可能获得冠军的约定，我们可以钦定 T 中任意一个元素为冠军。

那么我们可以使用一个 std::set 来维护上述的集合，注意 set 中每一个元素都是一个集合，按上述的偏序关系排序。由于我们只关心偏序关系，我们只维护每个集合的最大值和最小值。

那么这道题就做完了。由于合并最多进行 n-1 次，每次合并需要对 k 个项目逐一更新，复杂度 O(kn \log n) 可以通过。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 50006
using namespace std;
int n,m;
struct Node{int sz,minn[12],maxn[12];}tmp;
bool operator <(Node x,Node y)
{
    for(int i=1;i<=m;i++)if(x.maxn[i]>y.minn[i])return 0;
    return 1;
}
Node operator +(Node x,Node y)
{
    Node ret;ret.sz=x.sz+y.sz;
    for(int i=1;i<=m;i++)
        ret.maxn[i]=max(x.maxn[i],y.maxn[i]),ret.minn[i]=min(x.minn[i],y.minn[i]);
    return ret;
}
set<Node> S;
main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        tmp.sz=1;
        for(int j=1;j<=m;j++)
            scanf("%lld",&tmp.maxn[j]),tmp.minn[j]=tmp.maxn[j];
        set<Node>::iterator it;
        while((it=S.find(tmp))!=S.end())tmp=tmp+*it,S.erase(it);
        S.insert(tmp),printf("%lld\n",S.rbegin()->sz);
    }
    return 0;
}