Codeforces 400(#234 Div2 only) E Inna and Binary Logic

問題

Innaは整数の配列a[i]を使って次のようなことをする。

a[i]を一列に全部書く。これをa1[i]とする。
次に、n - 1個の(a1[i] and a1[i + 1])を書く。（ただしandはビット演算のand）
これをa2[i]とする。
次にn - 2個の(a2[i] and a2[i + 1])を書く……
を数字が最後の一つになるまで繰り替えす。

Innaが書いた全ての数の和をsumとする。

このとき次のクエリm個に答えよ。
a[i]のu[i]番目の数をv[i]に変更する。
この数列でInnaが数字を最初から書いたときのsumを出力せよ。
クエリで変更されたa[i]は、次のクエリにもそのまま残るものとする。

制約条件

n, m≦10^5
0≦a[i]≦10^5

方針

ビット演算のandなのでビットごとに独立に考えていい。
クエリを全部読んでおいて、ビットごとにクエリを処理して、
i番目のビットのせいでInnaが書いた数字の和を答えに足していけばよい。

今、ビット毎に独立に考えて操作をするので、a[i]は0, 1だけからなっている。
1がn個並んでいると、Innaはn + (n - 1) + (n - 2) + = n * (n + 1) / 2個の1を書くことになる。
なので、数字を変更すると、連続する1の個数が変化するので、
その分だけ上の式にしたがってsumを変更してやればよい。

連続する1は、binary indexed treeに0の場所を覚えさせておけば、
O(log n)で検索できるが、binary indexed treeを二分探索するO((log n) ^ 2)とかいう頭の悪いことをやってもギリギリ通った。

ソースコード

const int MX = 100010;
int n, m, a[MX], cur[MX];
int u[MX], v[MX];
ll ans[MX];

int bit[MX];
int sum(int i){
	int res = 0;
	for(++i ; i; i -= i & -i) res += bit[i];
	return res;
}
void add(int i, int x){
	for(++i ; i < MX; i += i & -i) bit[i] += x;
}

void change_bit(ll &ans, int pos, int on, int bit_pos){
	
	int left, right;
	int lo = pos, hi = n, mid;
	
	while(lo + 1 < hi){
		mid = (lo + hi) / 2;
		
		if(sum(mid) - sum(pos) != mid - pos) hi = mid;
		else lo = mid;
	}
	right = lo - pos;
	
	lo = -1; hi = pos;
	
	while(lo + 1 < hi){
		mid = (lo + hi) / 2;
		
		if(sum(pos - 1) - sum(mid - 1) != pos - mid) lo = mid;
		else hi = mid;
	}
	left = pos - hi;
	
	if(on){
		ans -= (1ll << bit_pos) * (left + 1) * left / 2;
		ans -= (1ll << bit_pos) * (right + 1) * right / 2;
		ans += (1ll << bit_pos) * (left + right + 2) * (left + right + 1) / 2;
		
		add(pos, 1);
	}
	else{
		ans += (1ll << bit_pos) * (left + 1) * left / 2;
		ans += (1ll << bit_pos) * (right + 1) * right / 2;
		ans -= (1ll << bit_pos) * (left + right + 2) * (left + right + 1) / 2;
		
		add(pos, -1);
	}
}


int main(){
	cin >> n >> m;
	rep(i, n) cin >> a[i];
	rep(i, m){
		cin >> u[i] >> v[i];
		u[i]--;
	}
	
	rep(pos, 32){
		memset(bit, 0, sizeof(bit));
		ll bit_ans = 0;
		
		rep(i, n) if(a[i] >> pos & 1) change_bit(bit_ans, i, 1, pos);
		rep(i, m){
			int prev = sum(u[i]) - sum(u[i] - 1);
			int next = v[i] >> pos & 1;
			
			if(prev != next) change_bit(bit_ans, u[i], next, pos);
			ans[i] += bit_ans;
		}
	}
	
	rep(i, m) cout << ans[i] << endl;
	
	return 0;
}