4071: [Apio2015]巴鄰旁之橋
Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 99 Solved: 45
[Submit][Status][Discuss]
Description
一條東西走向的穆西河將巴鄰旁市一分為二，分割成了區域 A 和區域 B。
每一塊區域沿著河岸都建了恰好 1000000001 棟的建築，每條岸邊的建築都從 0 編號到 1000000000。相鄰的每對建築相隔 1 個單位距離，河的寬度也是 1 個單位長度。區域 A 中的 i 號建築物恰好與區域 B 中的 i 號建築物隔河相對。 城市中有 N 個居民。第 i 個居民的房子在區域 Pi 的 Si 號建築上，同時他的辦公室坐落在 Qi 區域的 Ti 號建築上。一個居民的房子和辦公室可能分布在河的兩岸，這樣他就必須要搭乘船只才能從家中去往辦公室，這種情況讓很多人都覺得不方便。為了使居民們可以開車去工作，政府決定建造不超過 K 座橫跨河流的大橋。 由於技術上的原因，每一座橋必須剛好連接河的兩岸，橋梁必須嚴格垂直於河流，並且橋與橋之間不能相交。當政府建造最多 K 座橋之後，設 Di 表示第 i 個居民此時開車從家裡到辦公室的最短距離。請幫助政府建造橋梁，使得 D1+D2+?+DN 最小。
Input
輸入的第一行包含兩個正整數 K 和 N，分別表示橋的上限數量和居民的數量。
接下來 N 行，每一行包含四個參數：Pi,Si,Qi 和 Ti，表示第 i 個居民的房子在區域 Pi 的 Si 號建築上，且他的辦公室位於 Qi 區域的 Ti 號建築上。
Output
輸出僅為一行，包含一個整數，表示 D1+D2+?+DN 的最小值。
Sample Input
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
Sample Output
24
HINT
子任務
所有數據都保證：Pi 和 Qi 為字符 “A” 和 “B” 中的一個， 0≤Si,Ti≤1000000000，同一棟建築內可能有超過 1 間房子或辦公室（或二者的組合，即房子或辦公室的數量同時大於等於 1）。
子任務 1 （8 分）
K=1
1≤N≤1000
子任務 2 （14 分）
K=1
1≤N≤100000
子任務 3 （9 分）
K=2
1≤N≤100
子任務 4 （32 分）
K=2
1≤N≤1000
子任務 5 （37 分）
K=2
1≤N≤100000
Source
首先如果辦公室和家在同一側，直接將距離加到答案中即可。
那麼辦公室和家不在同一側應該如何解決呢？對於k=1，顯然只需要將橋建在所有位置的中位數即可。
對於k=2，可以發現每個人都會選擇距離家和辦公室中點較近的橋行走。那麼我們就可以按照家和辦公室中點將每個人排序，枚舉分割點，將分割點前後的人按k=1的情況分別處理。問題就轉化動態維護區間中位數了，可以用平衡樹處理。(方法類似bzoj1112)
這道題將所有人按中點排序的思路很好。
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define LL long long
#define MAXN 200100
using namespace std;
int n,root,tot,cnt=0;
LL m,x,y,ans=0,mn,a[MAXN],f1[MAXN],f2[MAXN];
char cx,cy;
struct tree_type
{
int l,r;
LL s,rnd,sum,v,w;
}t[MAXN];
struct node
{
LL x,y;
}b[MAXN];
inline LL read()
{
LL ret=0,flag=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') flag=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
return ret*flag;
}
inline char readch()
{
char ch=getchar();
while (ch!='A'&&ch!='B') ch=getchar();
return ch;
}
inline void solve1()
{
F(i,1,n)
{
cx=readch();x=read();cy=readch();y=read();
if (cx==cy) ans+=abs(x-y);
else a[++cnt]=x,a[++cnt]=y,ans++;
}
sort(a+1,a+cnt+1);
F(i,1,cnt) ans+=abs(a[i]-a[cnt>>1]);
printf("%lld\n",ans);
}
inline bool cmp(node n1,node n2){return n1.x+n1.yx){ins(t[k].l,x);if (t[t[k].l].rnd1){t[k].s--;t[k].w--;t[k].sum-=x;}
else if (!t[k].l||!t[k].r) k=t[k].l+t[k].r;
else if (t[t[k].l].rnd=x){m+=t[t[k].l].sum+(x-ln)*t[k].v;return t[k].v;}
else if (ln>=x) return getans(t[k].l,x);
else{m+=t[t[k].l].sum+t[k].w*t[k].v;return getans(t[k].r,x-ln-t[k].w);}
}
inline LL calc(int q)
{
m=0;
LL tmp=getans(root,q);
LL ret=t[root].sum-m*2;
return ret;
}
inline void solve2()
{
F(i,1,n)
{
cx=readch();x=read();cy=readch();y=read();
if (cx==cy) ans+=abs(x-y);
else b[++cnt].x=x,b[cnt].y=y,ans++;
}
sort(b+1,b+cnt+1,cmp);
f1[0]=root=tot=0;
F(i,1,cnt)
{
ins(root,b[i].x);ins(root,b[i].y);
f1[i]=calc(i);
}
f2[cnt+1]=root=tot=0;
D(i,cnt,1)
{
ins(root,b[i].x);ins(root,b[i].y);
f2[i]=calc(cnt-i+1);
}
mn=f1[0]+f2[1];
F(i,1,cnt) mn=min(f1[i]+f2[i+1],mn);
ans+=mn;
printf("%lld\n",ans);
}
int main()
{
LL ff=read();
n=read();
if (ff==1) solve1();
else solve2();
}
