2017 計蒜之道 初賽 第六場 微軟大樓設計方案（中等）

網址：https://nanti.jisuanke.com/t/15773

近日，微軟新大樓的設計方案正在廣泛征集中，其中一種方案格外引人注目。在這個方案中，大樓由 nn 棟樓組成，這些樓從左至右連成一排，編号依次為 11 到 nn，其中第 ii 棟樓有 h_ih

​i

​​ 層。每棟樓的每一層為一個獨立的 辦公區域，可以步行 直達同層相鄰樓棟的辦公區域，以及 直達同樓棟相鄰樓層的辦公區域。

由于方案設計巧妙，上一層樓、下一層樓、向左右移動到相鄰樓棟同層的辦公區域均剛好需要 11 分鐘。在這些辦公區域中，有一些被 核心部門 占用了（一個辦公區域内最多隻有一個核心部門），出于工作效率的考慮，微軟希望核心部門之間的移動時間越短越好。對于一個給定的 最大移動時間 kk，大樓的 協同值 定義為：有多少個 核心部門對 之間的移動時間不超過 kk。由于大樓門禁的限制，不可以走出整個大樓，也不可以登上天台思考人生。你可以認為在辦公區域内的移動時間忽略不計，并且在大樓内總是按照最優方案進行移動。

對于一個給定的新大樓設計方案，你能算出方案的協同值麼？

輸入格式

第一行包含兩個正整數 n,k(1\leq k\leq 200020)n,k(1≤k≤200020)，分别表示大樓的棟數以及最大移動時間。

第二行包含 nn 個正整數 h_1,h_2,…,h_n(1\leq h_i\leq 20)h

​1

​​ ,h

​2

​​ ,…,h

​n

​​ (1≤h

​i

​​ ≤20)，分别表示每棟樓的層數。

接下來一行包含一個正整數 mm，表示 核心部門 個數。

接下來 mm 行，每行兩個正整數 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

​​ 層。

輸入資料保證 mm 個核心部門的位置不會重複。

對于簡單版本：1\leq n,m\leq 501≤n,m≤50；

對于中等版本：1\leq n\leq 200000,1\leq m\leq 20001≤n≤200000,1≤m≤2000；

對于困難版本：1\leq n,m\leq 2000001≤n,m≤200000。

輸出格式

輸出一個整數，即整個大樓的 協同值。

樣例解釋

樣例對應題目描述中的圖，核心部門 11 和核心部門 33 之間的距離為 8>78>7，是以不能計入答案。

樣例輸入

5 7

4 1 1 3 1

3

1 4

3 1

4 3

樣例輸出

2

先存一下代碼，線段樹。等過了困難的再回來寫題解。。。

（隻能過中等）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
/******************************************************/
#define LL long long int
#define mem(a,b) memset(a,b,sizeof(a))
#define mid ((l+r)/2)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define L rt<<1
#define R rt<<1|1
#define N 200000+50
#define pow(a) a*a
#define INF 0x3f3f3f3f
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
/*********************************************************/
int n, MAX;
int m;
int dat[N];
struct node{
    int l, r, minn;
};
struct tree{
    int x, high;
}house[N];
node s[N<<];
void build(int l, int r, int rt){
    if (l == r){
        s[rt].minn = dat[l];
        return;
    }
    build(lson);
    build(rson);
    s[rt].minn = (s[L].minn < s[R].minn ? s[L].minn : s[R].minn);
}
int query(int a, int b, int l, int r, int rt){
    if (a <= l&&r <= b){
        return s[rt].minn;
    }
    int m = (l + r) / ;
    int res = , res2 = ;
    if (a <= m)res = query(a, b, lson);
    if (b > m)res2 = query(a, b, rson);
    return min(res, res2);
}
int dis(tree a, tree b){
    return abs(a.x - b.x) + abs(a.high - b.high);
}
int main(){
    scanf("%d%d", &n, &MAX);
    for (int i = ; i <= n; i++){
        scanf("%d", &dat[i]);
    }
    build(, n, );
    scanf("%d", &m);
    for (int i = ; i <= m; i++){
        int a, b;scanf("%d%d", &a, &b);
        house[i].x = a;
        house[i].high = b;
    }
    int cnt = ;
    for (int i = ; i <= m; i++){
        for (int j = +i; j <= m; j++){
            int did = dis(house[i], house[j]);
            if (did > MAX)continue;
            int minn = query(house[i].x, house[j].x, , n, );
            if (minn == min(house[i].high, house[j].high)){
                cnt++;
            }
            else{
                int d = house[i].high + house[j].high + abs(house[i].x - house[j].x)-;
                if (d <= MAX)cnt++;
            }
        }
    }
    cout << cnt  << endl;

}