CF878C Tournament

题意翻译

最近Berland开始了一场有k种运动的比赛。瓦萨亚希望在赌场上赚钱。比赛的计划非常神秘，并没有完全公开。比赛选手背靠背举行，每场比赛都涉及两名尚未淘汰的运动员。每场比赛都可以举行k种运动里的任意一种，失败者则遭到淘汰。最后剩下的运动员成为冠军。除此之外，该方案可以是任意的，不提前公开。瓦西亚了解各种运动中的运动员的力量。他认为，拥有更高力量的运动员总能获胜。比赛每年举行一次，每年都有一名新参赛者加入比赛。在第一场比赛中，只有一名运动员参加，第二场比赛有两名运动员，依此类推。请你帮助他找到每一年可能获得冠军的人数。

题目描述

Recently a tournament in k kinds of sports has begun in Berland. Vasya wants to make money on the bets.

The scheme of the tournament is very mysterious and not fully disclosed. Competitions are held back to back, each of them involves two sportsmen who have not left the tournament yet. Each match can be held in any of the k kinds of sport. Loser leaves the tournament. The last remaining sportsman becomes the winner. Apart of this, the scheme can be arbitrary, it is not disclosed in advance.

Vasya knows powers of sportsmen in each kind of sport. He believes that the sportsmen with higher power always wins.

The tournament is held every year, and each year one new participant joins it. In the first tournament, only one sportsman has participated, in the second there were two sportsmen, and so on. Vasya has been watching the tournament for the last n n n years. Help him to find the number of possible winners for each of the n n n tournaments.
输入格式

The first line contains two integers nand k ( 1<=n<=5⋅10^4 1<=n<=5·10^4 1<=n<=5⋅10^4 , 1<=k<=10 1<=k<=10 1<=k<=10 ) — the number of tournaments and the number of kinds of sport, respectively.

Each of the next n n n lines contains kintegers si1,si2,...,sik s_{i1},s_{i2},...,s_{ik} si1,si2,...,sik ( 1<=sij<=109 1<=s_{ij}<=10^{9} 1<=sij<=109 ), where sij s_{ij} sij is the power of the i i i -th sportsman in the j j j -th kind of sport. The sportsman with higher powers always wins. It's guaranteed that for any kind of sport all of these powers are distinct.
输出格式

For each of the n n n tournaments output the number of contenders who can win.
输入输出样例
输入 #1

输出 #1

1
2
1

输入 #2

输出 #2

1
1
3

输入 #3

输出 #3

1
1
2

说明/提示

In the first sample:

In the first tournament there is only one sportsman, and he is the winner.

In the second tournament, there are two sportsmen, and everyone can defeat another, depending on kind of sports.

In the third tournament, the third sportsman in the strongest in both kinds of sports, so he is the winner regardless of the scheme.

考虑把两个人的比赛连边，如果A可能赢B且B可能赢A，则他们可以互相到达，用强连通分量的方法进行缩点，那么最后整张图一定是一个链，那么第一个强连通分量的大小就是答案。

不过对于强连通分量的处理，这题有一个非常精妙的方法，就是用set，把输赢变成重载运算符，那么如果如果A可能赢B且B可能赢A，则A==B，可以直接用find函数。

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int data=0,w=1;
    char ch=0;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') {w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {data=data*10+ch-'0';ch=getchar();}
    return data*w;
}
void write(int x) {
    if(x>=10) write(x/10);
    register char ch=x%10+'0';  
    putchar(ch);
}
int n,m,ans,k;
struct node {
    int sz,mx[12],mn[12];
    friend bool operator < (node a,node b) {
        for(int i=1;i<=k;i++)
            if(a.mx[i]>b.mn[i]) return 0;
        return 1;
    }   
} sxd;
set <node> q;
signed main() {
    cin>>n>>k;
    for(int i=1;i<=n;i++) {
        sxd.sz=1;
        for(int j=1;j<=k;j++) {sxd.mn[j]=sxd.mx[j]=read();}
        set <node> :: iterator it=q.find(sxd);
        while(it!=q.end()) {
            sxd.sz+=(*it).sz;
            for(int j=1;j<=k;j++) {
                sxd.mx[j]=max(sxd.mx[j],(*it).mx[j]);
                sxd.mn[j]=min(sxd.mn[j],(*it).mn[j]);
            }
            q.erase(it);
            it=q.find(sxd);
        }
        q.insert(sxd);
        write((*q.rbegin()).sz);
        puts("");
    }
    return 0;
}