P7745 [COCI 2011/2012 #3] ROBOT
题目背景
Mirko 创造了一个新的机器人，并决定在一个巨大的测试轨道上测试它。
题目描述
我们不妨把测试轨道想象成一个二维坐标系。机器人从(0,0) 开始，接收一组由 SJIZ 表示的指令，每一个指令都标志着机器人应该在哪个方向移动。具体地，如果机器人当前位于(x,y)：
- 指令 S 意味着它应该移动到(x,y+1)。
- 指令 J 意味着它应该移动到(x,y-1)。
- 指令 I 意味着它应该移动到(x+1,y)。
- 指令 Z 意味着它应该移动到(x-1,y)。
当机器人接受指令并在测试轨道上移动时，Mirko 以下列方式验证其位置：
测试轨道上有n 个固定的控制点，每个控制点都会测量与机器人的**曼哈顿距离**，并将所有距离的和发送给 Mirko。假设机器人完全按照指令移动，请你计算执行每条指令后所有控制点距离机器人的曼哈顿距离之和。
输入格式
输入共n+2 行。
第一行，两个整数n,m，分别表示控制点的数量和指令的数量。
第2\sim n+1 行，每行两个整数(x_i,y_i)，分别表示每个控制点的横坐标和纵坐标。
第n+2 行一个长度为m 的字符串，表示机器人将接收到的指令。
输出格式
输出共m 行，每行一个整数，表示执行每条指令后所有控制点距离机器人的曼哈顿距离之和。
输入输出样例 #1
输入 #1
```
1 3
0 -10
ISI
```
输出 #1
```
11
12
13
```
输入输出样例 #2
输入 #2
```
3 5
0 0
1 1
1 -1
SIJJZ
```
输出 #2
```
5
4
3
4
5
```
说明/提示
【前置知识】
- 曼哈顿距离：设有两个点(a,b) 和(c,d)，则这两个点的曼哈顿距离为|a-c|+|b-d|。
【数据范围】
对于所有数据，$1\leqslant n\leqslant 10^5$，$1\leqslant m\leqslant 3\times 10^5$，$|x_i|,|y_i|\leqslant 10^6$，指令仅包含 SIJZ 四个字符中的一个。
【题目来源】
本题来源自 _[COCI 2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST 3](https://hsin.hr/coci/archive/2011_2012/contest3_tasks.pdf) T4 ROBOT_，按照原题数据配置，满分120 分。
由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。
（题面懒得维护了。）
思路
lower_bound二分和前缀和做法
本题要求的是一个会动的点和每一步后它对于其他固定点的的曼哈顿距离之和。
因为求的是曼哈顿距离（即|x-x_i|+|y-y_i| ），所以不妨把一个点打散成x_i 和y_i 两个数组，分别求这个点的x 到x_i，y 到y_i 的距离，分开来求且不影响结果。
由于绝对值的原因，一个点会把x_i 的求距离方式分为x-x_i(x_i\lt x) 和x_i-x(x_i\ge x) 两种。所以我们可sort()一下x_i 再代入x 用二分求得下标k，则左边部分全是(x_i\lt x)，右边部分全是(x_i\ge x)。
（其中大于等于的等于号要不要取都可以，因为代码中直接lb-1方便所以这里直接(x_i\ge x) ）
观察第一部分x-x_i 求和，即\sum_{i=0}^kx-x_i。不妨先预处理前缀sumx[k]表示前k 个x_i 的大小再减去k*x，sumx[k]-k*x；
第二部分是x_i-x 求和，$\sum_{i=k+1}^nx-x_i$。可以通sumx[n]-sumx[k]-(n-k)*x求和。
合并两部分(k*2-n)*x-sumx[k]*2+sumx[n]，y轴同理。
再加一个控制上下左右的代码。
复杂度O(m\log n)。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[114514],b[114514],suma[114514],sumb[114514],x,y;
int solve() {
int lx=lower_bound(a+1,a+n+1,x)-a-1;
int ly=lower_bound(b+1,b+n+1,y)-b-1;
return (lx*2-n)*x-suma[lx]*2+suma[n]+(ly*2-n)*y-sumb[ly]*2+sumb[n];
}
signed main() {
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i];
sort(a+1,a+n+1);
sort(b+1,b+n+1);
for(int i=1;i<=n;i++) {
suma[i]=suma[i-1]+a[i];
sumb[i]=sumb[i-1]+b[i];
}
string s;
cin>>s;
for(int i=0;i<m;i++) {
if(s[i]=='S')
y++;
if(s[i]=='J')
y--;
if(s[i]=='I')
x++;
if(s[i]=='Z')
x--;
cout<<solve()<<"\n";
}
return 0;
}