咖啡


私信TA

用户名:Tianxn

访问量:13796

签 名:

人一我百,人十我万

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

  自我简介:

解题思路:

                区间更新,区间查询------》线段树


                普通方法能过,但是原题的数据量描述如下:

                                                    对于 30% 的数据, n, m <= 10^3
                                                    对于 100% 的数据, n, m <= 10^5


                  线段树的东西,这里就赘述了,大家还是看博客博客比较好


注意事项:    注意边界


参考代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

struct Node{
	int L, R;
	int mid() { return L + R >> 1; }
}tree[N << 2];

ll sum[N << 2], table[N << 2];

void PushUp(int ri) {
	sum[ri] = sum[ri << 1] + sum[ri << 1 | 1];
}

void BuildTree(int ri, int L, int R) {
	tree[ri] = { L, R };
	if(L == R) {
		scanf("%d", &sum[ri]);
		return ;
	}
	int m = tree[ri].mid();
	BuildTree(ri << 1, L, m);
	BuildTree(ri << 1 | 1, m + 1, R);
	PushUp(ri);
}

void UpdateTree(int ri, int L, int R) {
	if(tree[ri].L == tree[ri].R) {
		sum[ri] = table[sum[ri]];
		return ;
	}
	int m = tree[ri].mid();
	if(R <= m) UpdateTree(ri << 1, L, R);
	else if(L > m) UpdateTree(ri << 1 | 1, L, R);
	else {
		UpdateTree(ri << 1, L, m);
		UpdateTree(ri << 1 | 1, m + 1, R);
	}
	PushUp(ri);
}

int main() { 
	int n, m;
	for(int i = 1; i < (N << 2); ++i) table[i] = (int)floor(log2(i)) + 1;
	scanf("%d%d", &n, &m);
	BuildTree(1, 1, n);
	int l, r;
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d", &l, &r);
		UpdateTree(1, l, r);
		printf("%lld\n", sum[1]);
	}
	return 0;
}

/*
对于 30% 的数据, n, m <= 10^3
对于 100% 的数据, n, m <= 10^5
*/


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

  评论区