P4231 三步必杀

本文主要是介绍P4231 三步必杀，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem: P4231 三步必杀

思路

这个问题可以使用等差数列差分的思想来解决。等差数列差分主要适用于频繁对原始数组的某个区间进行增减。

解题方法

首先，我们创建一个长度为 n+2 的差分数组 arr，初始化为 0。
然后，我们遍历 m 次操作，对于每一个操作，我们将 s 加到 arr[l] 上，并从 arr[l+1] 中减去 s，然后将 d 加到 arr[l+1] 上，并从 arr[r+1] 中减去 d+e，最后将 e 加到 arr[r+2] 上。这样，arr[i] 就表示第 i 次操作的增减量。
接下来，我们对 arr 数组进行两次前缀和的计算，这样 arr[i] 就变成了第 i 次操作的总增减量。
最后，我们遍历 arr 数组，计算最大值和异或值，并输出。

复杂度

时间复杂度:

$O(n)$，其中 n 是操作的次数。我们需要遍历 m 次操作，然后对 arr 数组进行两次前缀和的计算。

空间复杂度:

$O(n)$，我们需要创建一个长度为 n+2 的 arr 数组。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr = new StreamTokenizer(in);static int n, m;static int MAXN = (int)(1e7 + 10);static int MAXM = (int)(3e5 + 10);static long[] arr = new long[MAXN];public static void main(String[] args) throws IOException {n = nextInt();m = nextInt();while(m-- > 0) {int l = nextInt();int r = nextInt();int s = nextInt();int e = nextInt();int d = (e - s) / (r - l);set(l, r, s, e, d);}build();long xor = 0, max = 0;for(int i = 1; i <= n; i++) {max = Math.max(max, arr[i]);xor ^= arr[i];}out.println(xor + " " + max);out.flush();}private static void build() {// TODO Auto-generated method stubfor(int i = 1; i <= n; i++) {arr[i] += arr[i - 1];}for(int i = 1; i <= n; i++) {arr[i] += arr[i - 1];}}private static void set(int l, int r, int s, int e, int d) {// TODO Auto-generated method stubarr[l] += s;arr[l + 1] += d - s;arr[r + 1] -= d + e;arr[r + 2] += e;}private static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}

这篇关于P4231 三步必杀的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---