Codeforces #234 Div2. E. Inna and Binary Logic

若干面倒だが何とか解ききった。
http://codeforces.com/contest/400/problem/E

問題

数列A[1][1]～A[1][N]があるとき、A[k][i]=A[k-1][i] and A[k-1][i+1]の漸化式により数列A[k][1]～A[k][N+1-k]までを作っていく。
最終的にA[N][1]まで要素を作ると合計でN*(N+1)/2個の要素ができる。

初期状態としてA[1][1]～A[1][N]が与えられる。
また、その後クエリとして(p[i],v[i])が与えられるので、その際A[1][p[i]]=v[i]を代入する。
各クエリを実行した後、A[N][1]までの各要素を生成した場合のN*(N+1)/2要素の和を答えよ。

解法

bitwise-andの問題なので、ビットごとに考える。
まず、A[1][1]～A[1][N]までの数値が最終的な和にどう反映されるかを考える。
i番目のbitがA[1][1]～A[1][N]中でj個連続して立っていたとすると、A[2][1]～A[2][N-1]の間では(j-1)個、A[3][1]～A[3][N-2]の間では(j-2)個…と連続して立つ数が減少する。
よってその総和は(2^i)*j*(j+1)/2とO(1)で求めることができる。

この事実より、この問題は各ビットにおいて1が連続して何個立つかを管理できれば、その総和を簡単に答えることができる。
以下の実装では、A[1][1]～A[1][N]の各ビットにおいて1が連続する場所を(開始位置,連続数)のペアの配列で管理し、クエリ毎に1を増やしたり減らしたりしている。

int N,M;
int A[100002];
map<int,int> L[20];
ll tot[20];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N>>M;
	FOR(i,N) {
		cin>>A[i];
		FOR(j,20) if(A[i]&(1<<j)) {
			if(L[j].empty()) L[j][i]=1;
			else {
				map<int,int>::iterator it=L[j].end();
				it--;
				if(it->first+it->second==i) it->second++;
				else L[j][i]=1;
			}
		}
	}
	FOR(j,20) ITR(it,L[j]) tot[j]+=it->second*(ll)(it->second+1)/2;
	
	
	FOR(i,M) {
		cin>>x>>y;
		x--;
		ll t=0;
		FOR(j,20) {
			map<int,int>::iterator it=L[j].upper_bound(x);
			if((A[x]&(1<<j))>0 && (y&(1<<j))==0) {
				it--;
				tot[j]-=it->second*(ll)(it->second+1)/2;
				if(it->first+it->second-1!=x) {
					L[j][x+1]=it->first+it->second-1-x;
					tot[j]+=L[j][x+1]*(ll)(L[j][x+1]+1)/2;
				}
				if(it->first==x) {
					L[j].erase(it);
				}
				else {
					it->second=x-it->first;
					tot[j]+=it->second*(ll)(it->second+1)/2;
				}
			}
			if((A[x]&(1<<j))==0 && (y&(1<<j))>0) {
				if(it==L[j].begin()) {
					if(it!=L[j].end() && it->first==x+1) {
							tot[j]-=it->second*(ll)(it->second+1)/2;
							tot[j]+=(it->second+1)*(ll)(it->second+2)/2;
							L[j][x]=1+it->second;
							L[j].erase(it);
					}
					else {
						tot[j]++;
						L[j][x]=1;
					}
				}
				else {
					map<int,int>::iterator bit=it;
					bit--;
					
					if(bit->first+bit->second==x) {
						tot[j]-=bit->second*(ll)(bit->second+1)/2;
						if(it!=L[j].end() && it->first==x+1) {
							tot[j]-=it->second*(ll)(it->second+1)/2;
							bit->second+=1+it->second;
							L[j].erase(it);
							
						}
						else {
							bit->second++;
						}
						tot[j]+=bit->second*(ll)(bit->second+1)/2;
					}
					else {
						if(it!=L[j].end() && it->first==x+1) {
								tot[j]-=it->second*(ll)(it->second+1)/2;
								tot[j]+=(it->second+1)*(ll)(it->second+2)/2;
								L[j][x]=1+it->second;
								L[j].erase(it);
						}
						else {
							tot[j]++;
							L[j][x]=1;
						}
					}
					
				}
				
			}
			//if(tot[j]>0) _P("%d %d %lld %d\n",i,j,tot[j],tot[j]<<j);
			t += tot[j]<<j;
		}
		cout << t << endl;
		A[x]=y;
	}
	
}

まとめ

(開始位置,長さ)の対の管理が面倒で似たようなコードが増えてしまった。