2017计蒜之道第六场初赛 微软大楼设计方案(中等)（线段树）

近日，微软新大楼的设计方案正在广泛征集中，其中一种方案格外引人注目。在这个方案中，大楼由 $n$ 栋楼组成，这些楼从左至右连成一排，编号依次为 $1$ 到 $n$，其中第 $i$ 栋楼有 h_ih​i​​ 层。每栋楼的每一层为一个独立的 办公区域，可以步行 直达同层相邻楼栋的办公区域，以及 直达同楼栋相邻楼层的办公区域。

由于方案设计巧妙，上一层楼、下一层楼、向左右移动到相邻楼栋同层的办公区域均刚好需要 $1$ 分钟。在这些办公区域中，有一些被 核心部门 占用了（一个办公区域内最多只有一个核心部门），出于工作效率的考虑，微软希望核心部门之间的移动时间越短越好。对于一个给定的 最大移动时间 $k$，大楼的 协同值 定义为：有多少个 核心部门对 之间的移动时间不超过 $k$。由于大楼门禁的限制，不可以走出整个大楼，也不可以登上天台思考人生。你可以认为在办公区域内的移动时间忽略不计，并且在大楼内总是按照最优方案进行移动。

对于一个给定的新大楼设计方案，你能算出方案的协同值么？

输入格式

第一行包含两个正整数 $n,k(1\le k\le 200020)$，分别表示大楼的栋数以及最大移动时间。

第二行包含 $n$ 个正整数 h_1,h_2,...,h_n(1\leq h_i\leq 20)h​1​​,h​2​​,...,h​n​​(1≤h​i​​≤20)，分别表示每栋楼的层数。

接下来一行包含一个正整数 $m$，表示 核心部门 个数。

接下来 $m$ 行，每行两个正整数 x_i,y_i(1\leq x_i\leq n,1\leq y_i\leq h_{x_i})x​i​​,y​i​​(1≤x​i​​≤n,1≤y​i​​≤h​x​i​​​​)，表示该核心部门位于第 x_ix​i​​ 栋楼的第 y_iy​i​​ 层。

输入数据保证 $m$ 个核心部门的位置不会重复。

对于简单版本：$1\le n,m\le 50$；

对于中等版本：$1\le n\le 200000,1\le m\le 2000$；

对于困难版本：$1\le n,m\le 200000$。

输出格式

输出一个整数，即整个大楼的 协同值。

样例解释

样例对应题目描述中的图，核心部门 $1$ 和核心部门 $3$ 之间的距离为 $8>7$，因此不能计入答案。

样例输入

5 7 4 1 1 3 1 3 1 4 3 1 4 3

样例输出

2

思路：区间问题线段树，线段树求两个核心部门之间的最小层数（RMQ)，则dis（A,B）=fabs(xA-xB)+yA+yB-2*(A到B之间最小层数) 时间复杂度：O（n*logn+m^2*logn）;

代码：

#include <stdio.h> #include <math.h> #include <algorithm> #include <utility> using namespace std; const int N=200001; pair<int,int> t[N]; const int INF=0x3f3f3f3f; const int maxn=401000; int n_,k,h,m,ans=0; //存储线段树的全局数组； int n,dat[2*maxn-1]; //初始化 void init(int n_) { //为计算方便，元素个数扩大为2的幂； n=1; while(n<n_) n*=2; for(int i=0;i<2*n-1;i++) dat[i]=INF; } //n_个元素的初始化：for(int k=0;k<n_;k++) update(k,a[k]); //把第k个值（从0开始）更新为a； void update(int k,int a) { k+=n-1; dat[k]=a; //向上更新； while(k>0) { k=(k-1)/2; dat[k]=min(dat[2*k+1],dat[2*k+2]); } } //求[a,b)的最小值； //后面的参数是为了计算方便传入的； //k是节点的编号，l,r表示这个节点对应的是[l,r)区间； //外部调用时，用query(a,b,0,0,n)； int query(int a,int b,int k,int l,int r) { //如果[a,b)和[l,r)不相交，则返回INF； if(r<=a||b<=l) return INF; //如果[a,b)完全包含[l,r)，则返回当前节点的值； if(a<=l&&r<=b) return dat[k]; else{ //否则返回两个儿子中值的较小者； int vl=query(a,b,k*2+1,l,(l+r)/2); int vr=query(a,b,k*2+2,(l+r)/2,r); return min(vl,vr); } } int main() { scanf("%d %d",&n_,&k); init(n_); for(int i=0;i<n_;i++){ scanf("%d",&h); update(i,h); } scanf("%d",&m); for(int i=0;i<m;i++) scanf("%d %d",&t[i].first,&t[i].second); for(int i=0;i<m-1;i++) for(int j=i+1;j<m;j++){ int H=query(min(t[i].first,t[j].first)-1,max(t[i].first,t[j].first),0,0,n); int len=fabs(t[i].first-t[j].first)+fabs(t[i].second+t[j].second)-2*H; if(len<=k) ans++; } printf("%d\n",ans); return 0; }