「CTSC2008」图腾-树状数组

发布于 10 天前  61 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「CTSC2008」图腾-树状数组

Description

给定一个$1~n$的排列,至于求什么看下面。

$n \leq 200000$

Solution

$$f[1324]-f[1243]-f[1432]&=(f[1x2x]-f[1423])+(f[12xx]-f[1234])+(f[14xx]-f[1423])$$
$$=f[1x2x]+f[1234]-f[12xx]-f[14xx]$$
$$=f[1x2x]+f[1234]+f[13xx]-f[1xxx]$$

设$l_i,r_i$分别表示$i$位置左边/右边比它小的数的个数,这些东西都可以用$l_i,r_i$表示。

  • $f[1x2x]$:枚举中间的$2$的位置$i$,则右边的位置的方案数为$n-i-r_i$。左边选两个数$(x,y)$瞒住$a_x<a_y,x<y$的方案数为$l_i \times (i-1)$。然后有两种不合法情况1.两个数都小于$x<y,a_y<a_i$。2.$y<x$分别减去即可。
  • $f[1234]$:枚举中间$2$的位置$i$。方案数为$l_i\times\sum_{j>i,a[j]>a[i]}n-j-r[j]$
  • $f[1xxx]$:$\sum \binom {n-i-r_i} {3}$
  • $f[13xx]$:枚举$3$的位置$i$,$l_i\times r_i \times (n-r_i-1)-(\sum_{j<i,a_j<a_i}r_j-(\frac{l_i\times (l_i-1)}{2}-\sum_{j<i,a_j<a_i}l_j))$

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「CTSC2008」图腾-树状数组


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前, 相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!