【IOI2016】railroad

题面

http://uoj.ac/problem/236

题解

upd2019.8.14：本来想重写一遍的，后来发现我应该理解了，就咕了。

把速度看成点，在过山车的始终速度间连有向边，加速免费，减速一定要走边。

用【Segment and Points】的性质，把一定需要的加速边和减速边补出来。

此时，原图还可以不连通，但因为这是一个欧拉通路，所以起点和终点的度数是可以为奇数的。

把一个欧拉回路看成一个点，直接在原图上求最小生成树，求出来是保证有且仅有起点终点的度数为奇数的

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include"railroad.h"
#define LL long long
#define ri register int
#define N 200050
using namespace std;

int n,m,S[N],T[N],f[N];
int dct[N<<1];

struct edge {
  int u,v,l;
  bool operator < (const edge &rhs) const {
    return l<rhs.l;
  }
} e[N<<1];

int ton[N<<1];

int findroot(int x) {
  if (f[x]==x) return x;
  return f[x]=findroot(f[x]);
}

long long plan_roller_coaster(vector<int> s,vector<int> t) {
  int n=s.size();LL ans=0;
  int top=0;
  for (ri i=0;i<n;i++) dct[++top]=s[i];
  for (ri i=0;i<n;i++) dct[++top]=t[i];
  dct[++top]=-1000000100; dct[++top]=1000000100;
  sort(dct+1,dct+top+1); top=unique(dct+1,dct+top+1)-dct-1;
  for (ri i=0;i<n;i++) s[i]=lower_bound(dct+1,dct+top+1,s[i])-dct;
  for (ri i=0;i<n;i++) t[i]=lower_bound(dct+1,dct+top+1,t[i])-dct;
  ton[2]=-1; ton[top]=1;
  for (ri i=1;i<=top;i++) f[i]=i;
  for (ri i=0;i<n;i++) ton[s[i]+1]++,ton[t[i]+1]--;
  for (ri i=0;i<n;i++) f[findroot(s[i])]=f[findroot(t[i])];
  for (ri i=1;i<=top;i++) ton[i]+=ton[i-1];
  for (ri i=2;i<=top;i++) {
    if (ton[i]==0) continue;
    if (ton[i]>0) ans+=ton[i]*1LL*(dct[i]-dct[i-1]);
    f[findroot(i)]=findroot(i-1);
  }
  int m=0;
  for (ri i=2;i<top-1;i++) if (findroot(i)!=findroot(i+1)) e[++m]=(edge){i,i+1,dct[i+1]-dct[i]};
  sort(e+1,e+m+1);
  for (ri i=1;i<=m;i++) if (findroot(e[i].u)!=findroot(e[i].v)) f[findroot(e[i].u)]=findroot(e[i].v),ans+=e[i].l;
  return ans;
}