#6499. 「雅礼集训 2018 Day2」颜色

内存限制:8 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

n 个数字,第 i 个数字为 a_i

m 次询问,每次给出 k_i 个区间,每个区间表示第 l_{i, j} r_{i, j} 个数字,求这些区间中一共出现了多少种不同的数字。

部分数据强制在线。

输入格式

第一行包含三个整数 n, m, p p 0 1 表示是否强制在线。

第二行 n 个正整数,第 i 个表示 a_i

接下来依次给出每个询问,每个询问第一行一个正整数,表示 k_i ,接下来 k_i 行,每行两个正整数,分别表示 l_{i, j} r_{i, j} ,若 p = 1 且这不是第一个询问,输入的 l_{i, j} r_{i, j} 是经过加密的,你需要将这两个数字分别异或上上一个询问的答案,对 n 取模后再加 1 ,两者较小值为真实的 l_{i, j} ,较大值为真实的 r_{i, j}

输出格式

对每个询问输出一行一个整数表示答案。

样例

样例输入 1

3 2 0
1 2 1
1
1 2
2
1 1
3 3

样例输出 1

2
1

数据范围与提示

对于全部数据, 1 \leq n, m, \sum k_i, a_i \leq 10^5, 1 \leq l_{i, j} \leq r_{i, j} \leq n

  • 子任务 \rm 1(points:10) n, m, \sum k_i, a_i \leq 5000
  • 子任务 \rm 2(points:10) n, m, \leq 5000
  • 子任务 \rm 3(points:20) k_i = 1
  • 子任务 \rm 4(points:20) p = 0
  • 子任务 \rm 5(points:20) 1 \leq n, m, \sum k_i, a_i \leq 50000
  • 子任务 \rm 6(points:20) :无特殊限制