#PU495. USACO 2014 December Contest, Gold — Problem 2. Marathon

    ID: 1217 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:dec14来源:usaco.orgscoring:equal_test_cases线段树分块

USACO 2014 December Contest, Gold — Problem 2. Marathon

USACO 2014 December Contest, Gold — Problem 2. Marathon

题目描述

Problem 2: Marathon [Nick Wu, 2014]

An avid marathon runner herself, Bessie enjoys creating marathon

courses for her fellow cows to run. She has most recently designed a

route specified by N checkpoints (1 <= N <= 100,000) that must be

visited in sequence.

Unfortunately, Bessie realizes that the other cows may not have the

stamina to run the full route. She therefore wants to know how long

certain sub-routes take to run, where a sub-route is a contiguous

subsequence of the checkpoints from the full route. To make matters

more complicated, Bessie knows that the other cows, being lazy, might

choose to skip one checkpoint any time they run a sub-route --

whichever one results in a minimum total travel time. They are not

allowed to skip the first or last checkpoints in a sub-route, however.

In order to build the best possible marathon course, Bessie wants to

investigate the ramifications of making changes to the checkpoint

locations in her current course. Please help her determine how

certain changes to checkpoint locations will affect the time required

to run different sub-routes (taking into account that the cows might

choose to omit one checkpoint any time they run a sub-route).

Since the course is set in a downtown area with a grid of streets, the

distance between two checkpoints at locations (x1, y1) and (x2, y2) is

given by |x1-x2| + |y1-y2|.

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5 5

-4 4

-5 -3

-1 5

-3 4

0 5

Q 1 5

U 4 0 1

U 4 -1 1

Q 2 4

Q 1 4
11

8

8