P4231 三步必杀 题解

首先看到题目发现和P1438 无聊的数列很像，而且难度都相同，于是就想到用线段树维护差分数组就可以了。

可看到数据范围：

$1\leq n\leq 10^7$

这是什么鬼？！最后一个一个查询的时间复杂度需要$O(n\log n)$的时间复杂度，很明显就T掉了。

正解

观察题目，发现这题有$m$次修改，却没有查询，就和差分很像，不过细想之后发现只有一个差分数组的时候要维护$d_l\sim d_r$。这时我们只能用线段树或树状数组维护，还会T。

先把关系写出来：

$$d_l+s,d_{l+1\sim r}+d,d_{r+1}-e$$

发现修改的之后$d_{l+1\sim r}$的差分值没有改变，于是又开了一个差分数组$d2$。

先找一下规律：

l=2,r=5
a: 1  1  2  3  4  3  2
d[2]+s,d[3.4.5]+d,d[6]-e
d: 1  0  1  1  1  -1  -1
d1[2]+s,d1[3]+d-s,d1[6]-d-e,d1[7]+e
d1: 1  -1  1  0  0

此时我们将d1数组做一个前缀和：

d1[1],d1[1]+d1[2]+s,d1[1]+d1[2]+d1[3]+d
d1[1]+d1[2]+d1[3]+d1[4]+d,d1[1]+...+d1[5]+d,d1[1]+d1[2]+...+d1[6]-e
d1[1]+d1[2]+...+d1[7]-e

可以推出此时维护d1的前缀和时：

d[1],d[2]+s,d[3]+d,d[4]+4,d[5]+d,d[6]-e,d[7]

发现与我们维护的d数组完全相同，所以我们用d1数组维护d的差分，然后将d1[l]+s,d1[l+1]+d-s,d1[r+1]-d-e,d1[r+2]-e，就可以$O(1)$修改。

最后查询时发现

$$\begin{aligned} &d_k=\sum_{i=1}^{k}{d1_i} \\ &a_k=\sum_{i=1}^{k}{d_i} \end{aligned}$$

则我们可以先求出任意$d_k$的值，最后求一遍前缀和就行了，时间复杂度$O(n)$。

则程序总时间复杂度是$O(n+m)$，可以过。

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e7 + 5;

int n, m;
int l, r, s, e, d;

long long diff[N];

signed main() {
#ifndef ONLINE_JUDGE
	freopen("P4231.in","r", stdin);
//	freopen(".out", "w", stdout);
#endif
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> l >> r >> s >> e;
		d = (e - s) / (r - l);
		diff[l] = diff[l] +  s, diff[l + 1] = diff[l + 1] + (d - s), diff[r + 1] = diff[r + 1] - (d + e), diff[r + 2] = diff[r + 2] + e;
	}
	long long tmp = 0;
	long long resxor = 0, resmax = -0x3f3f3f3f;
	for (int i = 1; i <= n; ++i) {
		diff[i] += diff[i - 1];
		tmp += diff[i];
		resxor ^= tmp;
		resmax = (resmax > tmp ? resmax : tmp);
	}
	printf("%lld %lld\n", resxor, resmax);
	return 0;
}

The end