学校布置了作业,调了老半天都没办法多拿点分,目前是 WA + TLE,在线求调。洛谷私信找我要代码。
题目:
题目描述
某气象台每天都要从遍布于各地的观察站采集气温数据,并通过互联网为远程用户提供统计查询服务。其中最常见的一类查询是,用户指定一个矩形区域,查询该区域内的最高气温和最低气温。随着更多观察站的不断建立,原始数据本身的规模急剧膨胀。鉴于传统蛮力算法的效率已无法满足实用要求,气象台只好请你帮忙,通过改进数据结构和算法,提高查询的效率。
借助气象台提供的一组函数接口,服务器端可访问已采集到的所有数据,并报告查询结果。
数据范围
1 <= n <= 200,000,1 <= m <= 160,000
气温为整数,范围是 [0, 2^31)
观测站坐标为整数,范围是 [-2^31, 2^31);可能有坐标重合的观测站
对于每次查询,保证 x1 <= x2,y1 <= y2
资源限制
时间:2.5 sec
空间:256 MB