帮帮孩子，TLE on #9

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define i128 __int128
#define ull unsigned long long
#define rep(i,X,Y) for (int i=(X);i<=(Y);++i)
#define per(i,X,Y) for (int i=(X);i>=(Y);--i)
#define FIO(X) freopen(#X".in","r",stdin),freopen(#X".out","w",stdout);
#define mem(X,val) memset(X,val,sizeof(X));
#define pii pair<int,int>
#define pll pair<long long,long long>
#define fi first
#define se second
#define ALL(X) X.begin(),X.end()
#define pb push_back
#define eb emplace_back
const bool MUL=false;

const int N=5e5+10;

int n,q; ll a[N];

struct SEG {
    ll t[N<<2],f[N<<2],g[N<<2];
    i128 s[N<<2];
    void pushup(int u) {
        int ls=u<<1,rs=u<<1|1;
        s[u]=s[ls]+s[rs];
        f[u]=min(f[ls],f[rs]); f[u]=min(f[u],(ll)(g[ls]^g[rs]?__builtin_ctz(g[ls]^g[rs]):50));
        g[u]=g[ls]&((1ll<<f[u])-1);
    }
    void build(int u,int l,int r) {
        t[u]=0;
        if(l==r) {
            s[u]=g[u]=a[l]; f[u]=50;
            return;
        }
        int mid=l+r>>1,ls=u<<1,rs=u<<1|1;
        build(ls,l,mid); build(rs,mid+1,r);
        pushup(u);
    }
    void addt(int u,int l,int r,ll k) {
        s[u]+=(r-l+1)*k; t[u]+=k; g[u]=(g[u]+k)&((1ll<<f[u])-1);
    }
    void pushdown(int u,int l,int r) {
        int mid=l+r>>1,ls=u<<1,rs=u<<1|1;
        if(t[u]) {
            addt(ls,l,mid,t[u]); addt(rs,mid+1,r,t[u]);
            t[u]=0;
        }
    }
    void modify1(int u,int l,int r,int x,int y,ll k) {
        if(l>=x&&r<=y) {
            addt(u,l,r,k);
            return;
        }
        pushdown(u,l,r);
        int mid=l+r>>1,ls=u<<1,rs=u<<1|1;
        if(x<=mid) modify1(ls,l,mid,x,y,k);
        if(y>mid) modify1(rs,mid+1,r,x,y,k);
        pushup(u);
    }
    void modify2(int u,int l,int r,int x,int y) {
        // cerr<<u<<' '<<l<<' '<<r<<' '<<x<<' '<< y<<"  "<<g[u]<<'\n';
        if(l>=x&&r<=y) {
            if(g[u]) {
                addt(u,l,r,(g[u]&-g[u]));
                return;
            }
        }
        pushdown(u,l,r);
        int mid=l+r>>1,ls=u<<1,rs=u<<1|1;
        if(x<=mid) modify2(ls,l,mid,x,y);
        if(y>mid) modify2(rs,mid+1,r,x,y);
        pushup(u);
    }
    i128 query(int u,int l,int r,int x,int y) {
        if(l>=x&&r<=y) return s[u];
        pushdown(u,l,r);
        int mid=l+r>>1,ls=u<<1,rs=u<<1|1;
        if(y<=mid) return query(ls,l,mid,x,y);
        if(x>mid) return query(rs,mid+1,r,x,y);
        return query(ls,l,mid,x,y)+query(rs,mid+1,r,x,y);
    }
} tr;

template<typename T>
void write(T x) {if(x) {write(x/10); putchar('0'+x%10);}}

int Solve() {
    cin>>n>>q;
    rep(i,1,n) cin>>a[i];
    tr.build(1,1,n);
    while(q--) {
        int op,l,r; cin>>op>>l>>r;
        if(op==1) {
            tr.modify2(1,1,n,l,r);
        } else if(op==2) {
            tr.modify1(1,1,n,l,r,1);
        } else {
            // cerr<< "  "<<(ll)tr.query(1,1,n,l,r)<<'\n';
            write(tr.query(1,1,n,l,r));
            putchar('\n');
        }
    }
    return 0;
}
int main() {
    ios::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr);
    // FIO(rplrprq);
    int T=1; if(MUL) cin>>T; while (T--) { Solve(); }
    return 0;
}