2016保研题：魔法学校

题目

做法

因为要维护的是若干时间区间上的最大值，而且每一个时间点也是另一个学号序列的区间修改。直觉上想用可持久化线段树套个东西来解决。不过最大值这个东西没法维护，想了很长时间也没想出来。

跟别人讨论后感觉这个题只能用莫队算法。可以参考 https://zhuanlan.zhihu.com/p/25017840 。用线段树维护每个学生收到的短信数量。每次端点的移动耗时O(logn)。总时间复杂度O($n\sqrt{n}\log_2{n}$)。