【51Nod 1674】【算法马拉松 19A】区间的价值 V2

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1674
对区间分治，统计([l,r])中经过mid的区间的答案。
我的做法是从mid向右扫到r，统计出所有([mid,i],midleq i leq r)的and和or值。
然后发现这些and和or值有很多相同的，把相同的压在一起并记录sum，再从mid-1扫到l并暴力从mid向右统计答案。
事实上因为([mid,i],midleq i leq r)是连续的，所以压完后的个数是(O(2loga))的（a为(10^9)）。
这样时间复杂度是(O(nlognloga))。
听说有(O(nlog^2a))的二进制分组做法，好神啊orz

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int in() {
	int k = 0; char c = getchar();
	for (; c < '0' || c > '9'; c = getchar());
	for (; c >= '0' && c <= '9'; c = getchar())
		k = k * 10 + c - 48;
	return k;
}

const int N = 100003;
const ll p = 1000000007;
int n, a[N], AD[N], OR[N], len, sum[N], anow, onow;
ll ans = 0;

void solve(int l, int r) {
	if (l == r) return;
	int mid = (l + r + 1) >> 1;
	
	len = mid;
	AD[len] = OR[len] = a[mid];
	sum[len] = 1;
	for (int i = mid + 1; i <= r; ++i)
		if (((AD[len] & a[i]) != AD[len]) || ((OR[len] | a[i]) != OR[len])) {
			++len;
			AD[len] = AD[len - 1] & a[i];
			OR[len] = OR[len - 1] | a[i];
			sum[len] = 1;
		} else
			++sum[len];
	
	anow = onow = a[mid - 1];
	for (int i = mid - 1; i >= l; --i) {
		anow &= a[i];
		onow |= a[i];
		for (int j = mid; j <= len; ++j)
			ans = (ans + (ll) (anow & AD[j]) * (ll) (onow | OR[j]) % p * (ll) (sum[j]) % p) % p;
	}
	
	solve(l, mid - 1); solve(mid, r);
}

int main() {
	n = in();
	for (int i = 1; i <= n; ++i)
		a[i] = in(), ans = (ans + 1ll * a[i] * a[i]) % p;
	
	solve(1, n);
	printf("%d
", (int) ans);
	return 0;
}