【coci2011/2012 3】距离之和
题目：
Mirko创造了一个新的机器人并且决定去测试一下。我们可以想象测试的跑道是一个二维的空间。初始的时候，机器人在（0，0）的位置，在收到了一系列命令之后，机器人就会移动，这些命令是S，J，I，Z，每个命令代表了不同的移动方向。 具体一下，如果机器人原来在（x，y）的位置，在收到了S的命令之后，会向（x，y+1）移动，收到J之后，会向（x，y-1）移动，收到I命令之后会向（x+1，y）移动，收到Z命令之后会向（x-1，y）移动。 在这个二维空间上有N个固定的控制点，在每个命令执行之后，每个固定点就会计算自己与机器人的曼哈顿距离，然后把这些距离的总和返回给Mirko。 说明：两个点（x1，y1）和（x2，y2）的曼哈顿是|x1-x2|+|y1-y2|。
输入：
第一行是正整数N（1<=N<=100000）和M（1<=M<=300000)，N表示控制点的个数，M表示命令的数量。 接下来N行，每行两个整数（绝对值不大于1000000），表示控制点的坐标，有些控制点可能是相同的。接下来一行，一个长度为M的字符串（包含以上四种命令），表示机器人依次收到的命令。
输出：
输出M行，每行一个整数，对于第i行，输出的是第i个命令执行以后所有控制点与机器人的曼哈顿距离之和。
乍一看，暴力肯定会超时
可以坑50%数据点
不过正解也很明显
我们一开始就把当前的曼哈顿之和先算出来
记录行和列上的控制点的个数
把它弄一个前缀和
之后用x和y记录当前机器人的坐标
我们每次得到一个操作，便根据情况从ans里减掉一些，加上一些就可以了
‘S’:
+ lq[y];//lq为列的前缀和，hq为行的前缀和，l为每列的操作点的个数，h为每行操作点的个数
- (n-lq[y]);//n为点的总数
'J':
+ n-lq[y]+l[y]
- (lq[y]-l[y])
'I':
+ hq[x]
- (n-hq[x])
'Z':
+ n-hq[x]+h[x]
- (hq[x]-h[x])
标程：（请勿抄袭，后果很严重）
var hq,lq,h,l:array[-1000001..1000001]of longint; ch:char; x,y,n,m,i,j,k,s,nx,ny:longint; ans:int64; begin assign(input,'robot.in'); assign(output,'robot.out'); reset(input); rewrite(output); readln(n,m); for i:=1 to n do begin readln(x,y); inc(h[x]); inc(l[y]); ans:=ans+abs(x-0)+abs(y-0); end; for i:=-1000000 to 1000000 do begin lq[i]:=lq[i-1]+l[i]; hq[i]:=hq[i-1]+h[i]; end; nx:=0; ny:=0; for i:=1 to m do begin read(ch); case ch of 'S': begin ans:=ans+lq[ny]; ans:=ans-(n-lq[ny]); inc(ny); end; 'J': begin ans:=ans-(lq[ny]-l[ny]); ans:=ans+(n-(lq[ny]-l[ny])); dec(ny); end; 'I': begin ans:=ans+hq[nx]; ans:=ans-(n-hq[nx]); inc(nx); end; 'Z': begin ans:=ans-(hq[nx]-h[nx]); ans:=ans+(n-(hq[nx]-h[nx])); dec(nx); end; end; writeln(ans); end; close(input); close(output); end.
