061C

AGC061C 首先考虑怎样不重不漏计数，注意到实际上直接 \(2^n\) 算重当且仅当存在一些区间，使得这个区间中实际上没有其他人。这样导出了一个 \(O(n^2)\) 的 dp，直接记录当前最严的限制即可。 然而小学生都知道一个技巧，叫做存在是不好做的，不存在是好做的。所以考虑容斥，钦定若干区间 ......

题目链接 点击打开链接 题目解法 易知总情况数为 \(2^n\) 考虑重复计算的情况为：存在 \([l_i,r_i]\)，满足没有 \([l_j,r_j](i\neq j)\) 选在此区间中 可以得到一个容斥的 \(dp\) 做法 这个转移虽然感觉很显然，但卡了我一个晚上，一直调不出 令 \(f_i ......

## 题意 有两个长度为 $n$ 的正整数列 $A,B$。表示数 $i$ 可以填到 $A_i$ 或 $B_i$ 两个位置中的一个。问删去空位之后可以形成的排列种数。 （$ 1 \le n \le 5 \times 10^5$，$A_i,B_i$ 取遍 $\left[1, 2n\right]$）。 # ......