咖啡


私信TA

用户名:Tianxn

访问量:128018

签 名:

十年OI一场空,不开LL见祖宗。

等  级
排  名 8
经  验 26039
参赛次数 10
文章发表 197
年  龄 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
*/


 

0.0分

2 人评分

  评论区

这和模拟不是差不多
2022-02-18 12:39:37
  • «
  • 1
  • »