CF679E Bear and Bad Powers of 42
Description
题目链接：CF679E
定义一个正整数是坏的，当且仅当它是 42 的次幂，否则它是好的。
给定一个长度为 n 的序列 a_i，保证初始时所有数都是好的。
有 q 次操作，每次操作有三种可能：
- 1 i 查询 a_i。
- 2 l r x 将 a_{ldots r} 赋值为一个好的数 x。
- 3 l r x 将 a_{l dots r} 都加上 x，重复这一过程直到所有数都变好。
n,q le 10^5,a_i,x le 10^9。
Solution
线段树
考虑对于每个点，维护 d 表示距离该点最近的好数。
每次操作 3 直接暴力修改即可。
分析下这样做的复杂度：
由于在 10^{18} 范围内，42 的幂次只有 12 个，也就是说每次操作三，最多修改 12 次，显然这个复杂度是可以接受的。
Code
代码语言：javascript复制#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI) fread(FI,1,FS,stdin),FA==FB)?EOF:*FA )
#define pc(c) (FC==FE&&(clear(),0),*FC =c)
int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO FS;
I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3) (x<<1) (oc&15),isdigit(oc=tc()));}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
Tp I void writeln(Ty x) {W(OS[ OT]=x 48,x/=10);W(OT) pc(OS[OT--]);pc('n');}
}using namespace FastIO;
Cn int N=1e5 10;
int n,m,a[N];
LL pw[15];
#define LW(x) (lower_bound(pw 1,pw 12,x)-pw)
class SegmentTree{
private:
struct node{LL d,lg,tgA,tgC;}T[N<<2];
#define mid (l r>>1)
#define PT CI x=1,CI l=1,CI r=n
#define LT x<<1,l,mid
#define RT x<<11,mid 1,r
#define PU(x) (T[x].d=min(T[x<<1].d,T[x<<11].d))
#define PD(x) (T[x].tgC&&(T[x<<1].lg=LW(T[x].tgC),T[x<<1].d=pw[T[x<<1].lg]-T[x].tgC,T[x<<1].tgC=T[x].tgC,T[x<<1].tgA=0,
T[x<<11].lg=LW(T[x].tgC),T[x<<11].d=pw[T[x<<11].lg]-T[x].tgC,T[x<<11].tgC=T[x].tgC,T[x<<11].tgA=0,T[x].tgC=0),
T[x].tgA&&(T[x<<1].tgC?T[x<<1].tgC =T[x].tgA:T[x<<1].tgA =T[x].tgA,T[x<<1].d-=T[x].tgA,T[x<<11].tgC?T[x<<11].tgC =T[x].tgA:T[x<<11].tgA =T[x].tgA,T[x<<11].d-=T[x].tgA,T[x].tgA=0))
I void AP(CI x,LL v){T[x].lg=LW(v),T[x].d=pw[T[x].lg]-v;}
public:
I void B(PT){
if(l==r) return AP(x,a[l]),void();
B(LT),B(RT),PU(x);
}
I LL Q(CI p,PT){
if(l==r) return pw[T[x].lg]-T[x].d;
return PD(x),p<=mid?Q(p,LT):Q(p,RT);
}
I LL QD(PT){
if(T[x].d>=0) return T[x].d;
if(l==r) return AP(x,pw[T[x].lg]-T[x].d),T[x].d;
return PD(x),T[x].d=min(QD(LT),QD(RT));
}
I void A(CI L,CI R,LL v,PT){
if(L<=l&&r<=R) return T[x].tgC?T[x].tgC =v:T[x].tgA =v,T[x].d-=v,void();
PD(x),L<=mid&&(A(L,R,v,LT),0),R>mid&&(A(L,R,v,RT),0),PU(x);
}
I void C(CI L,CI R,LL v,PT){
if(L<=l&&r<=R) return T[x].lg=LW(v),T[x].d=pw[T[x].lg]-v,T[x].tgC=v,T[x].tgA=0,void();
PD(x),L<=mid&&(C(L,R,v,LT),0),R>mid&&(C(L,R,v,RT),0),PU(x);
}
}T;
I void UA(CI l,CI r,CI x){T.A(l,r,x);W(!T.QD()) T.A(l,r,x);}
int main(){
RI i,o,l,r;LL x;for(pw[0]=1,i=1;i<=11;i ) pw[i]=pw[i-1]*42;for(read(n,m),i=1;i<=n;i ) read(a[i]);
for(T.B();m--;) read(o,l),o<2?writeln(T.Q(l)):(read(r,x),o&1?UA(l,r,x):T.C(l,r,x));return clear(),0;
}
