把 team 相同的分成一组，我们可以做这样一个问题：钦定每个点的出度和入度求连边数。
当然这里我们发现有一些不同方案数的丢失，出现在两部分，入边和出边的分配。
由于我们清楚每一组的构成，每一组里入边的分配是容易计算的，就是 \(\frac{indeg!}{\prod c!}\)。
出边的分配考虑在 dp 里做。
这个连边的过程，如果排成一列，非常像线头 dp。
设 \(f(i,j,k)\) 表示前 \(i\) 个组内部匹配完毕，还剩 \(j\) 个入线头 \(k\) 个出线头的方案数，转移再枚举两层循环，这里的转移系数需要思考一下：首先是 \(i+1\) 为起点的若干条出边，分配出一部分向左剩下向右，这里有一个组合数；另外从 \(k\) 个出线头分配若干个给 \(i+1\)，还有未来的若干个出线头分配一些给它，一共有三个组合数系数。
不太会算这个复杂度，但跑的非常快，感觉弗如容斥做法的 \(O(n^2)\) 和 \(O(n\log^2 n)\)。
如果一个点在距离人 \(x\) 的时候被打上标记，以它为中心做一个边长 \(2x\) 的正方形，则这个人首先必须落到正方形的边上，且永远不能进入它。
由于可以认为人的行动轨迹是无限长的，那么正方形的左上角或者右下角必定有且仅有一个会被人经过，那就不妨每个点为中心做一个反斜杠的射线，当人被这条射线扫到的那一步给它打标记。
在坐标系上所有这样的斜线画出来，按照斜线为阶段去 dp，然后就是经典的 slope trick 形式了。时间复杂度 \(O(n\log n)\)。
令 \(m:=m+1\)，然后我们认为一行的权值是第一个白色格子的位置。
考虑 subtask4，可以通过很多手段算出最终状态每一行的美丽值。然后可以用线段树维护区间内的 min/min count，还有 sum 和 tag（表示给区间的 min position 加 tag），在 \(O(m\log n)\) 的时间内算出来。
考虑动态的情况，维护每一列上的白色连续段，每个连续段用 set 的形式存储在 \(\log n\) 个节点中（seg是从行的角度来看的），然后一个位置（行）的权值是 seg 上，根到它的所有节点的 set 里最小的列。
这样的设计是难以去维护的，因为 min/min count变的很繁琐。
但是他们只是用来决定三操作给哪些人加的，我们的 min/min count还是只对于子树信息去维护，而在三操作之前，可以在线段树上问出真正的区间最小权值，然后再下去决定给哪些人加。举例：如果根处的 set 存的就是最小权值，那么其实不是对 min pos 加而是每个位置都要加。
所以我们要维护两个 tag 了，一个是全局加的，一个是给 minpos 加的。
但是 tag 下放的时候还有学问，如果一个给 minpos 加的标记，但是 min=你当前这个节点 set 里存的 min，那么下传过后本来的 minpos 加其实变成了全局加，这个细节很有感觉。
这样时间复杂度是 \(O(m\log^2)\) 的。考虑卡常，把 set 换成可删堆。但是可删堆是不能空删的（删除一个不存在的数），所以外层维护连续段要做的比较精细。
令 \(a_i:=2n-a_i+1\)，然后我们认为每次保护的是编号比较小的。
首先第一个人一定赢，第二个人很可能赢。
第二个人赢不了肯定是 \(h_1=h_2=1\)。如果他们高度不相同那第二个人还是赢麻。
如果 \(h_1=h_2\) 那么 \(h_2\) 先掉一次然后再赢。
那这个过程拓展一下就是不断扫，当 \(h_i\) 前面出现一个高度相同的人的时候会继续减一。减成 \(0\) 就是输。
我们只关注前面出现的人的极长前缀，设 \(f(i,j)\) 是前 \(i\) 个人，\(1\sim j\) 都出现过了而 \(j+1\) 没有的方案数即可。
转移其实挺好想的，不写了。复杂度 \(O(n^3)\)。
有一个细节是先默认 \(2n\) 个人本质不同这样方便算一些系数，最后除掉 \(2^n\) 即可。
标签：set,log,min,复杂度,2023.3,tag,权值 From： https://www.cnblogs.com/Cry-For-theMoon/p/17170716.html