[BZOJ]4071: [Apio2015]巴邻旁之桥

题解: 首先明确如果处于同一区域时直接统计贡献即可不用过桥

　　　　对k分情况讨论:

　　　　　　当k=1时假设桥的位置是 p 那么

　　　　　　　　$$ sum_{i=1}^n |x_i-p|+|y_i-p| $$

　　　　很显然当对于所有x,y排序后的中位数是最优的选择位置具体证明可以模拟一下

　　　　　　当k=2时假设桥的位置是$p_1$和$p_2$

　　　　　　　　$$ sum_{i=1}^n minleft ( |x_i-p_1|+|y_i-p_1|,|x_i-p_2|+|y_i-p_2| ight ) $$

　　　　　　然后对于一个区间[x,y]我们考虑用其中位数表示为什么能用中位数表示呢我们考虑当桥在区间外面是 $$ 2|p-frac{x+y}{2}| $$ 然后我们就成功得把一个区间用一个点来代替这样的好处就是对于这n个区间用n个点来描述然后对于两座桥的选择我们很直观的可以看出对于中位数排序后的前面部分和后面部分各用一座桥是最优的对于每部分用一座桥的考虑办法就回到了 $ k=1 $的情况问题模型转化成加入2个点动态维护中位数然后倒过来删除2个点维护中位数的模型我们考虑用主席树去做这个题也可以用splay做

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=4e5+10;
const double eps=1e-8;
#define ll long long
const int inf=1e9+10;
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}

int pre[MAXN],ch[MAXN][2],key[MAXN],rt,cnt,sz[MAXN];
ll sum[MAXN];
void Treavel(int x)
{
    if(x)
    {
        Treavel(ch[x][0]);
        printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size=%2d key=%2d sum=%2lld
",x,ch[x][0],ch[x][1],pre[x],sz[x],key[x],sum[x]);
        Treavel(ch[x][1]);
    }
}
void debug(int rp)
{
    printf("root:%d
",rp);
    Treavel(rp);
}
void newnode(int &x,int t,int fa){
    x=++cnt;ch[x][0]=ch[x][1]=0;pre[x]=fa;
    key[x]=sum[x]=t;sz[x]=1;
}

void up(int x){
    sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
    sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+key[x];
}

void rotate(int x,int kind){
    int y=pre[x];
    ch[y][!kind]=ch[x][kind];pre[ch[x][kind]]=y;
    if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;
    pre[x]=pre[y];ch[x][kind]=y;pre[y]=x;
    up(y);
}

void splay(int x,int goal){
    while(pre[x]!=goal){
	if(pre[pre[x]]==goal)rotate(x,ch[pre[x]][0]==x);
	else{
	    int y=pre[x];int kind=ch[pre[y]][0]==y;
	    if(ch[y][kind]==x)rotate(x,!kind),rotate(x,kind);
	    else rotate(y,kind),rotate(x,kind);
	}
    }
    if(goal==0)rt=x;
    up(x);
}

void insert(int &x,int t,int fa){
    if(!x){newnode(x,t,fa);return ;}
    if(t<=key[x])insert(ch[x][0],t,x);
    else insert(ch[x][1],t,x);
    up(x);
}

int find1(int x,int k){
    if(sz[ch[x][0]]+1==k)return x;
    else if(k<=sz[ch[x][0]])return find1(ch[x][0],k);
    else return find1(ch[x][1],k-sz[ch[x][0]]-1);
}

int find2(int x,int k){
    if(key[x]==k)return x;
    else if(k<key[x])return find2(ch[x][0],k);
    else return find2(ch[x][1],k);
}

void erase(int k){
    splay(find2(rt,k),0);
    int t=sz[ch[rt][0]];
    splay(find1(rt,t),0);
    splay(find1(rt,t+2),rt);
    ch[ch[rt][1]][0]=0;
    up(ch[rt][1]);up(rt);
}


void inte(){
    newnode(rt,-inf,0);
    newnode(ch[rt][1],inf,rt);
    up(rt);
}

typedef struct node{
    int x,y;
}node;
bool cmp(node aa,node bb){return aa.x+aa.y<bb.x+bb.y;}
vector<int>vec;
node d[MAXN];
ll num[MAXN];



int main(){
    int op=read();int n=read();
    ll ans=0;int cnt1=0;
    char str1[11],str2[11];int x,y;
    inc(i,1,n){
	scanf("%s %d %s %d",str1,&x,str2,&y);
	if(str1[0]==str2[0])ans+=abs(y-x);
	else d[++cnt1]=(node){x,y};
    }
    ans+=cnt1;
    if(!cnt1){printf("%lld
",ans);return 0;}
    if(op==1){
	inc(i,1,cnt1)vec.pb(d[i].x),vec.pb(d[i].y);
	sort(vec.begin(),vec.end());
	int t=vec[cnt1-1];
	for(int i=0;i<vec.size();i++)ans+=abs(t-vec[i]);
	printf("%lld
",ans);
    }
    else{
	inte();
	sort(d+1,d+cnt1+1,cmp);
	inc(i,1,cnt1){
	    insert(rt,d[i].x,0);splay(cnt,0);
	    insert(rt,d[i].y,0);splay(cnt,0);
	    splay(find1(rt,1),0);splay(find1(rt,i+2),rt);
	    int t=ch[ch[rt][1]][0];
	    ll t1=sum[t];int t2=sz[rt]-2;
	    num[i]=1ll*key[t]*sz[t]-sum[t]+sum[rt]-sum[t]-1ll*(t2-sz[t])*key[t];
	}
	inc(i,1,cnt1-1){
	    erase(d[i].x);
	    erase(d[i].y);
	    splay(find1(rt,1),0);splay(find1(rt,cnt1-i+2),rt);
	    int t=ch[ch[rt][1]][0];
	    ll t1=sum[t];int t2=sz[rt]-2;
	    num[i]+=(1ll*key[t]*sz[t]-sum[t]+sum[rt]-sum[t]-1ll*(t2-sz[t])*key[t]);
	}
	ll minn=1e18;
	inc(i,1,cnt1)minn=min(minn,num[i]);
	printf("%lld
",minn+ans);
    }
    return 0;
}

4071: [Apio2015]巴邻旁之桥

Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 416 Solved: 191
[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 号建筑上。