Luogu6579 [Ynoi2019] Happy Sugar Life

发表于 更新于 分类于 ， ， 阅读次数：

第十三分块。

题意：给出一个长为 的序列 。

每次询问给出 ，求将 保留 内的值之后的顺序对个数。

允许离线， ，时限 ，空限 。

  • 对于 NOI 版，时限 ，空限 。

这玩意不弱于区间逆序对，考虑根号做法。

对于某次询问，将贡献分为五类：散块内部，两个散块之间，整块内部，整块之间，整块和散块之间。

  • 和散块有关的贡献（整块和散块之间、两个散块之间，散块内部）

    枚举散块的元素 ，计算其与后方元素 之间的贡献。这是查询“区间内 内的数的个数”。

    类似二次离线莫队，将询问离线后用值域分块扫描线求解，复杂度为 。

  • 整块内部的贡献

    对于每个整块，进行块内离散化（查询时，为了避免二分，还要维护一个离散化映射表）。

    在一个块看来，只有 种本质不同的值域区间。

    记 表示块 中 （ 已离散化）中的顺序对数，可以类似二维前缀和递推求解。

  • 整块之间的贡献

    • 的情况。

      将元素从小到大排序，逐个加入。维护每个块内出现的数的个数，记 为块 与 之间的顺序对。

      插入 时只需更新 ，查询时答案是 。这样插入和查询就都能做到 。

    • 的情况。

      首先用 的答案减去 的答案，然后只剩 的错误贡献。

      枚举每个块，考虑其中 内的数，询问是“查询块 内有多少个 的数”。

      记 表示前 个块中有多少个数 ，预处理之后，容易回答上述询问。

    离线逐块处理以节省空间。

时间复杂度 ，空间复杂度 。