【Codeforces 679E】Bear and Bad Powers of 42
线段树，均摊分析
题目大意：
给定一个数列，有三种操作：
- 单点查询。
- 区间赋值。
- 区间加。 如果执行该操作后这个区间内存在 $42$ 的整数次方，则重复执行这个操作直到不存在。
题解：
在 $64$ 位整数范围内一共有 $12$ 个 $42$ 的整数次方。
考虑用线段树维护区间信息，每个数记录一个 $\Delta$ 表示这个数减去大于等于它的最小的 $42$ 的整数次方。区间维护最大的 $\Delta$，其实是绝对值最小的。
考虑进行区间加的操作。我们对一个完整的区间执行加法操作时，如果 $\Delta$ 等于 $0$，那么打标记表示还需要重复执行。如果 $\Delta$ 小于 $0$，那么这个区间没有影响。如果 $\Delta$ 大于 $0$，则我们并不知道这个区间内是否有数会产生冲突。
考虑到每个数都有不超过 $12$ 个大于等于它的 $42$ 的整数次方，而当区间的 $\Delta>0$ 时，区间内必然存在一个数，大于等于它的 $42$ 的整数次方会减少一个，这种减少的操作最多会执行 $12$ 次。
那么当区间的 $\Delta>0$ 时，我们线段树继续向下递归修改，每次定位到所有 $\Delta>0$ 的数，并将其 $\Delta$ 调整至非正。
分析这样复杂度的正确性。每个数最多被减 $12$ 次，之后就不会访问至该个结点。访问一个结点的复杂度为 $O(\log n)$，那么修改它的最大复杂度就是 $O(12\log n)$。$n$ 个数总共的复杂度就是 $O(12n\log n)$。
所以区间加的复杂度是和它重复执行的次数无关的。
考虑区间赋值，它会产生一个问题，最坏是会将 $O(n)$ 个数的修改次数变回 $12$，导致上面的复杂度出现问题。
不过由于区间赋值，最多使区间内本质不同的数增加 $1$，因此在区间加操作中，如果一个区间的数都相同，那么把它当做一个数进行操作即可。那么一次区间赋值就只会增加 $O(12\log n)$ 的复杂度了。
单点修改操作直接查询即可。
总的时间复杂度为 $O(12(n+q)\log n)$。
Code：
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+5;
typedef long long LL;
struct data{
LL ass,add,dlt;
}d[N<<2];
int n,m;
bool flag;
const LL fd[]={1,42,1764,74088,3111696,130691232,5489031744,230539333248,9682651996416,406671383849472,17080198121677824,717368321110468608};
inline LL get_(LL x){return*lower_bound(fd,fd+12,x);}
void build(int l,int r,int o){
if(l==r){
cin>>d[o].ass;
d[o].add=0;
d[o].dlt=d[o].ass-get_(d[o].ass);
}else{
const int mid=l+r>>1;
build(l,mid,o<<1),build(mid+1,r,o<<1|1);
d[o].dlt=max(d[o<<1].dlt,d[o<<1|1].dlt);
}
}
inline void pushdown(int o){
if(d[o].ass){
d[o].ass+=d[o].add;
d[o].add=0;
d[o<<1].ass=d[o<<1|1].ass=d[o].ass;
d[o<<1].add=d[o<<1|1].add=0;
d[o<<1].dlt=d[o<<1|1].dlt=d[o].dlt;
d[o].ass=0;
}
if(d[o].add){
d[o<<1].add+=d[o].add,d[o<<1|1].add+=d[o].add;
d[o<<1].dlt+=d[o].add,d[o<<1|1].dlt+=d[o].add;
d[o].add=0;
}
}
void query(int l,int r,int o,const int&pos){
if(l==r||d[o].ass)cout<<d[o].ass+d[o].add<<'\n';else{
pushdown(o);
const int mid=l+r>>1;
if(pos<=mid)query(l,mid,o<<1,pos);else query(mid+1,r,o<<1|1,pos);
}
}
void assign(int l,int r,int o,const int&L,const int&R,const int&x,const LL&y){
if(L<=l&&r<=R)d[o]=(data){x,0,x-y};else{
pushdown(o);
const int mid=l+r>>1;
if(L<=mid)assign(l,mid,o<<1,L,R,x,y);
if(mid<R)assign(mid+1,r,o<<1|1,L,R,x,y);
d[o].dlt=max(d[o<<1].dlt,d[o<<1|1].dlt);
}
}
void modify(int l,int r,int o,const int&L,const int&R,const int&c){
if(L<=l&&r<=R){
d[o].add+=c,d[o].dlt+=c;
if(d[o].dlt==0)flag=1;
if(d[o].dlt<=0)return;else d[o].dlt-=c,d[o].add-=c;
}
if(d[o].ass&&L<=l&&r<=R){
d[o].ass+=d[o].add+c,d[o].add=0;
d[o].dlt=d[o].ass-get_(d[o].ass);
if(d[o].dlt==0)flag=1;
return;
}
pushdown(o);
const int mid=l+r>>1;
if(L<=mid)modify(l,mid,o<<1,L,R,c);
if(mid<R)modify(mid+1,r,o<<1|1,L,R,c);
d[o].dlt=max(d[o<<1].dlt,d[o<<1|1].dlt);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
build(1,n,1);
while(m--){
int op;
cin>>op;
if(op==1){
int x;
cin>>x;
query(1,n,1,x);
}
if(op==2){
int l,r,x;
cin>>l>>r>>x;
assign(1,n,1,l,r,x,get_(x));
}
if(op==3){
int l,r,c;
cin>>l>>r>>c;
do{
//cout<<l<<' '<<r<<' '<<c<<'\n';
flag=0;
modify(1,n,1,l,r,c);
}while(flag);
}
cout.flush();
}
return 0;
}