Codeforces 250D 線段樹：區間取模、區間求和、單點修改

題目操作

1. 區間求和 sum(l,r)
2. 區間取模 a[i] %= x (l≤i≤r)
3. 單點賦值 a[k] = x

關鍵優化：取模剪枝

線段樹節點維護 max 和 sum。若節點 max < x，整段無需取模直接返回。否則遞歸到葉子逐個取模。因為取模後值嚴格變小，每個元素被修改次數極少（O(log MAX)），總複雜度近似 O((n+q) log n)。

線段樹結構

struct Node { int l,r; long long sum, maxv; } tree[4*MAXN];
void push_up(int id) {
    tree[id].sum = tree[id<<1].sum + tree[id<<1|1].sum;
    tree[id].maxv = max(tree[id<<1].maxv, tree[id<<1|1].maxv);
}
void build(int l,int r,int id) { ... }
long long query(int l,int r,int id) { ... }
void update_mod(int l,int r,long long x,int id) {
    if (tree[id].maxv < x) return; // 剪枝
    if (tree[id].l == tree[id].r) {
        tree[id].sum %= x; tree[id].maxv = tree[id].sum; return;
    }
    int mid = (tree[id].l + tree[id].r) >> 1;
    if (r <= mid) update_mod(l,r,x,id<<1);
    else if (l > mid) update_mod(l,r,x,id<<1|1);
    else { update_mod(l,mid,x,id<<1); update_mod(mid+1,r,x,id<<1|1); }
    push_up(id);
}
void update_point(int pos,long long val,int id) { ... }

複雜度分析

• 單點修改、區間求和：標準 O(log n)。
• 區間取模：攤銷 O(log n log MAX)，實際極快。