专栏文章

一维差分进阶及二维差分

ssccc_
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minjex4q
此快照首次捕获于
2025/12/02 03:23
3 个月前
此快照最后确认于
2025/12/02 03:23
3 个月前
查看原文

二维差分

导入

如图，若我们想将图中的黄色部分都加上 vv，二维差分是一种比暴力枚举更优的方式。
若我们给 diffx1,y1diff_{x1, y1} 加上 vv，则会像上图一样多加了很多。
于是，可以将多的部分减掉 vv。即 diffx1,y2+1diff_{x1, y2 + 1} 与 diffx2+1,y1diff_{x2 + 1, y1} 减 vv。
但是，又多减掉了 diffx2+1,y2+1diff_{x2 + 1, y2 + 1}，再把它加回来就好了。

U508313 二维差分

CPP
#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

用差分将有监控覆盖的地方加一，求一遍前缀和，发现有地方会大于 11。为了统一，将大于 11 的地方都改为 11，再求一遍前缀和在判断即可。
CPP
#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

在给定的 kk 个前缀和元素中，最多可以求出 k−1k - 1 个数组元素。在这 k−1k - 1 个数组元素中，若出现 ai>ai+1a_i > a_{i + 1}，则绝对无解。
则用最大元素乘上剩下的元素个数，若大于等于 sum1sum_1，即前缀和数组的第一个值，则必定可行。因为多的是可以剪掉的 。而如果少了的话，是怎么加都加不了的，所以必定无解。
CPP
#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

发现暴力行不通，考虑对坐标离散化。
令 aa 数组存储离散化后的数轴左右端点。
再令 diff1,diff2diff1, diff2 为差分里一个加的数组，一个减的数组。
枚举数轴，再用差分：diff1[l]++, diff2[r]--。
枚举点，sumsum 统计当前点的数轴个数：
  • 当 sum≥ksum \ge k 且标记 f=0f = 0 时，存储答案，且标记 f=1f = 1。
  • 当 sum<ksum < k 且标记 f=1f = 1 时，存储答案（因为之前统计差分时是没有 + 1 的，所以当前点也算一个答案），标记 f=0f = 0。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...