[洛谷P4231]三步必杀 题解

洛谷P4231 三步必杀

传送门

• 思路：

题目中数据范围为 (N=10^7) ，这很明显是在告诉我们正解是 (operatorname{O}(N)) 算法。

而能做到 (operatorname{O}(1)) 静态修改与查询的自然就是差分了。

设原数组的 (A) ，差分数组为 (B) ，进行操作 ((l,r,s,t)) 时，令公差为 (d = frac{t - s}{r - l})，则

(forall i in [l,r],A_i gets A_i + s + (i-l) times d)

手推一下对应的差分数组 (B) 的变化：

(B_l gets B_l + s)

(forall i in (l,r],B_i gets B_i + d)

(B_{r + 1} gets B_{r + 1} - t)

发现 (B) 数组中仍然要进行区间修改操作，而差分数组只能支持单点修改，怎么办呢？

那就再增加一个 (B) 的差分数组 (C)，推一下 (B) 数组变化时 (C) 数组的变化：

对 (B_l) 执行单点修改，则在 (C) 中：(C_l gets C_l+s) , (C_{l+1} gets C_{l+1} - s)

对 ((l,r]) 执行区间修改，则：(C_{l+1} gets C_{l+1} + d) , (C_{r + 1} gets C_{r + 1} - d)

对 (B_{r+1}) 执行单点修改，则： (C_{r + 1} gets C_{r + 1} - t) , (C_{r + 2} gets C_{r+2} + t)

那么在程序中我们只需要开一个数组 (C) ，操作中按照上述方法更新。

统计时开两个前缀和变量 (sum_1,sum_2)，对应的算出 (B) 数组的元素，(A) 数组的元素，最后统计一下答案即可。

code:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
const int maxn = 1e7 + 5;
int read() {
	int s = 0;
	char c = getchar();
	for(;!isdigit(c);c = getchar());
	for(;isdigit(c);c = getchar())s = (s << 1) + (s << 3) + (c ^ '0');
	return s;
}
int n,m;
long long c[maxn];
int main() {
	n = read();
	m = read();
	for(int i = 1;i <= m;++ i) {
		int l = read(),r = read(),s = read(),e = read();
		int d = (e - s) / (r - l);
		c[l] += (long long)s;
		c[l + 1] -= (long long)s;
		c[l + 1] += (long long)d;
		c[r + 1] -= (long long)d;
		c[r + 1] -= (long long)e;
		c[r + 2] += (long long)e;
	}
	long long sum1 = 0,sum2 = 0,ans = 0,cnt = 0;
	for(int i = 1;i <= n;++ i) {
		sum1 += c[i];
		sum2 += sum1;
		cnt ^= sum2;
		ans = max(ans , sum2);
	}
	printf("%lld %lld",cnt,ans);
	return 0;
}