CF679E Bear and Bad Powers of 42

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

#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<<1|1,mid+1,r
        #define PU(x) (T[x].d=min(T[x<<1].d,T[x<<1|1].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<<1|1].lg=LW(T[x].tgC),T[x<<1|1].d=pw[T[x<<1|1].lg]-T[x].tgC,T[x<<1|1].tgC=T[x].tgC,T[x<<1|1].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<<1|1].tgC?T[x<<1|1].tgC+=T[x].tgA:T[x<<1|1].tgA+=T[x].tgA,T[x<<1|1].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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇