一维差分进阶及二维差分

sccc_ · 2025-10-21 23:00:17 · 个人记录

二维差分

导入

如图，若我们想将图中的黄色部分都加上 v，二维差分是一种比暴力枚举更优的方式。

若我们给 diff_{x1, y1} 加上 v，则会像上图一样多加了很多。

于是，可以将多的部分减掉 v。即 diff_{x1, y2 + 1} 与 diff_{x2 + 1, y1} 减 v。

但是，又多减掉了 diff_{x2 + 1, y2 + 1}，再把它加回来就好了。

U508313 二维差分

#include<bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

int n, m, q, a[N][N], diff[N][N], sum[N][N];

void add(int x1, int y1, int x2, int y2, int val) {
    diff[x1][y1] += val, diff[x1][y2 + 1] -= val, diff[x2 + 1][y1] -= val, diff[x2 + 1][y2 + 1] += val;
} 

int main() {
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            add(i, j, i, j, a[i][j]);
        }
    }
    while (q--) {
        int x1, y1, x2, y2, x;
        cin >> x1 >> y1 >> x2 >> y2 >> x;
        add(x1, y1, x2, y2, x);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + diff[i][j];
            cout << sum[i][j] << ' ';
        }
        cout << endl;;
    }
    return 0;
}

HDU-6514 Monitor

用差分将有监控覆盖的地方加一，求一遍前缀和，发现有地方会大于 1。为了统一，将大于 1 的地方都改为 1，再求一遍前缀和在判断即可。

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, m, p, q, diff[N * 10];

void get_id(int x, int y, int v) {
    if (x > n || y > m)
        return;
    diff[(x - 1) * m + y] += v;
    return;
}

int query(int i, int j) {
    if (i == 0 || j == 0)
        return 0;
    return diff[(i - 1) * m + j];
}

void calc() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            diff[(i - 1) * m + j] += query(i, j - 1) + query(i - 1, j) - query(i - 1, j - 1);
        }
    }
}

int main() {
    cin.sync_with_stdio(false);
    while (cin >> n >> m) {
        memset (diff, 0, sizeof diff);
        cin >> p;
        for (int i = 1; i <= p; i++) {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            get_id(x1, y1, 1), get_id(x1, y2 + 1, -1), get_id(x2 + 1, y1, -1), get_id(x2 + 1, y2 + 1, 1);
        }
        calc();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                diff[(i - 1) * m + j] = min(diff[(i - 1) * m + j], 1);
            }
        }
        calc();
        cin >> q;
        for (int i = 1; i <= q; i++) {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            int ans = query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
            if (ans == (x2 - x1 + 1) * (y2 - y1 + 1))
                cout << "YES\n";
            else
                cout << "NO\n"; 
        }
    }
    return 0;
}

CF1738B Prefix Sum Addicts

在给定的 k 个前缀和元素中，最多可以求出 k - 1 个数组元素。在这 k - 1 个数组元素中，若出现 a_i > a_{i + 1}，则绝对无解。

则用最大元素乘上剩下的元素个数，若大于等于 sum_1，即前缀和数组的第一个值，则必定可行。因为多的是可以剪掉的 。而如果少了的话，是怎么加都加不了的，所以必定无解。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e5 + 10;

int t, n, k, a[N], diff[N];

void work() {
    cin >> n >> k;
    for (int i = 1; i <= k; i++) {
        cin >> a[i];
        diff[i] = a[i] - a[i - 1];
    }
    if (k == 1) {
        cout << "Yes\n";
        return;
    }
    for (int i = 2; i < k; i++) {
        if (diff[i] > diff[i + 1]) {
            cout << "No\n";
            return;
        }
    }
    int lst = diff[2];
    if (lst * (n - k + 1) >= a[1])
        cout << "Yes\n";
    else
        cout << "No\n";
}

signed main() {
    cin >> t;
    while (t--)
        work();
    return 0;
}

CF612D The Union of k-Segments

发现暴力行不通，考虑对坐标离散化。

令 a 数组存储离散化后的数轴左右端点。

再令 diff1, diff2 为差分里一个加的数组，一个减的数组。

枚举数轴，再用差分：diff1[l]++, diff2[r]--。

枚举点，sum 统计当前点的数轴个数：

• 当 sum \ge k 且标记 f = 0 时，存储答案，且标记 f = 1。
• 当 sum < k 且标记 f = 1 时，存储答案（因为之前统计差分时是没有 + 1 的，所以当前点也算一个答案），标记 f = 0。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e6 + 10;

int n, k, pt[N * 2], diff1[N * 2], diff2[N * 2], id, idx;
pair<int, int> a[N], ans[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;
        pt[++idx] = a[i].first, pt[++idx] = a[i].second;
    }
    sort (pt + 1, pt + idx + 1);
    for (int i = 1; i <= n; i++) {
        int l = a[i].first, r = a[i].second;
        l = lower_bound(pt + 1, pt + idx + 1, l) - pt;
        r = lower_bound(pt + 1, pt + idx + 1, r) - pt;
        a[i] = {l, r};
    }
    for (int i = 1; i <= n; i++) {
        diff1[a[i].first]++, diff2[a[i].second]--;
    }
    int sum = 0;
    bool f = 0;
    for (int i = 1; i <= idx; i++) {
        sum += diff1[i];
        if (sum >= k && f == 0) 
            ans[++id].first = i, f = 1;
        sum += diff2[i];
        if (sum < k && f == 1) 
            ans[id].second = i, f = 0;
    }
    cout << id << '\n';
    for (int i = 1; i <= id; i++) 
        cout << pt[ans[i].first] << ' ' << pt[ans[i].second] << '\n';
    return 0;
}