UOJ #112. 【APIO2015】Palembang Bridges 線段樹

題意

有兩排建築，中間有一條河，給你每個人的起點和終點，現在你需要建k條橋，使得所有人起點到終點的距離最小，k=1或者2，n=100000

分析

先把同在一邊的起點和終點給去掉

首先k=1的時候，很容易想到每個人都要過橋，然後每個人的距離就是

|s−p|+|t−p| | s − p | + | t − p |

p是橋的位置，s和t是起點和終點的位置，那麼就是上式的貢獻

再很容易發現這其實就是一個中位數模型

k=2的時候，我們考慮一個類似上面的做法

首先一個結論：每個點會選擇的橋肯定是離 s+t2最近的 s + t 2 最 近 的

然後我們可以按照 s+t s + t 來排個序，然後枚舉斷點，斷點左邊的選左邊的橋，斷點右邊的選右邊的橋

然後就轉化為一條橋的形式了

斷點左邊維護一顆權值線段樹，斷點右邊也維護一顆，就可以支援找中位數啦

代碼

#include <bits/stdc++.h>
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll inf = e9;
const ll N = ;
const ll lg = ;
inline ll read()
{
  ll p=; ll f=; char ch=getchar();
  while(ch<'0' || ch>'9'){if(ch=='-') f=-; ch=getchar();}
  while(ch>='0' && ch<='9'){p=p*10+ch-'0'; ch=getchar();}
  return p*f;
}

ll lc[N*lg*2],rc[N*lg*2],c[N*lg*2],s[N*lg*2]; ll rt[],tot;

void link(ll &u,ll L,ll R,ll k,ll cc)
{
  if(!u) u=++tot;
  if(L==R){c[u] += cc; s[u] += L * cc; return ;}
  ll mid=(L+R)>>;
  if(k<=mid) link(lc[u],L,mid,k,cc);
  else link(rc[u],mid+,R,k,cc);
  c[u] = c[lc[u]] + c[rc[u]];
  s[u] = s[lc[u]] + s[rc[u]];
}

ll qry(ll u,ll L,ll R,ll k)
{
  if(L==R) return L;
  ll mid=(L+R)>>;
  if(c[lc[u]] >= k) return qry(lc[u],L,mid,k);
  else return qry(rc[u],mid+,R,k-c[lc[u]]);
}

pair<ll,ll> qry2(ll u,ll L,ll R,ll l,ll r) // c s
{
  if(l>r) return MP(,);
  if(L == l && R == r) return MP(c[u],s[u]);
  ll mid = (L+R)>>;
  if(r<=mid) return qry2(lc[u],L,mid,l,r);
  else if(l>mid) return qry2(rc[u],mid+,R,l,r);
  else
  {
    pii ls = qry2(lc[u],L,mid,l,mid);
    pii rs = qry2(rc[u],mid+,R,mid+,r);
    return MP(ls.first + rs.first , ls.second + rs.second);
  }
}

pair<ll,ll> q[N];

ll k,n; ll h[N],x[N],y[N];

int main()
{
  k = read(); n = read(); ll ans = ,maxx;
  ll nn = ; for(ll i=;i<=n;i++)
  {
    char ch1,ch2; ll xx,yy;
    scanf("\n%c%lld\n%c%lld",&ch1,&xx,&ch2,&yy);
    if(ch1 == ch2) ans += abs(xx-yy);
    else ans++ , nn++, x[nn] = xx,y[nn] = yy , h[nn*2-] = xx,h[nn*2] = yy;
  }n = nn;
  if(k == )
  {
    sort(h+,h+*n+); ll mid = h[n];
    for(ll i=;i<=*n;i++) ans = ans + abs(mid - h[i]);
    printf("%lld\n",ans);
  }
  else
  {
    for(ll i=;i<=n;i++) q[i] = MP(x[i] + y[i] , i);
    sort(q+,q+n+); rt[] = rt[] = tot = ;
    for(ll i=;i<=n;i++){link(rt[],,inf,x[i],); link(rt[],,inf,y[i],);}

    ll ls = ; ll rs = *n; ll mid = qry(rt[],,inf,rs>>); ll sum = ;
    pii lmid = qry2(rt[],,inf,,mid); sum+=mid * lmid.first - lmid.second;
    pii rmid = qry2(rt[],,inf,mid+,inf); sum+=rmid.second - mid * rmid.first;
    maxx = sum; // printf("%lld\n",sum + ans);

    for(ll i=;i<=n;i++)
    {
      ll pos = q[i].second;
      link(rt[],,inf,x[pos],-); link(rt[],,inf,y[pos],-);
      link(rt[],,inf,x[pos],); link(rt[],,inf,y[pos],);
      ls+=; rs-=;

      mid = qry(rt[],,inf,ls>>); sum = ;
      lmid = qry2(rt[],,inf,,mid); sum+=mid * lmid.first - lmid.second;
      rmid = qry2(rt[],,inf,mid+,inf); sum+=rmid.second - mid * rmid.first;


      mid = qry(rt[],,inf,rs>>);
      lmid = qry2(rt[],,inf,,mid); sum+=mid * lmid.first - lmid.second;
      rmid = qry2(rt[],,inf,mid+,inf); sum+=rmid.second - mid * rmid.first;

      maxx = min(maxx , sum); // printf("%lld\n",sum + ans);
    }
    printf("%lld\n",maxx + ans);
  }
  return ;
}