sfiction/selection/AtCoder
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
- AtCoder Grand Contest
- AGC005D, [容斥], 首先容斥需要计算至少i个错放的方案数、将所有位置拆分成多条链，每条链上奇偶位置相互独立，且方案数相同（错排方案的位置和元素一一对应）。奇数放在偶数位置的方案数可以表示为从n个数中选择某些数的方案数（反之亦然），如果选中一个奇数x，则表示将x放在x+1，如果选中一个偶数x，则表示将x+1放在x，因此无法选择最后一个位置和连续位置。有隔板法易得n个元素的链i个错排，仅考虑奇/偶的方案数为C(n-i,i)，总方案只需多项式相乘即可。
- AGC005E, [博弈], 定义d(u,v)为两点在B树上距离，则当d(u,v)>=3时，A可以在两个位置间相互往返而保持不败。而对于d(u,v)=3的情形，A不可能跨过B，因为会导致落败。由此简化了游戏模型。
- AGC005F, [树, 组合计数], 通过统计边来简化子树大小的统计。注意到对不同k，所取组合数的底相同，根据底统计系数用FFT加速。
- AtCoder Regular Contest
- ARC066F, [DP, 斜率优化, 分治], 将解分为不包含i和包含i的。前者只需通过DP解决。后者需要分治。合并过程中只需考虑跨过分割点的区间，因此只需要枚举一侧点，在另一侧中查询最优解，查询和DP类似。DP用斜率优化改进为O(n)。O(nlogn)。
- ARC067F, [性质, 数据结构, 差分求和], 将区间视为点，则每个Bij的覆盖区间对应一个矩形，求每个点上所盖矩形权值和。用差分求和改进复杂度。O(nmlogn+n^2)。用线段树在线硬怼也是可以的，只需要用m个单调栈维护每种券当前的使用范围。O(nmlogn)。
- ARC068E, [数论, 数据结构], 考虑做mlogm次查询，可能会将同一区间重复计入。若r-l+1>=i，则i必经过这个区间。若r-l+1<=i，则i不会重复经过这个区间。因此可以根据>=或>分类。前者通过前缀和求得，后者则用数据结构维护，依次查询。O(nlogm+mlog^2m)。另外一个做法是考虑相反的问题，则只有被i的非到达位置包含的区间才无法被到达（不会重复计入）。这样总共有mlogm个询问，内容是求被[L,R]包含的区间[l,r]的数量。可以将其转化为二维平面上矩形覆盖点查询的问题。查询事件点(L,R)，覆盖矩形则为[1..l,r..m]。通过扫描线可以在O(mlog^2m)内求解。
- ARC068F, [DP], 因为1是最低点，取走1之后，剩下部分必定单调，取法为2的幂，因此只需确定1..k-1即可。考虑取数的过程，1..k-1合法当且仅当能够被拆分为两个特殊的递减序列（元素有一定连续性），分别是取数过程中1的两侧。用dp(i,j)表示已经取i个元素，已取的最小元素为j。构造取数过程时可以始终令第一个序列的最小值小于第二个序列，所以我们只需要关注两个序列的最小值之间还有多少个数能取，这可以通过i-(n+1-j)得到，因此状态不需要第三维。转移时可以取一个更小值，或者当n-j+1!=i时，即还有比j更小的数未取时取一个更小的数。第一种转移可以用前缀和优化。O(nk)。
- AGC101F, [DP], 和平面上XXXXXXXXXXXXXXXX等价。然后转化成 O(n^2)DP。dp(i,j) 表示走到位置 (i,j)，且下一步是 (i+1,j) 的不同方案数。该方法用数据结构可以优化到 O(nlogn)。O(nlogn)。
}}}- AtCoder Grand Contest
- AGC005D, [容斥], 首先容斥需要计算至少i个错放的方案数、将所有位置拆分成多条链，每条链上奇偶位置相互独立，且方案数相同（错排方案的位置和元素一一对应）。奇数放在偶数位置的方案数可以表示为从n个数中选择某些数的方案数（反之亦然），如果选中一个奇数x，则表示将x放在x+1，如果选中一个偶数x，则表示将x+1放在x，因此无法选择最后一个位置和连续位置。有隔板法易得n个元素的链i个错排，仅考虑奇/偶的方案数为C(n-i,i)，总方案只需多项式相乘即可。
- AGC005E, [博弈], 定义d(u,v)为两点在B树上距离，则当d(u,v)>=3时，A可以在两个位置间相互往返而保持不败。而对于d(u,v)=3的情形，A不可能跨过B，因为会导致落败。由此简化了游戏模型。
- AGC005F, [树, 组合计数], 通过统计边来简化子树大小的统计。注意到对不同k，所取组合数的底相同，根据底统计系数用FFT加速。
- AtCoder Regular Contest
- ARC066F, [DP, 斜率优化, 分治], 将解分为不包含i和包含i的。前者只需通过DP解决。后者需要分治。合并过程中只需考虑跨过分割点的区间，因此只需要枚举一侧点，在另一侧中查询最优解，查询和DP类似。DP用斜率优化改进为O(n)。O(nlogn)。
- ARC067F, [性质, 数据结构, 差分求和], 将区间视为点，则每个Bij的覆盖区间对应一个矩形，求每个点上所盖矩形权值和。用差分求和改进复杂度。O(nmlogn+n^2)。用线段树在线硬怼也是可以的，只需要用m个单调栈维护每种券当前的使用范围。O(nmlogn)。
- ARC068E, [数论, 数据结构], 考虑做mlogm次查询，可能会将同一区间重复计入。若r-l+1>=i，则i必经过这个区间。若r-l+1<=i，则i不会重复经过这个区间。因此可以根据>=或>分类。前者通过前缀和求得，后者则用数据结构维护，依次查询。O(nlogm+mlog^2m)。另外一个做法是考虑相反的问题，则只有被i的非到达位置包含的区间才无法被到达（不会重复计入）。这样总共有mlogm个询问，内容是求被[L,R]包含的区间[l,r]的数量。可以将其转化为二维平面上矩形覆盖点查询的问题。查询事件点(L,R)，覆盖矩形则为[1..l,r..m]。通过扫描线可以在O(mlog^2m)内求解。
- ARC068F, [DP], 因为1是最低点，取走1之后，剩下部分必定单调，取法为2的幂，因此只需确定1..k-1即可。考虑取数的过程，1..k-1合法当且仅当能够被拆分为两个特殊的递减序列（元素有一定连续性），分别是取数过程中1的两侧。用dp(i,j)表示已经取i个元素，已取的最小元素为j。构造取数过程时可以始终令第一个序列的最小值小于第二个序列，所以我们只需要关注两个序列的最小值之间还有多少个数能取，这可以通过i-(n+1-j)得到，因此状态不需要第三维。转移时可以取一个更小值，或者当n-j+1!=i时，即还有比j更小的数未取时取一个更小的数。第一种转移可以用前缀和优化。O(nk)。
- AGC101F, [DP], 和平面上XXXXXXXXXXXXXXXX等价。然后转化成 O(n^2)DP。dp(i,j) 表示走到位置 (i,j)，且下一步是 (i+1,j) 的不同方案数。该方法用数据结构可以优化到 O(nlogn)。O(nlogn)。