Inconvenient Pairs（线段树/二分）

题目 题意：给定由n个横街道和m个纵街道组成的地图（其中边界0和1000000默认都是街道）；给定k个在街道上的行人（显然这些行人所在的横或纵坐标至少有一个在街道上）。求有多少对人，他们之间的最短距离不是曼哈顿距离（当然，两个人之间只能通过街道走路，不能穿墙）。 思路：在草稿纸上画一画，可以较容易的得出结论。对于所在横、纵坐标都处于街道上的人（如下图小黄），他去任何其他人的最短距离都是最短距离。

对于只有横或纵坐标处于街道上的人（如下图小黄），不失一般性，不妨设该人所在横坐标在街道上，设离他最近的左纵街道为L，右纵街道为R，那么小黄和L左边的人，以及右边的人的最短距离都是曼哈顿距离。小黄和(L,R)中的距离不是最短距离（如下图浅绿），但需要排除(L,R)中和小黄同个街道的人（如下图深绿）。因此，我们可以按顺序添加行人。计算浅绿人头，可以用区间查询，分别维护横和纵方向的线段树；计算深绿人头，可以用二分，维护每条街道的有序集合（代码用的是set）。

#include 
using namespace std;
#define ll long long
const int maxn = 200010;
const int maxm = 300010;
const int mx = 1000001;
#define lson (rt