Codeforces #441 Div1 D. High Cry

最後の最後まで問題を誤読するというとんでもないミスをやらかした。
http://codeforces.com/contest/875/problem/D

問題

整数列Aが与えられる。
L＜Rを満たす２値(L,R)のうち、(A[L] or A[L+1] or .... or A[R]) ＞ max(A[L]...A[R])となるものは何通りあるか。

解法

Lを総当たりしつつ、Rを数え上げよう。
Rを全部辿ると当然間に合わない。

よって左辺か右辺が変化するタイミングを求めよう。
(A[L] or A[L+1] or .... or A[R])が変化するのは、A[L]～A[R-1]で立っていないビットのうち初めてA[R]で立つビットがある場合である。
これは事前に前処理で各ビットの最寄りの登場位置を求めておけばよい。

次に、max(A[L]...A[R])が変化するのは、上記同様A[R]がこれまで立っていなかったビットを立てる場合の他、(A[L] or ... A[R-1]) = A[R]となる場合である。
例えばA[L..R]={3 0 0 6 0 0 7}となるケースである。

さて、このように左辺や右辺が変化するのは高々数十回なのでそれらの位置から、条件を満たすRの数を数え上げればよい。

int N;
int A[202020];
ll ret;
int nex[32];
map<int,int> mi;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(j,31) nex[j]=N;
	
	for(i=N-1;i>=0;i--) {
		set<int> cand;
		FOR(j,31) if((A[i]&(1<<j))==0) cand.insert(nex[j]);
		int pre=i,now=A[i];
		
		int add=ret;
		FORR(c,cand) {
			if(A[pre]!=now) {
				if(mi.count(now) && mi[now]<c) {
					ret+=mi[now]-pre;
				}
				else {
					ret+=c-pre;
				}
			}
			pre=c,now|=A[c];
		}
		FOR(j,31) if(A[i]&(1<<j)) nex[j]=i;
		mi[A[i]]=i;
	}
	
	cout<<ret<<endl;
}

まとめ

なぜか左辺をA[L] or A[R]と勘違いしていた。
想像以上に解いた人が多く、問題文も読み返したつもりだったのになぜか見逃していた…。