CF679E Bear and Bad Powers of 42

(Updated: )
oi

Description

题目链接：CF679E

定义一个正整数是坏的，当且仅当它是 $42$ 的次幂，否则它是好的。

给定一个长度为 $n$ 的序列 $a_i$，保证初始时所有数都是好的。

有 $q$ 次操作，每次操作有三种可能：

  • 1 i 查询 $a_i$。
  • 2 l r x 将 $a_{l\dots 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#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%10+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;
}