算法竞赛模板
未读123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178#ifdef ShadowDrunk//李超线段树实际上是维护在二维坐标系上插入线段，同时查询x == d时y最大的线段是哪个以及对应的值的变式线段 ...
E. Mycraft Sand Sort题目翻译 题目给我们一个长度为n的排列，代表n行沙子，其元素大小就是第i行沙子的长度。题目还给我们一个长度为n的数组，其数组元素的值代表第i行沙子的颜色。最终沙子会因重力而落下，我们要计算初始有多少种排列和颜色的组合可以使得最终沙子落下来的效果与给定的一样，注意对998244353取模。
思路 首先我们通过观察发现本题的一个重要性质，数组的颜色数组是不会发生改变的，因为每一行的沙子的长度都大于等于1。所以第一格的元素的颜色就把整个数组的颜色给定了下来。并且长度为i的沙子是什么颜色也不会改变，所以方案数会增多就来源于同色的沙子之间的交换。我们发现对于颜色相同的第x行和第y行沙子可以交换的条件是沙子x和y之间不存在比其长度最小值大的异色沙子行，我们可以使用并查集和链表，从长度最小的沙子行开始考虑交换维护这个过程计算答案。
注意这里有一个误区，用并查集从小到大合并之后阶乘计算贡献是错误的，其并不可以保证我们的交换条件合法。
代码12345678910111213141516171819202122232425262728293031323334 ...
