YZOJ P3371 简单计数问题

时间限制：3000MS      内存限制：262144KB

难度： $6.0$          出题人：zzx

• 问题描述

给定正整数序列 $a[1], a[2], \cdots , a[n]$，你需要依次解决 $m$ 个询问，每个询问用两个正整数 $L, R$ 描述， 请求出有多少个数在 $a[L],a[L+1],\cdots,a[R]$ 中出现正偶数次。

• 编程任务

求出每个查询的结果。

• 数据输入

输入第一行四个整数 $n$、$c$、$m$ 以及 $t$ 。

第二行 $n$ 个整数 $a[1],a[2],\cdots,a[n]$，每个数在 $[1,c]$ 间。

接下来 $m$ 行每行两个整数 $l$ 和 $r$，设上一个询问的答案为 $ans$ (第一个询问时 $ans=0$ )，令 $L=(l+t \times ans) \bmod n+1, R=(r+t \times ans) \bmod n+1$，若 $L>R$，交换 $L$ 和 $R$，则本次询问为 $[L,R]$ 。

• 结果输出

对于每个询问， 输出一行对应的答案。

• 样例输入

• 样例输出

• 数据范围

对于 $50\%$ 的数据，有 $t=0$ 。

对于另外 $50\%$ 的数据，有 $t=1$ 。

对于 $100\%$ 的数据，$n, m, c \leq 100000$。

 

 

 

---

 

 

 

首先对于 $t=0$ 的点，也就意味着离线，直接一个裸的莫队即可。

那本题的正解是。。。。。。在。。在线。。。在线莫队？

其实题解里写的就是【在线莫队】，但是我个人认为就是一个裸的分块。

把序列分块，记录 块内各种颜色出现次数的桶 的前缀和，然后再记录 $ans_{l, r}$ 表示块 $l$ 到 块 $r$ 之间的答案。

桶的前缀和可以 $O(c\sqrt n)$ 预处理，之后处理 $ans$ 也可以做到 $O(n\sqrt n)$ 。

那么现在对于一个询问 $[L, R]$：

若 $[L, R]$ 没有跨过连续的两个块，那么直接暴力算一下即可；

若 $[L, R]$ 跨过了至少两个连续的块，那么找到 $L$ 之后的一个块的分界点 $x$ 以及 $R$ 之前的一个块的分界点 $y$，答案先加上 $ans_{x, y}$ 。对于剩下的数再开一个桶暴力加，但是注意的是一个数 $c$ 出现的次数为 这个桶内的次数+中间跨过的块中 $c$ 出现的次数（已经前缀和预处理了）。

时间复杂度 $O((n+c)\sqrt n)$ 。（我跑垫底了）