蓝桥杯2014年第五届真题-Log大侠 （C++代码）

解题思路:
注意事项:

参考代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1E5+2;
int _log[maxn],a[maxn];
int n,m,sum;
int p(int n)
{
	return !n ? 1 : p(n-1)<<1;
}
int main()
{
	cin >> n >> m;
	int l,r,l1,r1;
	l = 1;
	//打表maxn内的对数 O(n)
	for(int i=1; p(i-1)<=maxn; ++i)
	{
		r = p(i);
		for(int j=l; j<r&&j<=maxn; ++j)
		{
			_log[j] = i;
		}
		l = r;		
	}
	for(int i=1; i<=n; ++i)
	{
		cin >> a[i];
		sum += a[i];
	}
	for(int i=0; i<m; ++i)
	{
		cin >> l1 >> r1;
		for(int j=l1; j<=r1; ++j)
		{
			sum -= a[j];
			a[j] = _log[a[j]];
			sum += a[j];
		}
		cout << sum << endl;
	}
	return 0;
}