Description

Solution

我最近到底怎么了，这种题都做不出来了，一看题第一反应李超线段树（虽然不会），觉得不可做，看一眼题解才发现这个题可以差分，然后差分还打错了好几次，我大概是要退役了吧。

Code

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

#include <iostream>

typedef long long ll;

const int N = 1e7 + 10;

ll a[N], b[N], c[N];

int n, m;

int main() {

	scanf("%d%d", &n, &m);

	ll x, y, z, w;

	for (int i = 1; i <= m; ++i) {

		scanf("%lld%lld%lld%lld", &x, &y, &z, &w);

		ll d = (w - z) / (y - x);

		c[x] += z; c[x+1] += d - z; c[y+1] -= w + d; c[y+2] += w;

	}

	for (int i = 1; i <= n; ++i) b[i] = b[i-1] + c[i];

	ll mx = 0;

	for (int j = 1; j <= n; ++j) a[j] = a[j-1] + b[j], a[0] ^= a[j], mx = std::max(a[j], mx);

	std::cout << a[0] << ' ' << mx << std::endl;

	return 0;

}

Note

开了long long的地方就不要再用int了，万一哪里错了就gg了。多层差分的时候要前后多玩几项，防止落下某些差分项。

巴特西

[Luogu]三步必杀

Description

Solution

Code

Note

最新文章

热门文章