其他的题要么不会要么太简单了，这个题想出来了还是挺惊喜的。

题目

【题目背景】
ReLU 函数是机器学习中常用的一个激活函数，其定义为：ReLU(x)=max(0,x)。
【题目描述】
在西西艾弗岛上有一台基于哥德尔机原理设计的通用人工智能机器，小C是负责维修这台机器的机器人。
有一天小C发现这个机器在一个算法部分上遇到了计算瓶颈，这个算法是这样的：
机器内部维护了一个神经网络，这个神经网络的权重是一个二维矩阵V，并且权重是一个整数。
即对于每个二维坐标(x,y)，矩阵在该位置的权重是V(x,y)，初始权重为0。
神经网络会进行n轮学习操作，每轮学习会给出参数x1,x2,y1,y2,v，然后对每个满足 x1 ≤ x ≤ x2, y1 ≤ y ≤ y2 的 (x,y)，将该位置对应的神经网络权重V(x, y) 修改为 v + ReLU(V(x,y)−v)；
在所有学习操作之后，神经网络的参数定下来不变了，紧接着有m次神经网络推理操作，每次推理操作给出x1,x2,y1,y2，查询对应子矩阵范围内最大的神经网络权重，即 max V(x,y)(x1 ≤ x≤x2,y1 ≤ y ≤y2)
小C发现机器在枚举这个问题优秀的算法时卡住了，目前只枚举出了一个很暴力的算法，为了让机器可以快点启动，他决定自己写好这个问题的算法来降低其启动常数，
你能帮帮他吗？
【输入格式】
从标准输入读入数据。
输入的第一行包含两个整数n,m；
接下来n行每行五个整数x1,x2,y1,y2,v，依次表示每次学习操作的参数；
接下来m行每行四个整数x1,x2,y1,y2，依次表示每次推理操作的参数。
【输出格式】
输出到标准输出。
共m行，依次表示每次查询操作的答案。
【样例1输入】

1
2
3
4
5
6
7
8
9
10
11
5 5
1 3 2 3 3
4 5 2 5 1
3 5 1 2 1
2 5 3 4 4
1 4 3 4 2
1 5 2 5
1 5 2 5
1 5 1 5
1 4 1 5
2 5 1 3

【样例1输出】

1
2
3
4
5
4
4
4
4
4

【子任务】
对于10%的数据，满足1≤n,m≤100。
对于另外10%的数据，满足1≤n,m≤10^3。
对于另外20%的数据，满足1≤n,m≤10^4。
对于另外20%的数据，满足1≤n,m≤5×10^4。
对于另外10%的数据，满足1≤n≤10^3。
对于100%的数据，满足1≤n,m≤5×10^5，对每个修改或查询操作，满足1≤x1≤x2≤n，1≤y1≤y2≤n对每个修改操作，满足1≤v≤n，所有数值为整数。

分析

最简单的解法当然是按照他说的模拟，但是这样只能得 20% 还是 40% 的分，这显然是可以尝试更精进一些的。

一开始以为是什么二维前缀和，二维差分之类的，然后发现一是不会写，二是好像不太对。

后面注意到修改值是修改为 v + ReLU(V(x, y) − v)，其中 ReLU(x)=max(0,x)，那么我们直接带入或编写的时候就可以发现是 v + max(0, V(x, y) - v) = max(v, V(x, y))。
所以这个学习操作就只是在新输入的值 v 和原有的值 V(x, y) 取更大的值而已，而查询操作也是求的最大值，不得不说这个套人工智能的壳确实有点意思。

那么对于最大值，首先想到的是 ST 表，遗憾的是，一维的 ST 表我都仅是有印象，更何况是二维的。而且 ST 表在前面修改部分是优化不了的，暴力修改肯定不对。

于是开始寻思偷鸡了，一开始还以为查询的某个点的最大值，于是就寻思：毕竟没要求在线查询，我可以把所有修改和查询先收集起来，然后对于查询的每个点，直接看所有修改有没有覆盖这个点，然后就取有覆盖的最大值就好了，这样就不用每次暴力修改了。

写到后面发现不对啊，查询的是一个面，不是点。
差点怀疑人生以为寄了，不过好在想了想后灵光一闪，发现只要更新最大值时更新到查询的范围内的其中一个点，就可以和它取最大值。
我草，那不就是矩形覆盖吗？犹记得之前写过一道矩形覆盖的题，写了一大堆条件写得我怀疑人生，好在记得其实正确答案不用写这么多的。具体来说就是用取反的方法，判断它们不相交是比较简单的，所以只要它们不是不相交，那么它们就是相交的。

然后还想到个优化，就是既然是求最大值，直接把修改操作按输入的值 v 排序，这样第一个覆盖到的修改操作就是答案了。
另外值得注意的是默认值是 0，也是有可能都没有修改到的。

解法

总结下来解法就是，离线获取所有的更新最大值的操作和查询操作，将操作按 v 值逆序排序，然后对于每个查询，依次判读二者范围的矩形是否相交，第一个相交的 v 值即为结果。若没有相交的则为 0。

最坏的复杂度应该是 O(nlogn + mn)，不过一般都不至于这么坑吧。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;

struct op
{
    int x1,x2,y1,y2,v;
}temp;
bool cmp(op &a, op &b) {
    return a.v > b.v;
}

int main() {
    // freopen("in1.in", "r", stdin);
    int n,m;
    scanf("%d%d", &n, &m);
    vector<op>ops(n);
    int x1,x2,y1,y2,v;
    for(int i=0;i<n;++i) {
        scanf("%d%d%d%d%d", &temp.x1,&temp.x2, &temp.y1,&temp.y2, &temp.v);
        ops.emplace_back(temp);
    }
    sort(ops.begin(), ops.end(), cmp);
    ++m;
    while(--m) {
        scanf("%d%d%d%d", &x1,&x2, &y1,&y2);
        v = 0;
        for(auto &theOp: ops) {
            if(theOp.x1>x2 || theOp.x2 < x1 || theOp.y1 > y2 || theOp.y2 < y1) {
                continue;
            }
            v = theOp.v;
            break;
        }
        printf("%d\n", v);
    }
    return 0;
}

总结

写出来了，还是挺开心的。毕竟很久没搞算法竞赛了，写的题目要么就是简单的要么就是不会的，难得有想想能想出来的。
分数这次好像也是不错，希望能一直好下去。
lalala😋😋😋