P4145 花神游历各国

问题

P4145 上帝造题的七分钟 2 / 花神游历各国
维护一个正整数序列，支持把区间内每个数替换为其平方根下取整，并查询区间和。

数据规模：$n,m\le 10^5$，初值不超过 $10^{12}$。

区间开方 + 区间和查询，显然就是线段树的板子。

可是区间开方这个操作对区间和是不封闭的，例如区间为 $4,9$ 时，先求和再开方是 $3$，而先开方再求和是 $5$。

所以我们没法在递归中提前操作区间，每一次区间修改都必须落实到叶子节点，但这样的线段树不就退化了吗？要你有何用？

接着我们会发现，即便初值达到 $10^{12}$，一个数被有效开方的次数也很少，而 $\sqrt{1}=1$，所以值已经不超过 $1$ 的节点可以直接跳过。

也就是说，我们可以同时维护一个区间最大值，如果区间最大值已经是 $1$ 了，就说明这个区间不需要再执行开方操作了，因为此时操作对答案是不影响的。

▶

P4145

struct SegTree {
/* ================================================== */
struct Node { 
    int l, r; 
    ll sum;
    ll mx;
} tr[maxn << 2];

void push_up( int u ) {
    tr[u].sum = tr[ls].sum + tr[rs].sum;
    tr[u].mx = max( tr[ls].mx, tr[rs].mx );
}

void build( int u, int l, int r, ll val[] ) {
    tr[u] = { l, r, 0, 0 };
    if( l == r ) {
        tr[u].sum = val[l];
        tr[u].mx = val[l];
        return ;
    }
    int mid = ( l + r ) >> 1;
    build( ls, l, mid, val );
    build( rs, mid + 1, r, val );
    push_up( u );
}

void upd( int u, int l, int r ) {
    if( tr[u].mx <= 1 ) return ;
    if( tr[u].l == tr[u].r ) {
        tr[u].sum = sqrt( tr[u].sum );
        tr[u].mx = tr[u].sum;
        return ;
    }
    int mid = ( tr[u].l + tr[u].r ) >> 1;
    if( l <= mid ) upd( ls, l, r );
    if( mid < r ) upd( rs, l, r );
    push_up( u );
}

ll ask( int u, int l, int r ) {
    if( l <= tr[u].l && tr[u].r <= r ) return tr[u].sum;
    int mid = ( tr[u].l + tr[u].r ) >> 1;
    ll res = 0;
    if( l <= mid ) res += ask( ls, l, r );
    if( mid < r ) res += ask( rs, l, r );
    return res;
}
/* ================================================== */
} seg;

ll a[maxn];

void solve( ) {
    int n = read( );
    for( int i = 1; i <= n; ++ i ) a[i] = read( );
    seg.build( 1, 1, n, a );

    int m = read( );
    for( int i = 1; i <= m; ++ i ) {
        int opt = read( );
        int l = read( ), r = read( );
        if( l > r ) swap( l , r );
        if( opt == 0 ) {
            seg.upd( 1, l, r );
        } else {
            cout << seg.ask( 1, l, r ) << '\n';
        }
    }
}

记录

• 归属：线段树区间剪枝、普通 Lazy 的边界。
• 新增：修改难以整段执行时，可以寻找“已经稳定”的区间信息，并利用操作快速收敛控制总递归量。
• 分类：保留；核心增量是操作收敛与稳定状态剪枝，而不是 Lazy 实现。