P5244 [USACO19FEB] Mowing Mischief P

, , ,

Description

https://www.luogu.com.cn/problem/P5244

Solution

按 $x_i$ 排序。

首先做一个 LIS，记 $f_i$ 表示以 $i$ 结尾的最长上升子序列，$g_i$ 表示最小代价。我们可以根据 $f_i$ 来分层转移 $g_i$。

观察到一个很重要的性质，对于同一层的一些点，$x_i$ 递增（因为我们事先排好序了），$y_i$ 递减。否则 $f_i$ 同层还可以转移。

有了上面这个性质，可以发现第 $f_x=i$ 层可以转移到 $i-1$ 层的范围是一个区间。如果不考虑 $x_i$ 的限制。

显然状态不太能化简，考虑优化转移。计算 $j<k$ 转移到 $i$ 时什么时候更优：
$$
f_j+(x_i-x_j)(y_i-y_j)<f_k+(x_i-x_k)(y_i-y_k)\
y_i<\dfrac{y_j-y_k}{x_k-x_j}x_i+\dfrac{f_k+x_ky_k-f_j-x_jy_j}{x_k-x_j}
$$
在平面上就是斜率为正的右下方。而又根据同一层的性质，也就是有决策单调性。$i$ 越大决策点越前。

但是我们现在有 $x_i$ 的限制，所以用线段树分治一下即可。

复杂度 $O(n\log ^2n )$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>
#define ll long long
#define int long long 
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
ll power(ll x,int y=mod-2,int p=mod) {
	ll sum=1;x%=p;
	while (y) {
		if (y&1) sum=sum*x%p;
		x=x*x%p;y>>=1;
	}
	return sum;
}
int n,m;
struct node {
	int x,y;
	node(int a=0,int b=0) {x=a;y=b;}
}a[maxn];
int W(int i,int j) {
	if (a[i].x>a[j].x) swap(i,j);
	return (a[j].x-a[i].x)*(a[j].y-a[i].y);
}
bool cmp(node x,node y) {return x.x<y.x;} 
struct BIT {
	#define lowbit(x) ((x)&(-(x)))
	int f[1000005];
	void add(int x,int y) {for (;x<=m;x+=lowbit(x)) f[x]=max(f[x],y);}
	int query(int x) {int ans=0;for (;x;x-=lowbit(x)) ans=max(ans,f[x]);return ans;}
}t;
int g[maxn],f[maxn],id[maxn];
vector<int>O[maxn],Q[maxn<<2];
int b[maxn],c[maxn];
int now,las;
void update(int l,int r,int rt,int head,int tail,int k) {
	if (head<=l&&r<=tail) return Q[rt].push_back(k),void();
	int mid=l+r>>1;
	if (head<=mid) update(l,mid,rt<<1,head,tail,k);
	if (tail>mid)  update(mid+1,r,rt<<1|1,head,tail,k);
}
const int inf=1e18;
void calc(int l,int r,int L,int R) {
	if (l>r) return ;
	int mid=l+r>>1,p=L,tmp=inf,x=Q[now][mid],i;
	for (i=L;i<=R;i++) {
		int y=O[las][i];
		if (tmp>g[y]+W(x,y)) tmp=g[y]+W(x,y),p=i;
	}
	g[x]=min(g[x],tmp);
	calc(l,mid-1,p,R);
	calc(mid+1,r,L,p);
}
void solve(int l,int r,int rt) {
	if (Q[rt].size()) {
		now=rt;
		calc(0,Q[now].size()-1,l,r);
		Q[rt].clear();
	}
	if (l==r) return ;
	int mid=l+r>>1;
	solve(l,mid,rt<<1);
	solve(mid+1,r,rt<<1|1);
}
signed main(void){
	freopen("P5244_2.in","r",stdin);
	int i,j;
	read(n);read(m);
	for (i=1;i<=n;i++) read(a[i].x),read(a[i].y);a[++n]=node(m,m);
	sort(a+1,a+1+n,cmp);
	memset(g,0x1f,sizeof(g));
	f[0]=0;g[0]=0;int ans=0;
	for (i=1;i<=n;i++) {
		f[i]=t.query(a[i].y)+1;
		t.add(a[i].y,f[i]);
		O[f[i]].push_back(i);
	}
	O[0].push_back(0);
	for (i=1;i<=f[n];i++) {
		int len=O[i-1].size();
		for (j=0;j<len;j++) {
			b[j]=a[O[i-1][j]].x;
			c[j]=a[O[i-1][j]].y;
		}
		for (auto x:O[i]) {
			int r=lower_bound(b,b+len,a[x].x)-b;
			int l=lower_bound(c,c+len,a[x].y,greater<int>())-c;
			// gdb(l,r);?r);
			update(0,len-1,1,l,r-1,x);
		}
		las=i-1;
		solve(0,len-1,1);
		// solve(0,O[i].size()-1,0,O[i-1].size()-1);
	}
	printf("%lld\n",g[n]);
	return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 && ./$i

fun fuct: 我在用暴力打标决策点的时候，不考虑转移的限制，决策点大多数是递增的。