题解：P13979 数列分块入门 4

zyzxzhangyi · 2025-09-07 00:37:31 · 题解

题目传送门

思路

和这道题一样，是一道线段树的板子题：区间修改，区间查询。

区间修改时使用懒标记，如下：

void change(long long i, long long l, long long r, long long x, long long y, long long v){
    if(x <= l && r <= y){
        add(i, l, r, v);
        return ;
    }
    long long mid = l + r >> 1;
    pushdown(i, l, r);
    if(x <= mid) change(i << 1, l, mid, x, y, v);
    if(y > mid) change(i << 1 | 1, mid + 1, r, x, y, v);
    tree[i] = tree[i << 1] + tree[i << 1 | 1];
}

区间查询时要记得放下标记，如下：

long long query(long long i, long long l, long long r, long long x, long long y){
    if(x <= l && r <= y) return tree[i];
    long long sum = 0, mid = l + r >> 1;
    pushdown(i, l, r);
    if(x <= mid) sum += query(i << 1, l, mid, x, y);
    if(y > mid) sum += query(i << 1 | 1, mid + 1, r, x, y);
    return sum;
}

输出答案时的取模必须是非负的，处理如下：

cout << (query(1, 1, n, x, y) % z + z) % z << "\n";

代码

#include <bits/stdc++.h>
using namespace std;

long long n, m, x, y, z, a[300005], tree[1200005], lazy[1200005];

void build(long long i, long long l, long long r){
    if(l == r){
        tree[i] = a[l];
        return ;
    }
    long long mid = l + r >> 1;
    build(i << 1, l, mid), build(i << 1 | 1, mid + 1, r);
    tree[i] = tree[i << 1] + tree[i << 1 | 1];
}

void add(long long i, long long l, long long r, long long v){
    tree[i] += (r - l + 1) * v, lazy[i] += v;
}

void pushdown(long long i, long long l, long long r){
    long long mid = l + r >> 1;
    if(!lazy[i]) return ;
    add(i << 1, l, mid, lazy[i]), add(i << 1 | 1, mid + 1, r, lazy[i]);
    lazy[i] = 0;
}

long long query(long long i, long long l, long long r, long long x, long long y){
    if(x <= l && r <= y) return tree[i];
    long long sum = 0, mid = l + r >> 1;
    pushdown(i, l, r);
    if(x <= mid) sum += query(i << 1, l, mid, x, y);
    if(y > mid) sum += query(i << 1 | 1, mid + 1, r, x, y);
    return sum;
}

void change(long long i, long long l, long long r, long long x, long long y, long long v){
    if(x <= l && r <= y){
        add(i, l, r, v);
        return ;
    }
    long long mid = l + r >> 1;
    pushdown(i, l, r);
    if(x <= mid) change(i << 1, l, mid, x, y, v);
    if(y > mid) change(i << 1 | 1, mid + 1, r, x, y, v);
    tree[i] = tree[i << 1] + tree[i << 1 | 1];
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n), m = n;
    while(m--){
        cin >> x;
        if(!x){
            cin >> x >> y >> z;
            change(1, 1, n, x, y, z);
        }else{
            cin >> x >> y >> z, z++;
            cout << (query(1, 1, n, x, y) % z + z) % z << "\n";
        }
    }
    return 0;
}

AC记录

时间复杂度：O(n \log n)。

空间复杂度：O(n)。