题解：P10630 [JOI Open 2017] 推土机 / Bulldozer
masterhuang
·
·
题解
平面上有 N 个点，点 i 位于 (X_i, Y_i)，权值为非零整数 W_i（可能为负数）。
在平面上画两条平行线，所得的总价值为平行线之间（压线也算）所有点的权值之和。求总价值的最大值。
先考虑平行线的斜率，初步猜测为是两点间的斜率。
但是稍加观察我们发现应该是两点间斜率 \pm\,\varepsilon 比较准确，因为可能有若干点共线的情况。
设两点间斜率从小到大依次为：$k_1,k_2,\cdots,k_m$。我们依次考虑斜率在 $(-\infty,k_1),[k_1,k_2),\cdots,[k_{m-1},k_m),[k_m,\infty)$ 的时候的答案。
显然在题目条件下，这整个区间都是等价的。
---
然后我们尝试描述被两条平行线夹在中间的点。
考虑和平行线垂直的任意一条直线，然后考虑所有点在这条线上的投影（垂直和**投影的垂直**，应该懂为啥了吧），如下图：
于是我们发现相当于投影上的一个区间，并且显然是双射的。
或者说，把这条直线顺次做扫描，扫描到的点依次加入一个序列，这东西对应序列的区间。
然后维护出区间，就转换为最大子段和问题。
---
然后我们考虑斜率改变的时候，序列会怎么改变。
初始由于斜率 $-\infty$，序列就是按照 $(x,y)$ 坐标这个二元组排序的结果。
一样的，只有在两个点连线的斜率**被扫描后**，这两点在序列中的位置才会交换。
直接扫描，线段树维护最大子段和，复杂度 $O(N^2\log N)$。
注意按斜率排序的时候，如果斜率相等，`pair` $(i,j)$ 小的要在前面，其中 $(i,j)$ 是形成此斜率的两点。
---
---
我把这归类为**平几维护相对顺序**的问题。类似题目 [P4864](https://www.luogu.com.cn/problem/P4864)，还有 **nfls《直线交点》**。
上面两题说的事情是：按 $x$ 坐标做扫描线，维护直线在 $x=X$ 时的相对顺序（例如求 $\texttt{kth}$）。
可以把直线看成序列中的元素，初始按照斜率排序（$x=-\infty$ 的值）。
然后每扫到一个交点，交换对应两条线在序列中的位置，就维护了相对顺序。
交换次数为 $O(n^2)$。
- 这题其实不太一样，是把点投影到直线上，要维护点的相对顺序。
```cpp
//洛谷 P10630
//https://www.luogu.com.cn/problem/P10630
#include<bits/stdc++.h>
#define LL long long
#define P pair<LL,LL>
#define x first
#define y second
#define ls w<<1
#define rs w<<1|1
#define lw l,m,ls
#define rw m+1,r,rs
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=2005;
int n,m,p[N];LL ans;
struct E{P t;LL w;}A[N];
struct F{P t,id;}B[N*N/2];
inline LL operator*(P A,P B){return A.x*B.y-A.y*B.x;}
struct T{LL sl,sr,s,mx;}a[N<<2];
inline void ins(T &A,int t){A={t,t,t,t};}
inline void pu(int w)
{
a[w].sl=max(a[ls].s+a[rs].sl,a[ls].sl);
a[w].sr=max(a[rs].s+a[ls].sr,a[rs].sr);
a[w].s=a[ls].s+a[rs].s;
a[w].mx=max({a[ls].mx,a[rs].mx,a[ls].sr+a[rs].sl});
}
void bd(int l=1,int r=n,int w=1)
{
if(l==r) return ins(a[w],A[l].w);
int m=(l+r)>>1;bd(lw),bd(rw),pu(w);
}
void upd(int p,LL t,int l=1,int r=n,int w=1)
{
if(l==r) return ins(a[w],t);int m=(l+r)>>1;
p<=m?upd(p,t,lw):upd(p,t,rw);pu(w);
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;
for(int i=1;i<=n;i++) cin>>A[i].t.x>>A[i].t.y>>A[i].w,p[i]=i;
sort(A+1,A+1+n,[](E A,E B){return A.t<B.t;});bd();
for(int i=1;i<=n;i++) for(int j=1;j<i;j++)
B[++m]={{A[i].t.x-A[j].t.x,A[i].t.y-A[j].t.y},{i,j}};
sort(B+1,B+1+m,[](F A,F B){
LL t=A.t*B.t;return !t?A.id<B.id:t<0;
});
ans=max(0ll,a[1].mx);
for(int i=1,j;i<=m;i=j)
{
for(j=i+1;j<=m&&!(B[i].t*B[j].t);j++);
for(int k=i;k<j;k++)
{
auto [u,v]=B[k].id;
upd(p[u],A[v].w),upd(p[v],A[u].w),swap(p[u],p[v]);
}ans=max(ans,a[1].mx);
}
return cout<<ans,0;
}
```