线段树

【APIO 2015】巴邻旁之桥

Posted by WHZ0325 on 2019-05-02, Viewed times

题目描述

一条东西走向的穆西河将巴邻旁市一分为二，分割成了区域 $A$ 和区域 $B$。

每一块区域沿着河岸都建了恰好 $1000000001$ 栋的建筑，每条岸边的建筑都从 $0$ 编号到 $1000000000$。相邻的每对建筑相隔 $1$ 个单位距离，河的宽度也是 $1$ 个单位长度。区域 $A$ 中的 $i$ 号建筑物恰好与区域 $B$ 中的 $i$ 号建筑物隔河相对。

城市中有 $N$ 个居民。第 $i$ 个居民的房子在区域 $P_i$ 的 $S_i$ 号建筑上，同时他的办公室坐落在 $Q_i$ 区域的 $T_i$ 号建筑上。一个居民的房子和办公室可能分布在河的两岸，这样他就必须要搭乘船只才能从家中去往办公室，这种情况让很多人都觉得不方便。为了使居民们可以开车去工作，政府决定建造不超过 $K$ 座横跨河流的大桥。

由于技术上的原因，每一座桥必须刚好连接河的两岸，桥梁必须严格垂直于河流，并且桥与桥之间不能相交。

当政府建造最多 $K$ 座桥之后，设 $D_i$ 表示第 $i$ 个居民此时开车从家里到办公室的最短距离。请帮助政府建造桥梁，使得 $D_1+D_2+\dots +D_N$ 最小。

$K=2$，$1\le N\le 100000$，$P_i$ 和 $Q_i$ 为字符 “A” 和 “B” 中的一个，$0\le S_i,T_i\le 1000000000$，同一栋建筑内可能有超过 $1$ 间房子或办公室（或二者的组合，即房子或办公室的数量同时大于等于 $1$）。

算法分析

当 $K=1$ 时很好算，列一下式子就会发现桥梁取在所有 $S_i$ 和 $T_i$ 的中位数处即可，这是个经典模型。

当 $K=2$ 时，我们可以发现，若 $S_i,T_i$ 之间有桥，则会通过这座桥，否则每个居民一定会选择距离自己两个端点最近的桥通过，也是距离两个端点所连成线段中点最近的桥。

按 $S_i,T_i$ 的中点对居民排序，则选择两座桥的居民分别形成一段连续的区间，枚举两个区间的分界点分别求出两边桥的位置即可。

问题转化为动态维护中位数以及中位数到其它点的距离，可以用权值线段树实现（离散化或动态开点）。

时间复杂度为 $O(nlog_2n)$。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 100005
typedef long long int ll;
struct SGT {
    int sz[N<<3];ll sum[N<<3];
    SGT() {memset(sz,0,sizeof(sz));memset(sum,0,sizeof(sum));}
    void modify(int o,int l,int r,int x,int d,int s) {
        if(l==r) {sz[o]+=d;sum[o]+=d*s;}
        else {
            int mid=(l+r)>>1;
            if(x<=mid) modify(o<<1,l,mid,x,d,s);
            else if(mid+1<=x) modify(o<<1|1,mid+1,r,x,d,s);
            sz[o]=sz[o<<1]+sz[o<<1|1];sum[o]=sum[o<<1]+sum[o<<1|1];
        }
    }
    int query(int o,int l,int r,int k) {
        int mid=(l+r)>>1;
        if(l==r) return mid;
        if(k<=sz[o<<1]) return query(o<<1,l,mid,k);
        return query(o<<1|1,mid+1,r,k-sz[o<<1]);
    }
    int querySz(int o,int l,int r,int ql,int qr) {
        if(ql<=l&&r<=qr) return sz[o];
        int mid=(l+r)>>1,ans=0;
        if(ql<=mid) ans+=querySz(o<<1,l,mid,ql,qr);
        if(mid+1<=qr) ans+=querySz(o<<1|1,mid+1,r,ql,qr);
        return ans;
    }
    ll querySum(int o,int l,int r,int ql,int qr) {
        if(ql<=l&&r<=qr) return sum[o];
        int mid=(l+r)>>1;ll ans=0;
        if(ql<=mid) ans+=querySum(o<<1,l,mid,ql,qr);
        if(mid+1<=qr) ans+=querySum(o<<1|1,mid+1,r,ql,qr);
        return ans;
    }
} sgt[2];
struct type {int s,t;} loc[N];int cnt=0;
inline bool cmp(const type &a,const type &b) {return a.s+a.t<b.s+b.t;}
int h[N<<1],sz=0;inline int id(int x) {return std::lower_bound(h,h+sz,x)-h+1;}
int main() {
    int k,n;scanf("%d%d",&k,&n);
    if(k==1) {
        ll ans=0;
        for(register int i=1;i<=n;++i) {
            char p[2],q[2];int s,t;scanf("%s%d%s%d",p,&s,q,&t);
            if(p[0]==q[0]) ans+=abs(t-s);
            else {h[sz++]=s;h[sz++]=t;++ans;}
        }
        std::sort(h,h+sz);
        for(register int i=0;i<sz;++i) ans+=abs(h[sz/2]-h[i]);
        printf("%lld\n",ans);
    }
    else {
        ll ans=0;
        for(register int i=1;i<=n;++i) {
            char p[2],q[2];int s,t;scanf("%s%d%s%d",p,&s,q,&t);
            if(p[0]==q[0]) ans+=abs(t-s);
            else {
                h[sz++]=s;h[sz++]=t;
                loc[cnt++]=(type){p[0]<q[0]?s:t,p[0]<q[0]?t:s};
            }
        }
        std::sort(loc,loc+cnt,cmp);
        std::sort(h,h+sz);sz=std::unique(h,h+sz)-h;
        for(register int i=0;i<cnt;++i) {
            sgt[1].modify(1,1,sz,id(loc[i].s),1,loc[i].s);
            sgt[1].modify(1,1,sz,id(loc[i].t),1,loc[i].t);
        }
        ll res=0x3f3f3f3f3f3f3f3fLL;
        for(register int i=0;i<cnt;++i) {
            sgt[0].modify(1,1,sz,id(loc[i].s),1,loc[i].s);
            sgt[0].modify(1,1,sz,id(loc[i].t),1,loc[i].t);
            sgt[1].modify(1,1,sz,id(loc[i].s),-1,loc[i].s);
            sgt[1].modify(1,1,sz,id(loc[i].t),-1,loc[i].t);
            int ls=sgt[0].query(1,1,sz,i+1),rs=sgt[1].query(1,1,sz,cnt-i-1);
            ll cur=(ll)sgt[0].querySz(1,1,sz,1,ls)*h[ls-1]-sgt[0].querySum(1,1,sz,1,ls);
            cur+=sgt[0].querySum(1,1,sz,ls,sz)-(ll)sgt[0].querySz(1,1,sz,ls,sz)*h[ls-1];
            cur+=(ll)sgt[1].querySz(1,1,sz,1,rs)*h[rs-1]-sgt[1].querySum(1,1,sz,1,rs);
            cur+=sgt[1].querySum(1,1,sz,rs,sz)-(ll)sgt[1].querySz(1,1,sz,rs,sz)*h[rs-1];
            res=std::min(res,cur+cnt);
        }
        printf("%lld\n",(res^0x3f3f3f3f3f3f3f3fLL)?ans+res:ans);
    }
    return 0;
}