分块-题目

「DTOI-2」星之界

不会做，思路来自 Konata28。以下小块指分块中不完整的块，大块指分块中完整的块。

按块大小为 $\sqrt n$ 对序列分块，每个块内开一个桶维护元素。由于值域与 $n$ 同阶，故桶的空间是 $O(n\sqrt n)$ 的。

先来化简柿子，不难得到 $\prod\limits_{i=l}^rC_{\sum_{j=l}^ia_j}^{a_i}=\frac{(\sum_{i=l}^ra_i)!}{\prod_{i=l}^ra_i!}$。

考虑如何合并两个块询问的答案：只需要将两个块的答案相乘，然后设两个块的和分别为 $x$ 与 $y$，那么答案再乘上 $\frac{(x+y)!}{x!y!}$ 即可。

故每一块只需要维护两个信息：区间和 与 区间答案。

考虑一次修改操作，小块的暴力修改。大块的直接改桶信息。假设有 $\alpha$ 个 $x$ 要改为 $y$，那么区间和 $+\alpha(y-x)$，区间答案乘 $(x!)^\alpha$，除 $(y!)^\alpha$，再除去原来区间和的阶乘，乘上新的区间和的阶乘即可。由于 $\alpha\le\sqrt n$，故只要与预处理出 $10^5$ 及以内数的阶乘的 $1$ 到 $\sqrt n$ 次幂与他们的逆元，就能在 $O(\sqrt n)$ 的复杂度内完成一次操作。

此处用到的另一个较为巧妙的技巧是代表元。发现小块暴力求解是需要获取他的真实的值。我们另一个块中一个值的代表元是块中这个数第一个出现的位置。每次整块修改时 $x\to y$ 只要将 $x$ 的代表元指向 $y$ 的代表元即可，若 $y$ 没有代表元，则直接修改 $x$ 代表元位置的值即可。

JRKSJ Round 6 2D/1B 第七学区

场切，差点一血。第一眼：什么傻逼题。第二眼：$5\times 10^7$ 啊，没事了。

考虑 $O(n\log V)$ 如何做。看到或，考虑按位计算贡献。我们先枚举每一位，看有多少个子区间的或这一位是 $1$。根据或运算的性质，我们发现只有这一位全 $0$ 的区间才是 $0$。于是对于每一位，将原序列转换为一个 01 序列，求出所有全 $0$ 的连续段，某一位 $i$ 的贡献就是 $2^i\times(\binom{n}{2}-\sum\binom{len_i}{2})$。$\{len\}$ 是所有全 $0$ 连续段的长度。

但是发现 $O(n\log V)$ 的复杂度是无法接受的，同时 $O(n)$ 的空间也是无法接受的。接下来的思路来自 cxy，膜拜。

考率对原序列进行分块，每个块的大小是 $B$。将原序列的答案拆成两部分：块内贡献 与 块间贡献。采取不同方式计算。

块内贡献用暴力枚举的方式计算，每个块内的复杂度 $O(B^2)$，块个数 $O(\frac{n}{B})$，于是这部分就在 $O(nB)$ 的复杂度内轻松解决。

块间的贡献较为麻烦，接下来分步解决。

首先考虑在较低复杂度内算出每一个二进制位在块内的第一个与最后一个 $1$ 的出现位置。暴力是单个块 $O(B\log V)$ 的，不够优秀。

考虑对块内的元素 $\{a\}$ 求前缀或运算和，称为序列 $\{s\}$。对于一个数 $a_i$，块内第一个出现在 $i$ 位置的二进制位就是 $s_i-s_{i-1}$ 的所有二进制为 $1$ 的位，不断取 $\text{lowbit}$ 即可。由于每一个二进制位只会在一个位置被算到，所以处理第一次出现位置的复杂度是 $O(\log V)$ 的，非常优秀。最后一个同理。因此单个块内处理该信息的复杂度是 $O(2\log V)$（本题较卡常，故把常数带在复杂度内），即 $O(128)$，所有块复杂度 $O(\frac{128n}{B})$。下称 $i$ 二进制位在块内的第一次出现位置为 $f_i$，最后一个位置为 $g_i$。

接下来延续第一种算法的思想，枚举每一个二进制位，保存该二进制位上一个 $1$ 出现的位置，为 $lst_i$。那么这一位的跨块且或为 $0$ 的且右端点在该块内的区间个数是 $(f_i-l)\times (l-lst_i-1)$。又容易算出所有跨块的区间个数，用其减去所有不合法的区间个数就是这一位或为 $1$ 且跨块的区间个数，乘上二进制值即为这一位贡献。块内计算该信息复杂度为 $O(\log V)$ 即 $O(64)$。所有块复杂度为 $O(\frac{64n}{B})$。

因此最终时间复杂度 $O(nB+\frac{128n+64n}{B})=O(nB+\frac{192n}{B})$，取 $B=14$ 左右时复杂度较为优秀，约为 $O(14n)$。空间上只需要存当前块的 $B$ 个值与每一位的上一次出现位置，与该块内每个二进制位出现的第一个与最后一个位置，即 $O(B+\log V)$，约 $250$ 个 long long 变量，绰绰有余。于是解决了此题。