Description
N,M<=100000,S,T<=1e9
Solution
首先可以感受一下，我们把街道看成一行，那么只有给出的2n个点的纵坐标是有用的，于是我们可以将坐标离散化至O(n)级别。
显然出发地和目的地的地位是相同的，因此我们强制要求从编号小的街道走向标号大的街道。
我们考虑一个朴素的DP，记\(F[i][j]\)表示当前转移到了第i行，连接第i-1行和第i行的桥梁位于位置j
枚举上一行的桥梁在哪里，我们可以得到一个大概的转移式子\(F[i][j]=S[i][j]+min(F[i-1][k]+c\left|j-k\right|)\)，其中\(S[i][j]\)为只与i，j有关的一个常数，可以理解成当前行的目的地到达情况和上一行的出发情况，c为经过这个桥的人数，可以提前算出。
直接转移是\(O(N^2M)\)的，加上一些类似前缀最小值优化的东西可以做到\(O(NM)\)
考虑继续发掘性质。
我们设出发地和目的地为关键点
容易看出，对于一行的某个关键点，它对整一行的答案影响可以写成一个斜率为-1的一次函数和一个斜率为1的一次函数，它显然是个斜率不降的函数（下凸壳）。
便于维护，我们对于每个j都记一个一次函数\(k_jx+b_j\)，表示\(f[i][j-1]\)与\(f[i][j]\)的连线的方程，显然交点处同时满足两个方程。
由于两个下凸的函数之和仍然是一个下凸的函数，因此只考虑关键点的影响时它总是个凸函数，我们只需要支持区间加一次函数即可。
考虑行间转移，\(F[i][j]=S[i][j]+min(F[i-1][k]+c\left|j-k\right|)\),\(S[i][j]\)就是关键点的贡献，我们只考虑\(min(F[i-1]k]+c\left|j-k\right|)\)，我们找到一个最小的\(x_1\)满足\(k_{x_1+1}\geq -c\),最大的\(x_2\)满足\(k_{x_2}\leq c\)
\[min(F[i-1][k]+c|k-x|)=
\left\{
\begin{array}{ll}
F[i-1][x_1]+c*x_1-c*x & x<x_1 \\
F[i-1][x] & x_1\leq x\leq x_2 \\
F[i-1][x_2]-c*x_2+c*x &x>x_2
\end{array}\right.
\]
\left\{
\begin{array}{ll}
F[i-1][x_1]+c*x_1-c*x & x<x_1 \\
F[i-1][x] & x_1\leq x\leq x_2 \\
F[i-1][x_2]-c*x_2+c*x &x>x_2
\end{array}\right.
\]
容易发现它还是个凸函数，相当于在原来的凸函数两边斜率绝对值大于c的部分修改掉。
这样我们只需要支持区间加、区间赋值为一次函数，以及查找某个斜率
线段树维护即可。
时间复杂度\(O(n\log n)\)
Code
#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define N 200005
#define LL long long
using namespace std;
int n,m,r,a[N][4],l,dc[N],le;
LL sum[N],ans,wz[N];
//lisanhua
struct node
{
int x,y,p;
}d[N],ds[2][N];
bool cmp1(node x,node y)
{
return x.y<y.y;
}
bool cmp2(node x,node y)
{
return (x.x<y.x)||(x.x==y.x&&x.y<y.y);
}
//segment tree
#define M 400005
int t[M][2],n1;
LL sp[M][2],mxk[M],lz[M][2],lc[M][2];
bool bc[M];
void build(int k,int l,int r)
{
if(l==r) return;
int mid=(l+r)>>1;
t[k][0]=++n1,build(t[k][0],l,mid);
t[k][1]=++n1,build(t[k][1],mid+1,r);
}
int opx,opy;
LL opk,opb;
inline void upd(int k,LL &x,LL &y)
{
sp[k][0]+=x,sp[k][1]+=y;
lz[k][0]+=x,lz[k][1]+=y;
mxk[k]+=x;
}
inline void upc(int k,LL &x,LL &y)
{
lz[k][0]=lz[k][1]=0;
sp[k][0]=x,sp[k][1]=y;
lc[k][0]=x,lc[k][1]=y;
mxk[k]=x;
bc[k]=1;
}
inline void down(int k)
{
if(bc[k])
{
upc(t[k][0],lc[k][0],lc[k][1]);
upc(t[k][1],lc[k][0],lc[k][1]);
lc[k][0]=lc[k][1]=0;bc[k]=0;
}
if(lz[k][0]||lz[k][1]) upd(t[k][0],lz[k][0],lz[k][1]),upd(t[k][1],lz[k][0],lz[k][1]);
lz[k][0]=lz[k][1]=0;
}
inline void up(int k)
{
mxk[k]=max(mxk[t[k][0]],mxk[t[k][1]]);
}
void add(int k,int l,int r)
{
if(opx>opy||opx>r||opy<l) return;
if(opx<=l&&r<=opy) upd(k,opk,opb);
else
{
int mid=(l+r)>>1;down(k);
add(t[k][0],l,mid),add(t[k][1],mid+1,r);
up(k);
}
}
void op_add(int p,int q,LL x,LL y) {opx=p,opy=q,opk=x,opb=y;add(1,1,r);}
void reset(int k,int l,int r)
{
if(opx>opy||opx>r||opy<l) return;
if(opx<=l&&r<=opy) upc(k,opk,opb);
else
{
int mid=(l+r)>>1;down(k);
reset(t[k][0],l,mid),reset(t[k][1],mid+1,r);
up(k);
}
}
void op_reset(int p,int q,LL x,LL y) {opx=p,opy=q,opk=x,opb=y;reset(1,1,r);}
int find(int k,int l,int r)
{
if(l==r) return (sp[k][0]>=opk)?l:l+1;
int mid=(l+r)>>1;down(k);
return (mxk[t[k][0]]>=opk)?find(t[k][0],l,mid):find(t[k][1],mid+1,r);
}
int op_find(int x) {opk=x;return find(1,1,r);}
LL get(int k,int l,int r)
{
if(l==r) return (sp[k][0]*wz[l]+sp[k][1]);
int mid=(l+r)>>1;down(k);
return(opx<=mid)?get(t[k][0],l,mid):get(t[k][1],mid+1,r);
}
LL op_get(int x) {opx=x;return get(1,1,r);}
LL smi;
void walk(int k,int l,int r)
{
if(l==r) smi=min(smi,sp[k][0]*wz[l]+sp[k][1]);
else
{
int mid=(l+r)>>1;down(k);
walk(t[k][0],l,mid),walk(t[k][1],mid+1,r);
}
}
//main
int main()
{
cin>>n>>m;
ans=0,smi=1e18;
fo(i,1,n)
{
scanf("%d%d%d%d",&a[i][0],&a[i][1],&a[i][2],&a[i][3]);
if(a[i][0]>a[i][2]) swap(a[i][0],a[i][2]),swap(a[i][1],a[i][3]);
if(a[i][0]==a[i][2]) ans+=abs(a[i][1]-a[i][3]);
else
{
sum[a[i][0]+1]++,sum[a[i][2]]--;
d[++l]=(node){a[i][0],a[i][1],0};
d[++l]=(node){a[i][2],a[i][3],1};
}
}
fo(i,1,m+1) sum[i]=sum[i-1]+sum[i];
sort(d+1,d+l+1,cmp1);
fo(i,1,l)
{
if(i==1||d[i].y!=d[i-1].y) r++,wz[r]=d[i].y;
dc[i]=r;
}
int lf[2]={0,0};
fo(i,1,l) d[i].y=dc[i],ds[d[i].p][++lf[d[i].p]]=d[i];
sort(ds[0]+1,ds[0]+lf[0]+1,cmp2);
sort(ds[1]+1,ds[1]+lf[1]+1,cmp2);
n1=1;
r=max(r,1);
build(1,1,r);
int lx[2]={0,0};
fo(p,0,1)
for(lx[p]=1;lx[p]<=lf[p]&&ds[p][lx[p]].x<=1+p;lx[p]++)
{
op_add(1,ds[p][lx[p]].y,-1,wz[ds[p][lx[p]].y]);
op_add(ds[p][lx[p]].y+1,r,1,-wz[ds[p][lx[p]].y]);
}
fo(i,3,m+1)
{
int w=op_find(-sum[i-1])-1;
op_reset(1,w,-sum[i-1],sum[i-1]*(LL)wz[w]+op_get(w));
w=op_find(sum[i-1]+1)-1;
op_reset(w+1,r,sum[i-1],-(LL)wz[w]*sum[i-1]+op_get(w));
fo(p,0,1)
for(;lx[p]<=lf[p]&&ds[p][lx[p]].x<=i-1+p;lx[p]++)
{
op_add(1,ds[p][lx[p]].y,-1,wz[ds[p][lx[p]].y]);
op_add(ds[p][lx[p]].y+1,r,1,-wz[ds[p][lx[p]].y]);
}
}
walk(1,1,r);
printf("%lld\n",ans+smi);
}