A. Short Program

每一位是独立的，分别考虑每一位初始是 0/1 时的最终状态，即可用 2-3 行解决。

B. Teams Formation

首先把同一辆车中的相邻 k 个人去掉，设去掉后每辆车的人数为 n。

若 k\geq n，除非每辆车中的人来自的城市两两相同，此时答案为 nm\bmod k；否则一个人都不会去掉，答案为 nm。

若 k<n，则考虑把相邻且相等的极大段缩成一个元素 (val,len)，val 表示这段元素的值，len(<k) 表示元素数，设共有 t 段。此时只有两辆相邻的车之间会消掉人，依次比较首位的两个元素，直到 val_i\neq val_{t-i+1} 或 len_i+len_{t-i+1}\neq k。若所有 i\in[1,t] 都匹配，说明每相邻两辆车都会消完，答案为 (m\bmod2)n；否则还有几种情况。

第一种是相邻两辆车之间被消掉的人数 sum<n。此时每两辆车间不会互相影响，答案为 nm-(m-1)sum；

第二种则反之。考虑什么时候会出现这种情况，发现一定有 t 为奇数且匹配到正中间的时候失配（若不失配就会对称地匹配完所有元素了）。设正中间的元素长度为 l，我们考虑先消除不是正中间的元素。那么答案为 nm-(m-1)(sum-l)。这样剩下的正中间元素会连在一起，可以方便地得出消去的人数 ml-ml\bmod k。所以最终的答案为 nm-(m-1)(sum-k)-[ml-ml\bmod k]。

但还有一种特殊的情况，即上述的第二种情况中，所有正中间元素恰好被消完了（k\mid ml），此时左右两端剩下的就会接到一起消掉，答案为 0。

细节虽然多，但讨论清楚就好了。

C. Tournament

考虑建图，若运动员 a 在某种项目比运动员 b 强，则从 a 到 b 连一条有向边。一个点对答案有贡献当且仅当从它出发可以到达所有点。考虑把强连通分量所成点，那么容易证明没有两个 SCC 间互相可以击败对方的情况，即缩点后的图是一条有向链，答案为链首 SCC 的大小。因此我们可以对于每个 SCC 维护它每个项目的最大值和最小值，以及它的大小。那么链中靠前的节点每个项目的最小值一定比靠后的节点的最大值大，即这条链间存在全序关系。这是容易维护的。

考虑加入一个运动员 x 的过程。若这个运动员的某个项目比一个 SCC 中这个项目的最小值大，则他可以击败这个 SCC；若这个运动员的某个项目比一个 SCC 中这个项目的最大值小，则他可以输给这个 SCC。设 A 为他可以击败的最强的SCC（引导链的一个前缀），B 为他可以输给的最弱的 SCC（引导链的一个后缀）。若 A 比 B 强（可以证明此时没有比 A 弱、比 B 强的 SCC），则 x 单独形成了一个 SCC，并加入到 A,B 之间；否则，B 和 A 间所有的 SCC（即前缀与后缀的交）应被缩成一个 SCC，因为它们可以通过 x 互相击败对方，同时 x 也应加入这个 SCC 中。这个过程可以用平衡树 / std::set 快速维护。缩点的操作涉及的 SCC 总数是 O(n) 的，总复杂度为 O(nk\log n)。代码：

#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
const int MAXN=55000;
const int MAXK=10;
int n, k, X, Y;
struct Node
{
    int v[2][MAXK], siz;
    bool operator < (const Node& rhs) const
    {
        return v[X][Y]<rhs.v[X][Y];
    }
    void insert(const Node& rhs)
    {
        for (int i=0; i<k; i++)
        {
            v[0][i]=min(v[0][i], rhs.v[0][i]);
            v[1][i]=max(v[1][i], rhs.v[1][i]);
        }
        siz+=rhs.siz;
    }
};
int main()
{
//  freopen("C.in", "r", stdin);
//  freopen("C.out", "w", stdout);
    scanf("%d%d", &n, &k);
    set<Node> s;
    for (int i=1; i<=n; i++)
    {
        Node t; t.siz=1;
        for (int j=0; j<k; j++)
        {
            int x; scanf("%d", &x);
            t.v[0][j]=t.v[1][j]=x;
        }
        Node a, b;
        memset(a.v, 0, sizeof a.v);
        memset(b.v, 0x3f, sizeof b.v);
        for (int j=0; j<k; j++)
        {
            X=0, Y=j; auto it=s.lower_bound(t);
            if (it!=s.begin()) a=max(a, *(--it));
            X=1, Y=j; it=s.upper_bound(t);
            if (it!=s.end()) b=min(b, *it);
        }
        if (a<b) s.insert(t);
        else
        {
            auto lt=s.find(b), rt=s.find(a); rt++;
            while (lt!=rt) t.insert(*lt), s.erase(lt++);
            s.insert(t);
        }
        printf("%d\n", s.rbegin()->siz);
    }
    return 0;
}

D. Magic Breeding

从答案入手考虑。容易观察到每个生物的某个特定的性状只会从初始的 k 个生物身上继承。于是我们就有了思路：把答案表示为 k 位二进制串，其中第 i 位为 1 表示答案不小于第 i 个初始生物的这种性状。于是取 \max 操作就变成了按位或，取 \min 操作就变成了按位与。

然而仅这样做并不能优化复杂度，但是会有一个性质：不同两位之间的运算是独立的。对于每一位，我们可以得到初始生物在这一位上的值，若对于两个不同的性状，初始生物在这一位上的值两两相同，则后续的操作也会得到同样的结果。我们一共有 k 个初始生物，因此会有 2^k 种初始值，对应 2^k 个 01 串。因此可以维护这些初始值经过若干次操作后的答案，询问时合并这种性状对应的初始值即可。

实现时需要预处理每种性状对应的初始值，可以用 std::bitset 加速维护过程。复杂度为 O(nk^2+\frac{q2^k}{64})。

#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
const int MAXN=110000;
const int MAXK=15;
const int MAXS=1<<12;
int a[MAXN][MAXK];
int c[MAXN][MAXK];
bitset<MAXS> b[MAXN];
int main()
{
//  freopen("D.in", "r", stdin);
//  freopen("D.out", "w", stdout);
    int n, k, q;
    scanf("%d%d%d", &n, &k, &q);
    for (int j=1; j<=k; j++)
        for (int i=1; i<=n; i++)
            scanf("%d", &a[i][j]);
    for (int i=1; i<=n; i++)
        for (int j=1; j<=k; j++)
            for (int p=1; p<=k; p++)
                if (a[i][p]>=a[i][j]) c[i][j]|=1<<p-1;
    for (int i=1; i<=k; i++)
        for (int j=0; j<MAXS; j++) b[i][j]=j>>i-1&1;
    for (int i=1, m=k; i<=q; i++)
    {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);
        switch (t)
        {
            case 1: b[++m]=b[x]|b[y]; break;
            case 2: b[++m]=b[x]&b[y]; break;
            case 3:
                int ans=0;
                for (int j=1; j<=k; j++)
                    if (b[x][c[y][j]]) ans=max(ans, a[y][j]);
                printf("%d\n", ans);
                break;
        }
    }
    return 0;
}