本文主要是介绍蓝桥杯 2014 C++B(5) Log大侠 线段树 区间修改，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
atm参加了速算训练班，经过刻苦修炼，对以2为底的对数算得飞快，人称Log大侠。 一天，Log大侠的好友 drd有一些整数序列需要变换，Log大侠正好施展法力… 变换的规则是： 对其某个子序列的每个整数变为: [log_2 (x) + 1] 其中[] 表示向下取整，就是对每个数字求以2为底的对数，然后取下整。 例如对序列 3 4 2 操作一次后，这个序列会变成 2 3 2。drd需要知道，每次这样操作后，序列的和是多少。
【输入格式】 第一行两个正整数 n m 。 第二行 n 个数，表示整数序列，都是正数。 接下来 m 行，每行两个数 L R 表示 atm这次操作的是区间 [L, R]，数列序号从1开始。
【输出格式】 输出 m 行，依次表示 atm 每做完一个操作后，整个序列的和。
例如，
输入：
3 3
5 6 4
1 2
2 3
1 3
程序应该输出：
10
8
6
【数据范围】
对于 30% 的数据， n, m <= 10^3
对于 100% 的数据， n, m <= 10^5
资源约定： 峰值内存消耗 < 256M
CPU消耗 < 1000ms 请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 注意: main函数需要返回0 注意: 只使用ANSI C/ANSI C++
标准，不要调用依赖于编译环境或操作系统的特殊函数。 注意: 所有依赖的函数必须明确地在源文件中 #include ，
不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#define lson p << 1
#define rson p << 1 | 1
using namespace std;
typedef long long LL;const int MAXN = 100010;
int f[MAXN];
LL tree[MAXN<<2]; //注意开long long
int n;void build(int p, int l, int r){if(l == r){scanf("%d",&tree[p]);//省去了a数组return;}int m = (l+r)>>1; build(p<<1,l,m);build(p<<1|1,m+1,r);tree[p] = tree[lson] + tree[rson];} void updateSome(int p, int l, int r, int tl, int tr){if(r < tl || l > tr)return;if(l == r){//其实这个比较费时 ，但是 这题不知道怎么进行类似懒惰标记的优化 只能在最底层进行更新了tree[p] = f[tree[p]];//这里修改值return;}int m = (l+r) >> 1;if(tl <= m)updateSome(lson,l,m,tl,tr);if(tr > m)updateSome(rson,m+1,r,tl,tr);tree[p] = tree[lson] + tree[rson];}int main()
{int m;scanf("%d%d", &n, &m);build(1, 1, n); for(int i = 1; i <= MAXN; i++)f[i] = (int)(log2(i) + 1);//这个数组也是个技巧while(m--){int l, r;scanf("%d%d", &l, &r);updateSome(1, 1, n, l, r);printf("%I64d\n", tree[1]);}return 0;
}这篇关于蓝桥杯 2014 C++B(5) Log大侠 线段树 区间修改的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
