HDU 4027 Can you answer these queries?：線段樹區間開方 + 標記剪枝 (覆蓋標記)

問題

序列長度 n ≤ 10^5，兩種操作：
0 a b：區間 [a,b] 每個數開平方 (取整)
1 a b：查詢區間和
數據保證總和 < 2^63。

關鍵觀察：開方快速收斂

對任意 64 位整數，連續開方 ≤ 6 次即變為 0 或 1，之後不再變化。因此每個元素被修改次數極少 (≤ 6)。可用線段樹維護區間和，並打一個 cover 標記：若節點區間內所有值均為 0/1，則 cover=true，後續開方操作直接跳過該節點。

線段樹節點

struct Node {
    int l, r;
    long long sum;
    bool cover; // 全為 0/1
};

核心操作

建樹

void build(int l, int r, int o=0) {
    node[o].l=l; node[o].r=r; node[o].cover=false;
    if (l==r) {
        scanf("%lld",&node[o].sum);
        if (node[o].sum<=1) node[o].cover=true;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,lson); build(mid+1,r,rson);
    pushup(o);
}

區間開方 (單點下推)

void update(int l, int r, int o=0) {
    if (node[o].cover) return; // 已穩定
    if (node[o].l==node[o].r) {
        node[o].sum = sqrt(node[o].sum);
        if (node[o].sum<=1) node[o].cover=true;
        return;
    }
    int mid=(node[o].l+node[o].r)>>1;
    if (l<=mid) update(l,r,lson);
    if (r>mid) update(l,r,rson);
    pushup(o);
}

查詢

long long query(int l, int r, int o=0) {
    if (node[o].l>=l && node[o].r<=r) return node[o].sum;
    int mid=(node[o].l+node[o].r)>>1;
    long long ans=0;
    if (l<=mid) ans+=query(l,r,lson);
    if (r>mid) ans+=query(l,r,rson);
    return ans;
}

複雜度分析

• 每個葉子最多被更新 6 次 → 總更新次數 ≤ 6n。
• 每次更新/查詢 O(log n) → 總時間 O((n+q) log n)，極易通過。