首页 > 试题广场 >

有趣的区间

[编程题]有趣的区间

热度指数：1557 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一个长度为 $n$ 的数组 $A$ ，下标从 $1$ 开始， $A_1,A_2,...,A_n$ 。定义一个区间 $[l,r]$ 是“有趣的区间”，当且仅当 $A_l \mid A_{l+1} \mid A_{l+2} \mid ... \mid A_{r-1} \mid A_{r}$ 结果为奇数。

$a \mid b$ 表示 $a$ 按位或 $b$ （按位或运算符“ $\mid$ ”是双目运算符。其功能是参与运算的两数各对应的二进位相或。只要对应的两个二进位有一个为 $1$ 时，结果位就为 $1$ ）。

求“有趣的区间”的个数，两个区间 $[L1,R1],[L2,R2]$ 相同，当且仅当 $L1=L2$ 且 $R1=R2$ 。

输入描述:

第一行包含一个整数 $n$ $(1\le n\le 5e5)$ ，表示数组 $A$ 的长度。

第二行包含 $n$ 个整数，分别表示数组 $A$ 的 $n$ 个元素，其中 $0\le A_i\le 1e9$ 。

输出描述:

一行包含一个整数，表示 ”有趣的区间“ 的个数。

示例1

输入

2
2 1

输出

说明

”有趣的区间“ 有

$[1,2]$ $($ $2 \mid 1 = 3$ 是奇数 $)$

$[2,2]$ $($ $1$ 是奇数 $)$

共 $2$ 个。

算法知识视频讲解

菜狗二号

发表于 2022-01-14 10:10:50

D.有趣的区间原题链接感觉题解的办法好简单呜呜呜，但是我不会。这里给出我的做法：由题意知，只要区间中有一个数为奇数那么该区间就是有趣的区间。不妨考虑[1,n]的所有区间个数设为s，不管它是否有趣。那么显然s = (1+n)*n/2 考虑以下例子： 5 1 2 3 4 5 那么列出展开全文

yunayu

发表于 2026-01-17 00:25:15

很显然的补集思想+组合数学。不难得出包含任意奇数的区间都为有趣的区间，单步容斥可得所有区间个数减去无趣区间个数即为有趣区间个数，而无趣区间为全为偶数的区间。优化计数可用组合数学，即连续的最大无趣区间包含的无趣区间个数只与区间长度有关，因此可实现时间复杂度为的计数。天冷了，请多喝热水，祝您拥有美好的一展开全文

kilomatutinal

发表于 2026-01-17 00:53:02

喵～我来帮你解释这段代码喵！(≧ω≦)这段代码是求“有趣的区间”个数喵～一个区间要有趣，就需要区间里所有数按位或的结果是奇数呢！(・ω<)关键点喵：一个数是奇数的话，它的二进制最低位一定是1喵！所以区间按位或是奇数，就说明区间里至少有一个奇数哦～因为只要有一个奇数，按位或的最低位就是1，结果就展开全文

牛客nb666号

发表于 2024-05-17 17:51:00

有趣的区间 x是奇数 ⇔ x的二进制最低位为1 A[l] | ...|A[r]为奇数 ⇔ A[l~r]至少有一个数是奇数设以A[i]为右端点, 考虑它的左端点(<=i)能取哪些位置: (1) 如果A[i]为奇数, 左端点可以随便取, 因为包含了A[i]这个奇数, 有i+1个 (2) 如展开全文

BE-ABLE-N

发表于 2022-01-14 16:08:26

Problem Solution 翻译下题意：当一个区间内存在一个元素为奇数时，则被称为有趣的区间，并且只要两个区间的左右端点有一个不一样，这两个区间就不是同一个区间。了解题意后，如何求出满足条件的区间个数呢？我们可以假设数组内所有元素都为奇数，可以很容易地想到，此时的区间个数为1 + 展开全文

BeauWill

发表于 2026-01-17 00:42:03

根据二进制按位或的性质，我们不难发现"有趣的区间"就是至少包括一个奇数的区间。我们考虑枚举数组A下标i从1~n，枚举的时候我们只统计以当前下标为区间右端点的答案。（可以证明，这样统计是不重不漏的）如果当前枚举的数A[i]是奇数，那么所有区间[j,i]，j取遍1~i，都是" 展开全文

Kato_Shoko

发表于 2026-01-17 15:05:51

一个比较经典的题目，思路详情可看：【1月17日牛客每日一题】 #include <bits/stdc++.h> #define il inline #define double long double using namespace std; using ll = long long 展开全文

Guoxu_

发表于 2024-02-21 17:08:47

思路显然，区间中只要包含一个奇数，其结果就会是奇数。进一步思考，统计包含一个或以上奇数的区间的工作量大于统计只包含偶数的区间的工作量。代码实现 #include <bits/stdc++.h> using namespace std; using ll = long long; 展开全文

憨憨的竹林

发表于 2026-01-17 12:34:04

这道题看似跟按位或有关系，实际上并没有hhh，小误导依据题目定义，一个奇数与一个奇数或者偶数“|”运算后都会得到奇数，只有两个偶数“|”运算后会得到偶数；而按位或运算遵从交换律，那么我们翻译一下题目，也就是说，只要一个区间内有奇数，那么这个区间就满足题目条件我们在输入完数据以后可以分开进行思考，从头展开全文