咖啡


私信TA

用户名:Tianxn

访问量:13797

签 名:

人一我百,人十我万

等  级
排  名 14
经  验 8591
参赛次数 1
文章发表 124
年  龄 22
在职情况
学  校 西安航空学院
专  业 软件工程

  自我简介:

解题思路:

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

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

因为每次都是查询的是整个区间的和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;
}


C语言网提供「C语言、C++、算法竞赛」在线课程,全部由研发工程师或ACM金牌退役选手亲自授课,以视频+配套题目的学练同步模式教学,强化动手,并提供增值服务!

  评论区