蓝桥杯2014年第五届真题-Log大侠 （C语言代码）普通模拟（比较简洁）

解题思路:

首先，这中写法是过不了原题的数据量的（有兴趣的可以看看我对本题的另一个题解，用线段树写的）;但是在我们的网站中普通模拟的方法是可以过的。

模拟虽然能过，但也有技巧进行优化代码，是代码更简洁。

因为每次都是查询的是整个区间的和ans，即[1，n]。

在读入数据时可以边读边求和；

在更改某一个位置上的数时，我们可以在总和ans中先把这个数减去；

在更改完毕后，再加回给总和ans即可。

例如：

3 3

5 4 6

1 2 

2 3

1 3

就拿样例来说吧：

f[1] = 5, f[2] = 4, f[2] = 6。

再读入数据的过程中记录了总和ans = 5  + 4 + 6 = 15;

更新区间[1，2]：ans = ans - f[1] = 10 , f[1] = log2(f[1]) + 1 = 3, ans = ans + f[1] = 13;

                          ans = ans - f[2]  = 7, f[2] = log2(f[2]) + 1 = 3, ans = ans + f[2] =10;

                           所以结果为10。

其他也是这样计算的。 自己跟着程序模拟一下就，显而易见了。

注意事项:

参考代码:

#include <cstdio>
#include <cmath>
const int N = 1e5 + 9;
int f[N];
int main() {
	long long ans = 0;
	int n, m, l, r;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &f[i]);
		ans += f[i];
	}
	for(int i = 0; i < m; ++i) {
		scanf("%d%d", &l, &r);
		for(int j = l; j <= r; ++j) {
			ans -= f[j];
			f[j] = floor(log2(f[j]) + 1);
			ans += f[j];
		}
		printf("%lld\n", ans);
	}
	return 0;
}