题意
描述
有(M)条河，每条河的两边有居民点，所以共有(M+1)排居名点;
如果要从一排居名点到另一排相邻的居民点需要过河；
现在有(n)个人，每个人的起点坐标是((P_{i},S_{i}))，终点((Q_{i},T_{i}))；
你可以在每条河上修建一座桥，过河必须通过桥；
相邻居民点距离为(1)，不考虑过河的时间；
问(n)个人到终点的路径之和最小是多少；
范围
(1 le N , M le 10^5 , 1 le S_{i} ,T_{i} le 10^9 , 1 le P_{i},Q_{i} le M+1)
题解：
-
答案一定在(S_{i})或者(T_{i})上(我不会证明。。。)
-
考虑所有的可行位置为(a_{i})；
-
一条路径的贡献可以放到每座桥上，分为两部分：
- 经过桥(i 和 i - 1) (b_{i})次；
- 从(a_{k})到桥(i)，(a_{k})为某个起点或者终点，设(g_i(j) = sum_{k}|a_{k}-a_{j}|)；
[egin{align} f_{1,j} &= g_{1}(j) &(i=1) \ f_{i,j} &= min { f_{i-1,k} + b_{i} |a_{i}-a_{k}| + g_{i}(j) } &(i gt 1) \ end{align} ] -
所以得到一个(O(n^2m))的(dp)，可以用单调队列简单优化到(O(nm))；
-
(g_{1})一定是凸函数，所以(f_{1})一定是凸的，同时由于凸函数对加法封闭，所以直接考虑转移前半部分：
-
考虑在(f_{i-1})上找到两个斜率为 (-b_{i}) 和(b_{i})的点设为(j1和j2)
-
[f_{i,j} = g_{i}(j） + egin{cases} &f_{i-1,j1} &+& b_{i} |a_{i}-a_{j1}| &(j lt j1)\ &f_{i-1,j} &+ &b_{i} |a_{i}-a_{j}| &(j1 le j le j2)\ &f_{i-1,j2} &+ &b_{i} |a_{i}-a_{j2}| &(j2 lt j)\ end{cases} ]
-
(分析绝对值简单比较就可以得到)
-
所以(f_{i-1} o f_{i})就是区间赋值一次函数，区间加一次函数，所以(f_{i})仍然是凸的；
-
用线段树或者(set)维护差分即可；
-
注意要另外维护一下(f_{i,1}) ;
#include<bits/stdc++.h> #define pb push_back #define mk make_pair #define ls (k<<1) #define rs (k<<1|1) #define ll long long #define inf 1e18 #define il inline using namespace std; const int N=100010; int n,m,tot,sub[N<<1],P[N],S[N],Q[N],T[N]; vector<int>a[N]; ll B,sum[N],b[N],ans; il char gc(){ static char*p1,*p2,s[1000000]; if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin); return(p1==p2)?EOF:*p1++; } il int rd(){ int x=0;char c=gc(); while(c<'0'||c>'9')c=gc(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc(); return x; } ll s[N<<3],d[N<<3],dr[N<<3],ly1[N<<3],ly2[N<<3]; il void build(int k,int l,int r){ ly2[k]=inf; if(l==r){ if(!l)d[l]=-inf; if(l==tot)d[l]=inf; return; } int mid=l+r>>1; build(ls,l,mid); build(rs,mid+1,r); } il void mfy1(int k,int l,int r,ll x){ d[k]+=x;dr[k]+=x;ly1[k]+=x; s[k]+=(sub[r+1]-sub[l])*x; } il void mfy2(int k,int l,int r,ll x){ d[k]=dr[k]=ly2[k]=x;ly1[k]=0; s[k]=(sub[r+1]-sub[l])*x; } il void pushup(int k,int l,int r){ s[k]=s[ls]+s[rs]; dr[k]=dr[rs]; } il void pushdown(int k,int l,int r){ if(ly2[k]!=inf){ int mid=l+r>>1; mfy2(ls,l,mid,ly2[k]); mfy2(rs,mid+1,r,ly2[k]); ly2[k]=inf; } if(ly1[k]){ int mid=l+r>>1; mfy1(ls,l,mid,ly1[k]); mfy1(rs,mid+1,r,ly1[k]); ly1[k]=0; } } void update1(int k,int l,int r,int x,int y,ll v){ if(l==x&&r==y){mfy1(k,l,r,v);return;} int mid=(l+r)>>1; pushdown(k,l,r); if(y<=mid)update1(ls,l,mid,x,y,v); else if(x>mid)update1(rs,mid+1,r,x,y,v); else update1(ls,l,mid,x,mid,v),update1(rs,mid+1,r,mid+1,y,v); pushup(k,l,r); } void update2(int k,int l,int r,int x,int y,ll v){ if(l==x&&r==y){mfy2(k,l,r,v);return;} int mid=(l+r)>>1; pushdown(k,l,r); if(y<=mid)update2(ls,l,mid,x,y,v); else if(x>mid)update2(rs,mid+1,r,x,y,v); else update2(ls,l,mid,x,mid,v),update2(rs,mid+1,r,mid+1,y,v); pushup(k,l,r); } int query1(int k,int l,int r,ll x){ if(l==r)return l; int mid=l+r>>1; pushdown(k,l,r); if(dr[ls]>=x)return query1(ls,l,mid,x); else return query1(rs,mid+1,r,x); } ll query2(int k,int l,int r,int x,int y){ if(l==x&&r==y)return s[k]; pushdown(k,l,r); int mid=l+r>>1; if(y<=mid)return query2(ls,l,mid,x,y); else if(x>mid)return query2(rs,mid+1,r,x,y); else return query2(ls,l,mid,x,mid)+query2(rs,mid+1,r,mid+1,y); } il void Update1(int cur){ sort(a[cur].begin(),a[cur].end()); int sz=a[cur].size(); a[cur].push_back(tot); ans+=sum[cur]; for(int i=0,now=1,lst=1;i<=sz;++i){ lst=now,now=a[cur][i]; int x=2*i-sz; if(lst<now)update1(1,0,tot,lst,now-1,x); } } il void Update2(int cur){ int x1=query1(1,0,tot,-b[cur]); int x2=query1(1,0,tot,b[cur]); if(1<x1){ ans=ans+query2(1,0,tot,1,x1-1)+1ll*(sub[x1]-sub[1])*b[cur]; update2(1,0,tot,1,x1-1,-b[cur]); } if(x2<tot){update2(1,0,tot,x2,tot-1,b[cur]);} } int main(){ freopen("bridge.in","r",stdin); freopen("bridge.out","w",stdout); n=rd();m=rd(); for(int i=1;i<=n;++i){ P[i]=rd()-1;S[i]=rd();Q[i]=rd()-1;T[i]=rd(); if(P[i]>Q[i])swap(P[i],Q[i]),swap(S[i],T[i]); sub[++tot]=S[i],sub[++tot]=T[i]; } sub[++tot]=1; sort(sub+1,sub+tot+1); tot=unique(sub+1,sub+tot+1)-sub-1; for(int i=1;i<=n;++i){ S[i]=lower_bound(sub+1,sub+tot+1,S[i])-sub; T[i]=lower_bound(sub+1,sub+tot+1,T[i])-sub; int l=P[i],r=Q[i]; if(l==r){ans+=abs(sub[T[i]]-sub[S[i]]);continue;} a[l+1].pb(S[i]);sum[l+1]+=sub[S[i]]-1; a[r].pb(T[i]);sum[r]+=sub[T[i]]-1; b[l+2]++,b[r+1]--; } build(1,0,tot); Update1(1); for(int i=2;i<=m;++i){ b[i]+=b[i-1]; Update2(i); Update1(i); } int pos=query1(1,0,tot,0); if(pos>1)ans+=query2(1,0,tot,1,pos-1); printf("%lld ",ans); return 0; }//这是fxy写的set; #pragma GCC optimize(3) #include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<cmath> #include<stack> #include<set> #include<algorithm> #define rg register #define ll long long #define LDB long double #define ull unsigned long long #define view(i,x) for(rg int i=hd[x];i!=-1;i=e[i].nt) #define go(i,x,a) for(rg int i=a;i<x;i++) #define inf 0x3f3f3f3f #define INF 0x7fffffff using namespace std; const int maxn=1e5+5; int n,m,f[maxn],l,r; vector<int>g[maxn]; multiset<int>s,t; ll ans=0; inline int rd(){ int ret=0,af=1; char gc=getchar(); while(gc < '0' || gc > '9'){ if(gc=='-') af=-af; gc=getchar(); } while(gc >= '0' && gc <= '9') ret=ret*10+gc-'0',gc=getchar(); return ret*af; } inline void update(int x){ if(l <= x && x <= r){ s.insert(x); t.insert(x); l=r=x; return ; } if(x < l){ ans+=l-x; s.erase(s.find(l)); if(s.find(l) == s.end()){ r=l; l=s.size() > 1 ? *(--s.end()):x; }else r=l; s.insert(x); s.insert(x); t.insert(r); return ; } if(x > r){ ans+=x-r; t.erase(t.find(r)); if(t.find(r) == t.end()){ l=r; r=t.size() > 1 ? *(t.begin()):x; }else l=r; t.insert(x); t.insert(x); s.insert(l); } } int main(){ //#ifndef ONLINE_JUDGE freopen("bridge.in","r",stdin); freopen("bridge.out","w",stdout); //#endif n=rd(); m=rd(); int p,q,a,b; go(i,n+1,1){ p=rd(); a=rd(); q=rd(); b=rd(); if(p == q){ ans+=abs(a-b); continue; } if(p > q) swap(p,q),swap(a,b); g[p].push_back(a); g[q-1].push_back(b); if(p+1 <= q-1) f[p+1]++,f[q]--; } go(i,m+1,1) f[i]+=f[i-1]; l=0; r=inf; s.insert(l); t.insert(r); go(i,m+1,1){ if(i > 1){ while(s.size() > f[i]) s.erase(s.begin()); while(t.size() > f[i]) t.erase(--t.end()); if(s.size() == 0) s.insert(0); if(t.size() == 0) t.insert(inf); } go(j,g[i].size(),0) update(g[i][j]); } printf("%lld",ans); return 0; }