线段树Cogs 775山海经

775.山海经

★★★ 输入文件： hill.in 输出文件： hill.out 简单对比

时间限制：1 s 内存限制：128 MB

【问题描述】

南山之顶即鹊山。其首日则显赫若画, 位于西海之巅, 植物茂盛, 多桂树点缀其间, 命名为祝余者, 于荒漠中生长, 能耐酷暑严寒……又东行三百里处, 即为堂庭之山, 植物种类丰富, 常有奇树异草生其间, 其中有白猿出没于林间.

再向东行三百八十里处, 则为猨翼之山. 山中分布着各种怪兽与奇异生物: 水中常有奇怪鱼类出没, 山上栖息着白玉奇石及蝮虫、怪蛇. 山顶上建有祝余木可供攀登. 然后不可攀登.

《山海经》是一部以山为主线、大海为贯穿物来记载古代自然与人文特征的手册，在其编年中每一段落都不会涉及相同的山脉两次。有一天，地理老师想再次游览这部经典著作中的某一特定路径（i,j）。他希望找到这样一条路径的所有山的喜好程度之和（c,d），其中a≤c≤d≤b能够达到最大值。于是他向我求助，请问你能否帮助他实现这一目标？需要注意的是，在《山海经》中，第i座山只能通向第i+1座山。

【输入】

输入第1行是两个数，n，m，2≤n≤100000，$1≤m≤10000