原题链接：蓝桥杯2014年第五届真题-Log大侠
解题思路:
其实暴力就行了。
参考代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int SIZE = 100002;
LL table[SIZE], cnt;
struct tree {
LL value; int left, right;
} tree[SIZE << 4];
void buildtree(int root, int L, int R) {
tree[root].left = L; tree[root].right = R;
if (L == R) {
scanf("%lld", &tree[root].value);
if (tree[root].value == 1) {
tree[root].value = 2; cnt++;
}
return;
}
int mid = (L + R) >> 1;
buildtree(root << 1, L, mid);
buildtree(root << 1 | 1, mid + 1, R);
tree[root].value = tree[root << 1].value + tree[root << 1 | 1].value;
}
void updata(int root, int L, int R) {
if (tree[root].value == (tree[root].right - tree[root].left + 1) * 2)
return;
if (tree[root].left == tree[root].right) {
tree[root].value = table[tree[root].value];
return;
}
int mid = (tree[root].right + tree[root].left) >> 1;
if (L > mid)
updata(root << 1 | 1, L, R);
else if (R <= mid)
updata(root << 1, L, R);
else {
updata(root << 1, L, mid);
updata(root << 1 | 1, mid + 1, R);
}
tree[root].value = tree[root << 1].value + tree[root << 1 | 1].value;
}
int main() {
for (int pos = 1; pos < SIZE; pos++)
table[pos] = (int)(log2(pos) + 1);
int poi, que; scanf("%d%d", &poi, &que);
buildtree(1, 1, poi);
int L, R;
while (que--) {
scanf("%d%d", &L, &R);
updata(1, L, R);
printf("%lld\n", tree[1].value - cnt);
}
}0.0分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
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("%I64d\n", sum[1]); } return 0; } /* 对于 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 ; }