#include<cstdio>

#include<iostream>

using namespace std;

int main(){

int a, b;//定义两个加数

freopen("aplusb.in", "r", stdin);//导入文件

freopen("aplusb.out", "w", stdout);

cin >> a >> b;//输入加数

cout << a+b;//相加并输出

fclose(stdin);//关闭文件

fclose(stdout);

return 0;

}

图片来自OIWIKI 

扫描线算法就是用线段树给每个矩形的上下边进行标记，下面标记为 $1$，上面标记为 $-1$，然后从下往上不断统计答案，然后更新线段树。 

需要注意的是，每个线我们保存的是一个区间的信息，所以需要注意 $r + 1$ 或 $r - 1$。 

因为每个节点坐标的取值区间太大，所以我们要离散化，然后二分找值。

定义 $f(u,k)$ 表示以 $u$ 为根的子树里有 $k$ 个节点与 $u$ 联通的最小道路，$size(u)$ 为 $u$ 的子树内节点个数。

初始状态：$\forall u \in [1,n],f(u,1)=|son_u|$，其中 $|son_u|$ 表示 $u$ 的出边个数。

转移方程：

$$\sum\limits_{v\in son_u,j\in [1,size(u)],k\in [1,size(v)]} f(u,j+k)=\min\{f(u,j)+f(v,k)-2\}$$

其中 $-2$ 是因为最初 $u,v$ 两点的连边被断开，多加的 $2$ 要在这里减回来。

感性理解一下为什么说时间复杂度是 $\Theta(n^2)$ 的：

发现主要的时间复杂度是在 $j,k$ 的枚举上，而 $j,k$ 的枚举其实等价于枚举点对。

原因不难理解，每两个节点只有在它们的 LCA 处会被枚举到。

因此，总的时间复杂度是 $\Theta(n^2)$

思路：

    求出每个数据包在网络中存在的最（晚）后时刻，不妨记作 $last$，则 $last>T$ 的数据包数即是答案。

要点：

    1、对于被复制的某数据包，服务器 $i$ 只会转发最早且第一次到达自己的那个复制包，因为后续到达的相同数据包将会被接收而不再转发；

    2、最早到达服务器 $i$ 的复制包一定是通过最短路（最少传输时间）抵达的，然后通过服务器 $i$ 的最长出边转发出去的复制包可能会在网络中存在更久；

    3、那么，对于服务器 $i$ 而言，某数据包传输过程分为两段：（1）从起点 $s$ 沿最短路抵达服务器 $i$；（2）沿服务器 $i$ 最长边转发至邻接服务器；

    则：某数据包传输时间 $=$ $shortest[i]$ $+$ $farest[i]$，前者是从 $s \sim i$ 的最短路，后者是 $i$ 的最长出边；

    综上，$last = max\{ shortest[i] + farest[i] \} + startime$（开始传输时刻） 

这一题的一个比较简单的思路，就是对于一个点 $a_i$，找到 $y$ 坐标在区间 $[y_i + m, max_y]$ 内的所有点中，$x_i$ 的前驱和后继，然后更新答案。

对于二维平面上的的区间查询问题，树套树应该是最经典的解法了。比如这一题可以用线段树套平衡树，对于线段树的每个节点 $[L, R]$ 上建立一个平衡树，保存输入序列上 $y$坐标 落在 $[L, R]$ 内的点的 $x$ 坐标。因为平衡树本身支持查询前驱和后继，所以实现树套树之后就很简单了，该算法的时间复杂度为 $O(n \log^2 n)$。不过似乎树套树主要用来解决带修的这种问题，并且不容易调试，码长略长，所以还是思考另外的做法。

跟磁力块那一题的解法类似，可以用分块做，一开始觉得用分块时间复杂度可能比较高（当时还准备放弃写树套树，幸亏我太蒻了没学过树套树，要不然掉进坑里了），但是实际好像相当快？

对于每个块用 $y$ 值排序，内部用 $x$ 值排序，对于每一个点，二分找到满足条件（即 $y$ 坐标和该点的 $y$ 坐标的差 $\ge m$）的最小的块（预先保存每个块的最小 $y$ 值），由于预先排序保证了这个块之后的块也都满足条件，然后再在这些块内部二分找到 $x$ 坐标的前驱和后继，更新答案，然后对于最左的块的左边一个块，朴素枚举，更新答案。

对于每一个点的查询操作，时间复杂度为 $O(\sqrt n \log n)$

故总时间复杂度为 $O(n \sqrt n \log n)$

当然，这样的时间复杂度还是很高，但是还有很多优秀的算法：

譬如 skylake 大佬的算法：通过维护 $y$ 坐标的区间最值，然后用尺取法，保证两个最值的差 $\ge m$，然后更新答案。这个算法实在是太优秀了，并且代码写出来极为简洁，好像是大佬开始比赛十分钟秒掉的？简直叹为观止 orzorz%%%%%%%%，我还没有学过 RMQ，可能不是很了解，不过据推测这个时间复杂度是 $O(n \log n + n)$？果然犇人写犇算法，直接比我的算法快一个数量级（虽然可能这一题数据太水，我的代码反而快了大雾）。

再譬如 关神犇 提出的算法：维护两个二叉堆，堆内以 $y$ 坐标为关键字，并且在堆外以 $x$ 为关键字排序。每次枚举一个点就取出两个堆中满足条件的点，更新答案，然后弹出这些数（因为已经以 $x$ 为关键字排序，所以在当前点之后的点不会离这些点更近，即这些点对于答案已经没有贡献了），之后把该点存入堆内。这个算法实在是太神了（关神犇您是我的神orzorzorz%%%%%%%%%%%%%%%），因为只进行了 $2n$ 次插入和 $n$ 次删除操作，每个操作的时间复杂度是 $\log n$，所以总时间复杂度为 $O(n \log n)$。看这道题的标签里有优先队列，也许正解就是这个，为此再次膜拜神犇叹为观止的做题直觉orzorz。

当然，除此之外，还有用线段树维护区间最值的神犇的方法，具体思路和 skylake 大佬的大同小异，不过线段树实现代码更加冗长，这里不再赘述。

上述各位神犇的思路我都进行了代码实现，可以去 我的博客 察看作为参考。

选择了第一个选左边或者右边之后，不难想到第一个选到的数所对应的另一个数一定要最后一个输出，为了达到最后一个输出，这个两边的数要分开处理，左边的数对应的都是 L，右边的数对应的都是 R。

将这两边看做两个队列 $L$ 和 $R$，首先我们感性地考虑：两边队头对应的另一个数一定比较 “远”，猜测可能是两边队列的队尾。接下来我们证明一定是队尾：

假设接下来要确定的回文子串的长度是 $l$（先前确定在答案序列中的数已在队列中删除），那么 $|L| + |R| - 2 = l - 2$，就是说除了这两个数之外的 $l - 2$ 个数都要先弹出队列，如果对应的这个数不在队尾，那么除非包括这个数弹出，弹出队列的数量达不到 $l - 2$，就是说这个数把队列卡住了。由此，队头对应的数一定是队尾，如果两个队列的队尾都没有对应的数，就说明无解。

确定队头对应的数一定是其中一个队列的队尾之后，把这个两个数从队列中删除也就不难了，只需实现两个双端队列，弹出一个队头之后把这个队尾也弹出就行了，假设队头的答案序列位置是 $k$，那么对应的队尾的位置就是 $n - k + 1$。

考虑字典序，我们优先把第一个数选为 L，并且队头也要优先考虑 L 。