CF1726G A Certain Magical Party

发布时间 2023-12-22 23:37:45作者: 进击的C++

CF1726G A Certain Magical Party

聚会上有 \(n\) 个人,第 \(i\) 个人有一个开心指数 \(a_i\)
每个人都有一种确定的个性,这种个性可以用一个二进制整数 \(b\) 来表示。如果 \(b=0\) ,那么意味着如果他将一个故事讲给一个开心指数比他低的人,他的开心指数就会增加。如果 \(b=1\) ,那么意味着如果他将一个故事讲给一个开心指数比他高的人,他的开心指数就会增加。
让我们定义讲故事的顺序为从左到右。接下来发生以下过程:从左至右的每个人给除他以外的所有人听。请注意,当这发生时,所有的快乐指数保持不变。当这个人讲完以后,他会根据他的个性计算目前开心指数比他少/多的人数,他的开心指数会加上这个量。请注意,只有当前的人的快乐指数增加
作为聚会的组织者,你不希望任何人伤心地离开。因此,你需要计算可以使得全部 \(n\) 人在这个过程的最后开心指数都相同的发言顺序的数量。如果两个发言顺序中至少有一个人的位置不同,则这两个发言顺序是不同的。
对于 \(100\%\) 的数据,满足 \(1 \leq n \leq 2\times10^5\)\(a_1 , a_2 ,...,a_n(1\leq a_i\leq 2n)\)\(b_1 , b_2 ,...,b_n(b_i \in \{0,1\})\)