简要题意
给你一个长度为 \(n\) 的正整数序列 \(a\)，有 \(m\) 个询问，每一个询问给出一个区间 \([l,r]\)。定义函数 \(f(x)=\lfloor\log_{2}(x)+1\rfloor\)。将 \([l,r]\) 的所有元素 \(a_p\) 修改为 \(f(a_p)\)。然后输出序列 \(a\) 的全局和。
对于 \(100\%\) 的数据，\(1 \leq n,m \le 10^5,1 \leq a_i \leq 10^9\)。
思路
前置知识：线段树。
这一道题是无标记区间修改线段树（我自己取得名字）的模板题。
这道题如果使用普通的线段树区间修改（打标记法），无论是标记下传还是标记永久化，都有一个问题：如何实现区间更新？也就是说知道 \(\sum_{i=l}^{r}{a_i}\)，如何求 \(\sum_{i=l}^{r}{f(a_i)}\)？
这不是不好求，是不能求。
那我们考虑回归暴力。暴力思路很简单，在线段树上找到 \([l,r]\) 的所有元素，一一单点更新即可。
接下来见证奇迹的时刻：首先，易证当 \(x=1\) 或 \(x=2\) 时，\(f(x)=x\)。
那我们只需要再维护一个区间最大值，如果线段树遍历到的区间最大值 \(\leq 2\)，那么直接不用更新了，返回。
这样子似乎复杂度没变？不不不，复杂度已经变成了 \(O(\alpha(a_i)n)\)！
这里给出简单证明过程：首先，\(f(i)\approx \log_{2}(i)\)，也就是说，单次 \(f(i)\) 时缩减到了 \(\log(i)\) 级。
然后就是计算，发现 \(x=10^{9}\) 只需要 \(3\) 次！计算次数大致与反 Ackermann 函数同阶（有兴趣的同学自己去证）。
然后理论上每一个元素只会被单点修改 \(3\) 次！所以就是 \(O(\alpha(a_i)n)\) 了！
这就是无标记区间修改线段树。课后习题还有几道无标记区间修改线段树的题，供大家练习。
课后习题：
- P4145 上帝造题的七分钟 2 / 花神游历各国
- mod 板线段树（学长出的线段树神仙题）
代码
#include <bits/stdc++.h>
#define int long long
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
using namespace std;
int n,m;
const int N = 1e5+5;
struct node{
int maxt,sumt;
} t[N<<2];
inline void pushup(int i){
t[i].maxt=max(t[ls].maxt,t[rs].maxt);
t[i].sumt=t[ls].sumt+t[rs].sumt;
}
void build(int i,int l,int r){
if(l==r){
cin>>t[i].maxt;
t[i].sumt=t[i].maxt;
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(i);
}
inline int magic(int x){
return floor(log(x)/log(2)+1);
}
void update(int ql,int qr,int i,int l,int r){
if(t[i].maxt<=2){
return;
}
if(l==r){
t[i].sumt=t[i].maxt=magic(t[i].sumt);
return;
}
if(ql<=mid){
update(ql,qr,ls,l,mid);
}
if(qr>mid){
update(ql,qr,rs,mid+1,r);
}
pushup(i);
}
int query(int ql,int qr,int i,int l,int r){
if(ql<=l&&r<=qr){
return t[i].sumt;
}
int ret=0;
if(ql<=mid){
ret += query(ql,qr,ls,l,mid);
}
if(qr>mid){
ret += query(ql,qr,rs,mid+1,r);
}
return ret;
}
signed main(){
cin>>n>>m;
build(1,1,n);
while(m--){
int l,r;
cin>>l>>r;
update(l,r,1,1,n);
cout<<query(1,n,1,1,n)<<'\n';
}
return 0;
}
原文地址：http://www.cnblogs.com/zheyuanxie/p/p8618.html
