A6014. 「2017 山东三轮集训 Day6」C
编程题
省选/NOI-
知识点
题目描述
JOHNKRAM 对于可持久化数据结构比较感兴趣，某天他突然想到：能否将可持久化线段树和可持久化字典树合二为一呢？于是他出了这样一道题：
给一个长度为 $n$ 的序列 $a_i$，每次对序列中的所有数与另外某个数进行一次某种位运算或者询问区间 $[l, r]$ 内第 $k$ 小的数是多少。JOHNKRAM 发现他自己不会做，于是他来向你求助。
给一个长度为 $n$ 的序列 $a_i$，每次对序列中的所有数与另外某个数进行一次某种位运算或者询问区间 $[l, r]$ 内第 $k$ 小的数是多少。JOHNKRAM 发现他自己不会做，于是他来向你求助。
输入格式
第一行包含两个整数 $n$ 和 $m$，表示序列长度和操作个数。
第二行包含 $n$ 个整数，表示序列 $a_i$。
接下来 $m$ 行，每行是以下四种之一：
* $\texttt{Xor x}$
* $\texttt{And x}$
* $\texttt{Or x}$
* $\texttt{Ask l r k}$
前三种表示对整个序列与 $x$ 进行一次给定位运算，最后一种表示一次询问。
第二行包含 $n$ 个整数，表示序列 $a_i$。
接下来 $m$ 行，每行是以下四种之一：
* $\texttt{Xor x}$
* $\texttt{And x}$
* $\texttt{Or x}$
* $\texttt{Ask l r k}$
前三种表示对整个序列与 $x$ 进行一次给定位运算，最后一种表示一次询问。
输出格式
对于每一次询问，输出一个整数，表示区间 $[l, r]$ 内第 $k$ 小的数。
输入输出样例
输入 #1
10 10 1 2 3 4 5 6 7 8 9 0 Xor 1 And 254 Ask 1 2 2 Ask 1 8 3 Ask 1 7 4 Or 513 Xor 2 Ask 5 10 3 Ask 1 9 6 Ask 3 10 3
输出 #1
2 2 4 517 519 517
说明/提示
对于 $5\%$ 的数据，$1 \leq n \leq 1000$；
对于另外 $35\%$ 的数据，最多存在两种修改操作；
对于 $100\%$ 的数据，$1 \leq n,m \leq 50000, 0 \leq a_i, x < 2 ^ {31}, 1 \leq l \leq r \leq n, 1 \leq k \leq r - l + 1$。
对于另外 $35\%$ 的数据，最多存在两种修改操作；
对于 $100\%$ 的数据，$1 \leq n,m \leq 50000, 0 \leq a_i, x < 2 ^ {31}, 1 \leq l \leq r \leq n, 1 \leq k \leq r - l + 1$。