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)\) 。（我跑垫底了）