YZOJ P3371 简单计数问题

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

 

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注