[C++知识库]P2879 [USACO07JAN] Tallest Cow S(差分)

[USACO07JAN] Tallest Cow S - 洛谷https://www.luogu.com.cn/problem/P2879

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <cmath>
#include <map>
#include <cstdlib>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MN = 65005;
const int MAXN = 2000010;
const int INF = 0x3f3f3f3f;
#define IOS ios::sync_with_stdio(false)

int n, i, h, R;
int a[MAXN];
typedef pair<int, int> P;
bool vis[10001][10001];
P cow[MAXN];
int main() {
	scanf("%d %d %d %d", &n, &i, &h, &R);
	for (int i = 1; i <= R; i++) {
		scanf("%d %d", &cow[i].first, &cow[i].second);
	}
	for (int i = 1; i <= R; i++) {
		int x, y;
		x = cow[i].first;
		y = cow[i].second;
		if (x > y) {
			swap(x, y);
		}
		if (vis[x][y] == 0) {
			vis[x][y]=1;
			a[x + 1] -= 1;
			a[y] += 1;
		}
	}
	a[0] = h;
	for (int i = 1; i <= n; i++) {
		a[i] += a[i - 1];
		printf("%d\n", a[i]);
	}
	return 0;
}