有趣的区间【牛客tracker 每日一题】
有趣的区间
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
给出一个长度为n nn的数组A AA，下标从1 11开始，A 1 , A 2 , . . . , A n A_1,A_2,...,A_nA1,A2,...,An。定义一个区间[ l , r ] [l,r][l,r]是“有趣的区间”，当且仅当A l ∣ A l + 1 ∣ A l + 2 ∣ . . . ∣ A r − 1 ∣ A r A_l∣A_{l+1}∣A_{l+2}∣...∣A_{r−1}∣A_rAl∣Al+1∣Al+2∣...∣Ar−1∣Ar结果为奇数。
a ∣ b a∣ba∣b表示a aa按位或b bb（按位或运算符“∣∣”是双目运算符。其功能是参与运算的两数各对应的二进位相或。只要对应的两个二进位有一个为1 11时，结果位就为1 11）。
求“有趣的区间”的个数，两个区间[ L 1 , R 1 ] , [ L 2 , R 2 ] [L1,R1],[L2,R2][L1,R1],[L2,R2]相同，当且仅当L 1 = L 2 L1=L2L1=L2且R 1 = R 2 R1=R2R1=R2。
输入描述：
第一行包含一个整数n ( 1 ≤ n ≤ 5 e 5 ) n (1≤n≤5e5)n(1≤n≤5e5)，表示数组A AA的长度。
第二行包含n nn个整数，分别表示数组A AA的n nn个元素，其中0 ≤ A i ≤ 1 e 9 0≤A_i≤1e90≤Ai≤1e9。
输出描述：
一行包含一个整数，表示 ”有趣的区间“ 的个数。
示例1
输入：
2 2 1输出：
2说明：
”有趣的区间“ 有[ 1 , 2 ] ( ( 2 ∣ 1 = 3 [1,2] (( 2∣1=3[1,2]((2∣1=3是奇数))[ 2 , 2 ] ( ( 1 [2,2] ((1[2,2]((1是奇数))共2 22个。
解题思路
首先推导核心规律，按位或运算结果为奇数的充要条件是二进制最低位为1，而按位或的特性为：区间内只要有一个数是奇数（最低位1 11），整个区间的按位或结果必为奇数，只有区间内所有数都是偶数时，按位或结果才是偶数。因此采用反向求解策略，先计算数组的总区间数n ∗ ( n + 1 ) / 2 n*(n+1)/2n∗(n+1)/2，再减去所有全偶数子区间的数量，得到有趣区间的个数；遍历数组统计连续偶数的长度c cc，遇奇数则计算该段全偶子区间数c ∗ ( c + 1 ) / 2 c*(c+1)/2c∗(c+1)/2并从总数扣除，重置c cc，遍历结束后扣除最后一段全偶区间数；该方法时间复杂度O ( n ) O(n)O(n)，无冗余计算，完美适配n ≤ 5 × 10 5 n≤5×10^5n≤5×105的规模，高效精准统计出符合要求的区间总数。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=5e5+10;ll a[N];intmain(){ll n;cin>>n;for(ll i=0;i<n;i++)cin>>a[i];ll ans=n*(n+1)/2;ll c=0;for(ll i=0;i<n;i++){if(a[i]&1){ans-=c*(c+1)/2;c=0;}elsec++;}ans-=c*(c+1)/2;cout<<ans<<endl;return0;}