简要题意
给你一个长度为 \(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\) 递归 \(k(x)\) 到 \(1\)。我们发现 \(k(x)\) 不太好求，于是我们反过来知道 \(x\) 求 \(k(x)\)：
\[\underbrace{2^{2^{2^\cdots}}}_{k(x)}=x
\]
下面我们把上式简写为 \(2@k(x)=x\)。
自然想到阿克曼函数 \(A(2,k(x))=2@k(x)=x\)。然后 \(k(x)\) 就是和 \(\alpha(x)\) 同阶了。
均摊时间复杂度分析：由于每一个元素最多被单点修改 \(\alpha(10^9)\approx 3\) 次。所以均摊时间复杂度是 \(O(3n)\)。
这就是无标记区间修改线段树。课后习题还有几道无标记区间修改线段树的题，供大家练习。
课后习题：
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;
}
（听说有人抄我的交题解，我劝你善良）
