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\) …