蓝桥杯2014年第五届真题-Log大侠 （C语言代码）线段树

解题思路:

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

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

                                                    对于 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
*/