题解：P11894 「LAOI-9」Update

看到题目是区间修改，容易想到差分。但是题目要求对于每个 $a_i \leftarrow a_i + \lfloor \log_2 a_i \rfloor $。所以计算答案时要运用数学方法，对于当前这个 $a_i $，令 \(\lfloor \log_2 b_i\rfloor=\lfloor\log_2 a_i\rfloor+1\)，计算 \(a_i\) 与 \(b_i\) 之间的差值再除以 \(\lfloor\log_2 a_i\rfloor\)，如果差值要小于等于当前剩余的计算次数，就可以直接跳；否则就拿答案再加上剩余次数乘上 \(\lfloor\log_2 a_i\rfloor\)。时间复杂度是线性对数。

#include<bits/stdc++.h>
using namespace std;
const int N=1010101;
int n,m,a[N],sum[N],num,cnt[N];
int main(){scanf("%d%d",&n,&m);cnt[1]=1;for(int i=2;i<=25;i++)cnt[i]=cnt[i-1]*2;for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=m;i++){int l,r;scanf("%d%d",&l,&r);sum[l]++,sum[r+1]--;}for(int i=1;i<=n;i++){num+=sum[i];int ans=a[i],k;for(int j=1;j<=25;j++){if(cnt[j]>a[i]){k=j-1;break;}}for(int j=1;j<=num;){int w=log2(ans);int v=(cnt[k+1]-ans);if(w==0)break;else v=(v+w-1)/w;if(v<=num-j+1){j+=v;ans+=w*v;k++;}else{ans+=w*(num-j+1);j=num+1;}}printf("%d ",ans);}return 0;
}