2021.10.31模拟赛

A pair of wings for me at this moment

2021.10.21 模拟赛

题没交上去

某种意义的模拟题，线段树暴力维护当然是可以的

但是考虑每次会加入一个空格和删除若干空格，所以 set 一类的东西会更方便些

或者用栈记录空格位置和长度来做到 $O(n)$

发现一个区间会被重复统计当且仅当它的左端点是最小值或右端点，用单调栈统计下每个数作为最大/最小值能到的左/右端点

然后减去同时满足左右端点的，可以用主席树统计 $\sum\limits_{j=i+1}^{r_i}[l_j \le i]$ 的个数

发现其实这个填数的过程限制很多，从 $[i,i+b]$ 到 $[i+1,i+b+1]$ 的过程中如果 $a_i$ 只出现了一次，那么 $a_{i+b+1}$ 只能是 $a_i$

否则的话他可以随便放一个数，假设是 $a_k$ 则往后移动 $k$ 位后就又可以随便填

设 $dp_{i}$ 表示填第 $i$ 个格子方案数，则 $dp_i = \sum\limits_{j=i+1}^{i+b}dp_j$ 后缀和优化下可以 $O(n)$

然后考虑前 $b+1$ 个数的状态，枚举第一次出现重复的位置是 $i$ 则另一个可以选择 $b+1-i$ 个位置，其他数有 $(b-1)!$ 的方案，乘上 $dp_{i+b+1}$ 即可

很好想，每次询问容斥一遍就行

不过不太好写，要注意二元环和枚举的子集恰好构成环一类的