Split an Interval into OR and AND
Autumn Tournament (2025)
Submission name: oriand.cpp
Problem summary
Count intervals [L,R] of length at least2 that admit a split M: the OR of [L,M] contains all K bits and the AND of [M+1,R] is0. Count each interval once, regardless of the number of valid splits.
Input
N K, then N nonnegative K-bit integers.
Output
The number of qualifying intervals.
Constraints
1 ≤ N ≤250000; 1≤K≤63; 0≤Ai≤2^K−1.
Worked example
Original statement sample.
Input
6 1 1 0 0 0 1 0
Output
9
Solution analysis
- For a fixed L, the earliest possible split M is the earliest endpoint where every bit has appeared as1. Moving the split later cannot help the AND suffix reach0 sooner: the earlier suffix contains every element of the later suffix and possibly more, so its AND can only have fewer set bits. It is therefore sufficient to try the earliest M.
- Scan backward while keeping, for each bit, its next1 position and next0 position. The maximum of the next1 positions gives orEnd[L]; the maximum of the next0 positions gives zeroEnd[L], the earliest endpoint where the AND from L is0. A missing bit occurrence uses the sentinel N.
- For every L, let start=orEnd[L]+1. If start<N, the earliest qualifying R is zeroEnd[start]. All larger R also work, so add N−R. With K=1 and [1,0,0,0,1,0], the contributions by L are5,1,1,1,1,0, totaling9.
Why it works
An OR is full exactly when each bit has a1 somewhere in its interval, and an AND is zero exactly when each bit has a0. Next-occurrence maxima therefore find their earliest endpoints exactly. The earliest-split argument shows no qualifying interval is missed, while counting endpoints only once for each L prevents duplicate counting across splits.
Watch out. Use unsigned long long for values and1ULL<<bit; K can be63. Never shift a signed1 by62. A missing occurrence means no endpoint exists. Both split parts must be nonempty, and the answer needs long long.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,bits;
cin>>n>>bits;
vector<unsigned long long>values(n);
for(auto&value:values){
cin>>value;
}
// A missing next occurrence uses n, meaning no valid endpoint exists.
vector<int>nextOne(bits,n),nextZero(bits,n);
vector<int>orEnd(n),zeroEnd(n);
for(int i=n-1;i>=0;i--){
int fullOr=0;
int zeroAnd=0;
for(int bit=0;bit<bits;bit++){
if(values[i]&(1ULL<<bit)){
nextOne[bit]=i;
}
else{
nextZero[bit]=i;
}
fullOr=max(fullOr,nextOne[bit]);
zeroAnd=max(zeroAnd,nextZero[bit]);
}
orEnd[i]=fullOr;
zeroEnd[i]=zeroAnd;
}
long long answer=0;
for(int left=0;left<n;left++){
int suffixStart=orEnd[left]+1;
if(suffixStart<n){
answer+=n-zeroEnd[suffixStart];
}
}
cout<<answer<<'\n';
}