2020 China Collegiate Programming Contest - Mianyang Site J.Joy of Handcraft

题目分析

题目大意：现在有一圈灯泡，给定这些灯泡的周期 t i t_i ti​和 x i x_i xi​。其中第 i i i个灯泡会在 ( 2 k t i + 1 ) s (2kt_i + 1)s (2kti​+1)s时刻亮起，并保持亮起直至 ( 2 k t i + t i ) s (2kt_i + t_i)s (2kti​+ti​)s后熄灭，即：在 ( 2 k t i + t i + 1 ) (2kt_i +t_i + 1) (2kti​+ti​+1)时刻开始保持熄灭，如此往复循环。

现在要求对于给定的灯泡序列，求出 [ 1 , m ] [1,m] [1,m]时间段内每个时间点最亮的灯泡的亮度。

思路分析：首先对于某一时间点，需要维护静态区间最大值，因此考虑线段树维护区间最大值。

首先我们所有的灯泡按照时间开始的顺序进行排序，对于相同周期的灯泡，我们按照亮度从大到小的顺序进行排序。然后模拟灯亮起的过程，不断地向线段树上插入当前时间区间的信息即可。值得注意的是，由于是取最大值，我们又按照相同时间从大到小进行了排序，因此对于相同周期的只需要遍历第一个即可。

Accepted Code

#include 
using namespace std;

const int N = 1e5 + 10;
int n, q, tree[N  1], tree[rt]); }

inline void push_down(int rt){
    if(lazy[rt]){
        lazy[rt