选数异或（2023寒假每日一题 8）
创始人
2025-05-31 00:52:06
0次
给定一个长度为 nnn 的数列 A1,A2,⋅⋅⋅,AnA_1,A_2,···,A_nA1,A2,⋅⋅⋅,An 和一个非负整数 xxx，给定 mmm 次查询，每次询问能否从某个区间 [l,r][l,r][l,r] 中选择两个下标不同的数使得他们的异或等于 xxx。
输入格式
输入的第一行包含三个整数 n,m,xn,m,xn,m,x。
第二行包含 nnn 个整数 A1,A2,⋅⋅⋅,AnA_1,A_2,···,A_nA1,A2,⋅⋅⋅,An。
接下来 mmm 行，每行包含两个整数 li,ril_i,r_ili,ri 表示询问区间 [li,ri][l_i,r_i][li,ri]。
输出格式
对于每个询问，如果该区间内存在两个数的异或为 xxx 则输出 yes，否则输出 no。
数据范围
对于 20%20\%20% 的评测用例，1≤n,m≤1001≤n,m≤1001≤n,m≤100；
对于 40%40\%40% 的评测用例，1≤n,m≤10001≤n,m≤10001≤n,m≤1000；
对于所有评测用例，1≤n,m≤100000，0≤x<220，1≤li≤ri≤n，0≤Ai<2201≤n,m≤100000，0≤x<2^{20}，1≤l_i≤r_i≤n，0≤A_i<2^{20}1≤n,m≤100000，0≤x<220，1≤li≤ri≤n，0≤Ai<220。
输入样例：
4 4 1
1 2 3 4
1 4
1 2
2 3
3 3
输出样例：
yes
no
yes
no
样例解释
显然整个数列中只有 2,32,32,3 的异或为 111。
#includeusing namespace std;const int N = 100010, M = (1 << 20) + 10;int n, m, x;
int last[M], g[N];int main(){scanf("%d%d%d", &n, &m, &x);int a;for(int i = 1; i <= n; i++){scanf("%d", &a);g[i] = max(g[i-1], last[a^x]);last[a] = i;}int l, r;while(m--){scanf("%d%d", &l, &r);if(g[r] >= l) puts("yes");else puts("no");}return 0;
}
上一篇：B端权限设计
相关内容
热门资讯
【MySQL】锁
锁 文章目录锁全局锁表级锁表锁元数据锁（MDL）意向锁AUTO-INC锁...
【内网安全】 隧道搭建穿透上线...
文章目录内网穿透-Ngrok-入门-上线1、服务端配置：2、客户端连接服务端ÿ...
GCN的几种模型复现笔记
引言 本篇笔记紧接上文，主要是上一篇看写了快2w字，再去接入代码感觉有点...
数据分页展示逻辑
import java.util.Arrays;import java.util.List;impo...
Redis为什么选择单线程？R...
目录专栏导读一、Redis版本迭代二、Redis4.0之前为什么一直采用单线程？三、R...
【已解决】ERROR: Cou...
正确指令： pip install pyyaml
关于测试，我发现了哪些新大陆
关于测试 平常也只是听说过一些关于测试的术语，但并没有使用过测试工具。偶然看到编程老师...
Lock 接口解读
前置知识点Synchronized synchronized 是 Java 中的关键字，...
Win7 专业版安装中文包、汉...
参考资料：http://www.metsky.com/archives/350.htm...
3 ROS1通讯编程提高(1)
3 ROS1通讯编程提高3.1 使用VS Code编译ROS13.1.1 VS Code的安装和配置...
大模型未来趋势
大模型是人工智能领域的重要发展趋势之一，未来有着广阔的应用前景和发展空间。以下是大模型未来的趋势和展...
python实战应用讲解-【n...
目录 如何在Python中计算残余的平方和 方法1：使用其Base公式 方法2：使用statsmod...
学习u-boot 需要了解的m...
一、常用函数 1. origin 函数 origin 函数的返回值就是变量来源。使用格式如下...
常用python爬虫库介绍与简...
通用 urllib -网络库(stdlib)。 requests -网络库。 grab – 网络库&...
药品批准文号查询|药融云-中国...
药品批文是国家食品药品监督管理局（NMPA）对药品的审评和批准的证明文件...
【2023-03-22】SRS...
【2023-03-22】SRS推流搭配FFmpeg实现目标检测 说明： 外侧测试使用SRS播放器测...
有限元三角形单元的等效节点力
文章目录前言一、重新复习一下有限元三角形单元的理论1、三角形单元的形函数（Nÿ...
初级算法-哈希表
主要记录算法和数据结构学习笔记，新的一年更上一层楼！ 初级算法-哈希表...
进程间通信【Linux】
1. 进程间通信 1.1 什么是进程间通信 在 Linux 系统中，进程间通信...
【Docker】P3 Dock...
Docker数据卷、宿主机与挂载数据卷的概念及作用挂载宿主机配置数据卷挂载操作示例一个容器挂载多个目...