C. 「SFCOI-1」颜色

    传统题 3000ms 512MiB

「SFCOI-1」颜色

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个长度为 nn 的序列 aamm 次询问,每次查询 [l,r][l, r] 区间内第 kk 小的颜色。

出于某些原因,本题强制在线。

输入格式

第一行,两个整数 n,mn, m

第二行,nn 个整数 a1,a2,,ana_1, a_2, \cdots, a_n

接下来 mm 行,每行三个整数 l,r,kl', r', k'

last_ans\text{last\_ans} 为上一个询问的答案,则 $l = (l' \operatorname{xor} \text{last\_ans}) \bmod n + 1,r = (r' \operatorname{xor} \text{last\_ans}) \bmod n + 1,k = (k' \operatorname{xor} \text{last\_ans}) \bmod (r - l + 1) + 1$。

注意:若 l>rl > r 则交换 l,rl, r,若上一个询问的答案为 1-1last_ans=0\text{last\_ans} = 0

输出格式

mm 行,每行一个整数。若区间内的颜色数小于 kk,输出 1-1;否则,输出区间内第 kk 小的颜色。

10 5
3 1 5 6 4 2 2 2 8 5 
411557971 957829880 532263476
522520394 877151126 788213692
29996341 805744647 928415111
67170767 343566035 82131806
228050485 939669125 751397400
1
-1
2
2
2

数据范围

对于 30%30\% 的数据,1n,m1031 \leq n, m \leq 10^3

对于另 20%20\% 的数据,1ai1041 \leq a_i \leq 10^4

对于 100%100\% 的数据,1n,m1051 \leq n, m \leq 10^51ain1 \leq a_i \leq n0l,r,k<2310 \leq l', r', k' < 2^{31}

「SFCOI-1」Sadness Fan Club Round 1

未参加
状态
已结束
规则
IOI
题目
4
开始于
2023-3-11 14:00
结束于
2023-3-11 18:00
持续时间
4 小时
主持人
参赛人数
67