#P4546. codechef XRQRS

    ID: 3667 传统题 1000ms 512MiB 尝试: 773 已通过: 132 难度: 6 上传者: 标签>CF2100提高可持久化 Trie路径复制前缀版本作差最大异或查询按位贪心Trie 上第 k 小

codechef XRQRS

题目描述

给定一个初始时为空的整数序列(元素由 11 开始标号)以及一些询问:

类型1:在数组后面就加入数字 xx。

类型2:在区间 [l,r][l,r] 中找到 yy,最大化 x⊕yx \oplus y。

类型3:删除数组最后 kk 个元素。

类型4:在区间 [l,r][l,r] 中,统计小于等于 xx 的元素个数。

类型5:在区间 [l,r][l,r] 中,找到第 kk 小的数。

输入格式

输入数据第一行为一个整数 qq,表示询问个数。

接下来 qq 行,每行一条询问,对应题目描述。

类型1的询问格式为「11 xx」。

类型2的询问格式为「22 ll rr xx」。

类型3的询问格式为「33 kk」。

类型4的询问格式为「44 ll rr xx」。

类型5的询问格式为「55 ll rr kk」。

输出格式

对于每个2、4、5询问,输出一行对应答案。

样例输入

10
1 8
5 1 1 1
1 2
2 2 2 7
2 2 2 7
1 1
4 2 2 2
2 1 2 3
4 1 3 5
1 6

样例输出

8
2
2
1
8
2

数据规模与约定

令 nn 表示每次询问前数组中元素的个数。

对于第三类询问,1≤k≤n1\le k\le n。

对于第五类询问,k≤r−l+1k\le r-l+1。

1≤l≤r≤n1\le l\le r\le n,1≤x,n≤5×1051\le x,n\le 5\times 10^5。