Loj 2845 Innophone

Posted on | Edited on | Views:

分块 + 斜率优化.

选择的 $a$ 一定是某个出现过的 $x$ ,或者 $a$ 大于所有的 $x$ .

否则将 $a$ 增大到下个出现过的 $x$ ,答案不会变劣, $b$ 的选择同理.

于是可以从小到大枚举 $a​$ ,只需要考虑 $b​$ 的选择对 $x<a​$ 的点贡献的影响.

将所有 $x<a$ 的点按照 $y​$ 从小到大排序.

若共有 $cnt$ 个点的 $x<a$ ,那么选择第 $i$ 个点的 $y$ 作为 $b$ ,带来的贡献是 $v_i=(cnt-i+1)\cdot y_i$ .

随着 $a$ 的增大, $x<a$ 的点会不断增多,每加入一个新点,它后面的点 $v_i$ 不变,前面的点的 $v_i$ 会加上 $y_i$ .

如果直接用平衡树打标记,修改后没法得到区间内新的 $\max v_i​$ ,考虑分块来处理.

若某一块整体被加了 $tag$ 次,那么块内真正的贡献为 $v_i’=tag\cdot y_i+v_i$ ,变形得到 $v_i=-tag\cdot y_i+v_i’$ .

即用一条斜率为 $-tag​$ 的直线去截块内所有点,要最大化截距,于是可以维护出块内所有点的上凸壳.

斜率只会变小,被截到的点只会往右侧移动,那么不用在凸壳上二分,记录一下当前被截到的是哪个点即可.

先算出所有点都被插入时,每个点分别在哪一块,插入时直接插到那一块中即可.

插入点时,重构一下插入的那一块的上凸壳,修改前面所有非空块的 $tag​$ ,并重新计算它们的贡献.

时间复杂度 $O(n\log n+n\sqrt n)$ .

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1.5e5+10,S=400;
struct v2
{
	ll x,y;
	int id;
	v2 operator - (const v2 &rhs) const
	{
		return (v2){x-rhs.x,y-rhs.y};
	}
	ll operator * (const v2 &rhs) const
	{
		return x*rhs.y-y*rhs.x;
	}
}p[MAXN],q[MAXN],pt[MAXN];
bool cmpy(const v2 &A,const v2 &B)
{
	return A.y<B.y;
}
bool cmpx(const v2 &A,const v2 &B)
{
	return A.x<B.x;
}
int n,B,bel[MAXN],vis[MAXN];
struct Block
{
	int lp,rp,cnt,tag,tp,pos;
	ll res;
	v2 stk[S];
	Block(){cnt=tag=res=0;}
	ll calc(v2 cur)
	{
		return cur.x*tag+cur.y;
	}
	void ReBuild(int x)
	{
		if(tag)
		{
			for(int i=lp;i<=rp;++i)
				if(vis[i])
					pt[i].y+=pt[i].x*tag;
			tag=0;
		}
		for(int i=lp;i<x;++i)
			if(vis[i])
				pt[i].y+=pt[i].x;
		vis[x]=1,++cnt;
		tp=0;
		for(int i=lp;i<=rp;++i)
			if(vis[i])
			{
				if(tp && pt[i].x==stk[tp].x && pt[i].y<=stk[tp].y)
					continue;
				while(tp>=2 && (pt[i]-stk[tp-1])*(stk[tp]-stk[tp-1])<=0)
					--tp;
				stk[++tp]=pt[i];
			}
		pos=1;
		while(pos+1<=tp && calc(stk[pos])<calc(stk[pos+1]))
			++pos;
		res=calc(stk[pos]);
	}
	void upd()
	{
		if(!cnt)
			return;
		tag++;
		while(pos+1<=tp && calc(stk[pos])<calc(stk[pos+1]))
			++pos;
		res=calc(stk[pos]);
	}
}block[S];
void ins(int x)
{
	pt[x].x=pt[x].y=p[x].y;
	for(int i=x+1;i<=block[bel[x]].rp;++i)
		if(vis[i])
			pt[x].y+=pt[x].x;
	for(int i=bel[x]+1;i<=bel[n];++i)
		pt[x].y+=pt[x].x*block[i].cnt;
	block[bel[x]].ReBuild(x);
	for(int i=1;i<bel[x];++i)
		block[i].upd();
}
ll query()
{
	ll res=0;
	for(int i=1;i<=bel[n];++i)
		res=max(res,block[i].res);
	return res;
}
int main()
{
	n=read();
	B=sqrt(n);
	for(int i=1;i<=n;++i)
	{
		p[i].x=read(),p[i].y=read();
		bel[i]=(i-1)/B+1;
		block[bel[i]].lp=(bel[i]-1)*B+1;
		block[bel[i]].rp=bel[i]*B;
	}
	block[bel[n]].rp=n;
	sort(p+1,p+1+n,cmpy);
	for(int i=1;i<=n;++i)
		p[i].id=i,q[i]=p[i];
	sort(q+1,q+1+n,cmpx);
	ll ans=q[1].x*n;
	for(int i=1,j=0;i<=n;++i)
	{
		while(j+1<=n && q[j+1].x==q[i].x)
			ins(q[++j].id);
		i=j;
		ans=max(ans,q[i+1].x*(n-i)+query());
	}
	cout<<ans<<endl;
	return 0;
}