题目描述

问题摘要

有 $N$ 个柱子排成一排，一开始每个柱子的损伤度均为 0。
接下来会进行 $M$ 次攻击，每次攻击可以用 4 个参数 $l, r, s, e$ 来描述：

  • 作用范围： 第 $l$ 个到第 $r$ 个之间所有的柱子（包含 $l, r$）。
  • 伤害数值： 对第 $l$ 个柱子的伤害为 $s$，对第 $r$ 个柱子的伤害为 $e$。
  • 伤害分布： 攻击产生的伤害值是一个等差数列。
    示例： 若 $l=1, r=5, s=2, e=10$，则对第 1~5 个柱子分别产生 2, 4, 6, 8, 10 的伤害。
    目标： 求出所有攻击完成后，每个柱子的最终损伤度。

输入格式

  1. 第一行包含 2 个整数 $N, M$，用空格隔开。
  2. 接下来 $M$ 行，每行 4 个整数 $l, r, s, e$，含义见题目描述。
  3. 数据保证对每个柱子产生的每次伤害值都是整数。

输出格式

由于输出数据可能过大无法全部输出，为了确保你真的能维护所有柱子的损伤度，只需要输出两个值：

  1. 所有柱子损伤度的异或和（XOR sum）。
  2. 所有柱子损伤度的最大值。
    _(注：异或即所有数字按位异或起来的值，C++ 中运算符为 ^)_

输入输出样例

样例 #1

输入：
Plaintext

5 2
1 5 2 10
2 4 1 1

输出：
Plaintext
3 10

样例 #2

输入：
Plaintext

6 2
1 5 2 10
2 4 1 1

输出：
Plaintext
3 10

二阶差分

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int N,M,l,r,s,e;
    cin>>N>>M;
    vector<int>zhu(N+3,0);
    for(int i=1;i<=M;i++)
    {
        cin>>l>>r>>s>>e;
        int d;
        if (r == l) {
            d = 0; 
        } else {
            d = (e - s) / (r - l);
        }
        zhu[l]+=s;
        zhu[l+1]+=d-s;
        zhu[r+1]-=d+e;
        zhu[r+2]+=e;
    }
    for(int i=2;i<=N;i++)
    zhu[i]+=zhu[i-1];
    for(int i=2;i<=N;i++)
    zhu[i]+=zhu[i-1];
    int x=zhu[1];
    int themax=zhu[1];
    for(int i=2;i<=N;i++)
    {
        if(zhu[i]>themax)
        themax=zhu[i];
        x^=zhu[i];
    }
    cout<<themax<<" "<<x;
}