| 等 级 | |
| 排 名 | 18 |
| 经 验 | 20461 |
| 参赛次数 | 13 |
| 文章发表 | 127 |
| 年 龄 | 3 |
| 在职情况 | 学生 |
| 学 校 | 贺州学院 |
| 专 业 |
自我简介：
TA的其他文章
原题链接：蓝桥杯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 人评分
评论区
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
*/
2019-05-12 21:52:53
#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 ;
}
2019-05-12 21:52:08
兄弟 可以帮我看看为什么输出超限了吗
2019-05-12 21:51:54
- «
- 1
- »