改试卷（paper）

题目背景

zyc快速地浏览了一下手上的数学试卷，并且拿向下一张。

“咦……是他的。唉，他怎么这个时候总是不在。”他叹道。“这下得好好改了。”

“这是什么做法啊……这么复杂？这到底是不是对的啊？”

他手上的试卷采用了一种极度复杂的暴算方法，并跳过了所有计算过程，只有若干个“解得”“可推得”。

题目描述

为了检查这个做法是否正确，他不得不维护一个初始为空的二维点集，并支持以下操作共 \(n\) 次：

向集合内加入一个点 \((x,y)\)。
从集合内删除第 \(x\) 次操作加入的点。保证第 \(x\) 次操作是 1 操作。
给出参数 \(a,b\)，询问对于当前点集内的所有点 \((x,y)\)，\(ax+by\) 的最大值是多少。特别的，若当前点集为空，规定答案为0。

zyc发现暴力检查的话就会像手上这张卷子的主人一样浪费整整一小时的时间才能算完。

所以，他想找到更好的方法。

不过，他总喜欢再检查一遍。所以，请你看看他和你算的结果是不是一样的吧。

输入格式

第一行一个整数 \(n\)，表示操作次数。
接下来 \(n\) 行，每行为 1 x y 或 2 x 或 3 x y ，表示题面中给出的一种操作。

输出格式

对于每个 3 操作，输出对应的答案，单独占一行。

样例 #1

样例输入 #1

样例输出 #1

19
130

提示

对于前 \(20\%\) 的数据，\(n\le 2000\)。

对于前 \(40\%\) 的数据，\(n\le 5\times 10^4\)。

对于前 \(70\%\) 的数据，\(n\le 10^5\)。

对于所有数据，\(1\le n\le 10^6,0\le x,y,a,b\le 10^9\)。

保证操作2给出的必定能对应上一个操作1。

分析

显然暴力写的好，\(70pts\) 是有的

\(70pts \ code\)

点击查看代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define int long long
#define N 100010
using namespace std;
template<typename T>void read(T &x)
{
	x=0;char c=getchar();T neg=0;
	while(!isdigit(c))neg|=!(c^'-'),c=getchar();
	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
	if(neg)x=(~x)+1;
}//快读 
template<typename T>void wr(T x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)wr(x/10);
	putchar((x-x/10*10)^48);
	return ;
}//快写 
int n,opt[N],id;
struct node{
	int x;int y;
}re[N];
int ask(int a,int b)//当前存在的值中暴力查询 
{
	int ans=0;
	for(int i=1;i<=id;i++)
		ans=max(ans,a*re[i].x+b*re[i].y);
	
	return ans;
}
signed main()
{
//	freopen("paper.in","r",stdin);
//	freopen("paper.out","w",stdout);
	read(n);
	for(int i=1;i<=n;i++)
	{
		int c,x,y;
		read(c);
		if(c==1)
		{
			++id;
			opt[i]=id;//添加可行值 
			read(x),read(y);
			re[id].x=x;re[id].y=y;
		}
		if(c==2)  read(x),re[opt[x]].x=0;re[opt[x]].y=0;//删去指定值 
		
		if(c==3)
		{
			int a,b;
			read(a),read(b);
			int Ans=ask(a,b);//暴力查询 
			wr(Ans),putchar('\n');
		}
	}
	return 0;
}

正解

观察数据范围 , \(O(n^2)\) 是显然不可以接受的

先从性质入手
\(ax+by=m\) 要求 \(m\) 的最大值

对式子变形 \(y=\frac{m}{b}-\frac{a}{b}x\)

问题就转化为 \(\frac{m}{b}\) 的最大值 (即该直线在 \(y\) 轴上的最大值)

显然我们需要的点维护的是一个凸包（那些有效对答案可能有贡献的点）

对于凸包用单调斜率进行维护

考虑如何查询

显然答案只可能是之前操作中出现且没有被删除的值

我们不妨从每次操作出现的时间入手

维护一个时间段，时间段中包含该时间内存在的点集

对于时间段我们用线段树维护

那么查询即从开始到该询问的操作时间这个时间段中寻找答案

这个时间段中的点集就是上文中的凸包

但是如果每一次查询都从该时间段中的凸包一个一个选择是\(O(n)\)的效率

显然不可行

考虑二分? 每次查询 \(O(log\ n)\) ,维护也是\(O(log\ n)\) 总时间复杂度就是\(O(nlog^2n)\)

这样也无法通过

此时 \(y1\) 在 \(3\) 位置有最优解

我们可以发现 \(y2\) 在 \(3\) 位置之前都不如 \(3\) 之后的答案

也就是说如果我们确定了 \(y1\) 的位置后，\(y2\) 只可能在 \(y1\) 之后的点集产生最大值

显然满足该条件的前提是 \(y2\) 的斜率大于 \(y1\)

那我们对斜率（-\(\frac{a}{b}\)）排序，查询时就有了进一步优化

查询出答案就完了

\(AC\ code\)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define N 1000010
#define int long long
using namespace std;


int n,ed[N],ans[N];
int opt;
int X,Y;
int bug[N<<2];

struct node{  int x,y ;  int id,opt ; }re[N];
struct cool{  int x,y ; } ;

template<typename T>void read(T &x)
{
	x=0;char c=getchar();T neg=0;
	while(!isdigit(c))neg|=!(c^'-'),c=getchar();
	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
	if(neg)x=(~x)+1;
}
template<typename T>void wr(T x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)wr(x/10);
	putchar((x-x/10*10)^48);
	return ;
}// 快读快写 



bool cmp(node a,node b)
{
	if(a.opt!=b.opt) return a.opt<b.opt;
	if(a.opt==1) return a.x==b.x? a.y<b.y : a.x<b.x ;// 对 1操作 添加的点进行排序，目的是有序建立凸包 
	return a.x*b.y<b.x*a.y ; //对 3操作 斜率进行排序 
}

bool ck(cool a,cool b,cool c) {return (c.y-b.y)*(b.x-a.x) >= (b.y-a.y)*(c.x-b.x) ; }// 维护凸包 等效于（y1-y2）/(x1-x2) >= (y2-y3)/(x2-x3) 
int calc(cool a,cool b){ return a.x*b.x+a.y*b.y ; }// 计算(ax+by) 


cool make(int x,int y){ cool st; st.x=x; st.y=y ;return st;}
vector<cool>shell[N<<2];
cool st[N];

//build 操作 是在该时间段中加入存在的点 并未维护凸包 
void build(int x,int l,int r,int L,int R,cool k)
{
	if(L<=l&&r<=R)
	{
		shell[x].push_back(k);// 加入该时间出现的点 
		return ;
	}
	int mid=(l+r)>>1;
	if(L<=mid) build(x<<1,l,mid,L,R,k);
	if(R>mid) build(x<<1|1,mid+1,r,L,R,k);
}

// make_shell 对存在的时间段中维护凸包 
void make_shell(int x,int l,int r)
{
	
	int top=0;
	for(int i=0;i<shell[x].size();i++)
	{
		cool v=shell[x][i];
		
		while(top>1&&ck(st[top-1],st[top],v)) top--;//单调队列维护凸包 
		st[++top]=v;
	}
	
	shell[x].resize(top);// 重新更新点集 当然也可以使用 clear() 但时间复杂度不如 resize（） 
	for(int i=1;i<=top;i++) shell[x][i-1]=st[i];
	
	
	if(l==r) return ;
	
	int mid=(l+r)>>1;
	make_shell(x<<1,l,mid);
	make_shell(x<<1|1,mid+1,r);
	
}

// 查询答案  
int upd(int x,int l,int r,int pos,cool k)
{
	
	while(bug[x]+1<shell[x].size()&&calc(k,shell[x][bug[x]+1])>calc(k,shell[x][bug[x]])) ++bug[x];// bug记录当前凸包上有效答案的起始点 及维护上文中的 3 位置 
	//   一定是bug[x]+1<shell[x].size() 如果是bug[x]<shell[x],size()  bug[x]+1 会 溢出为一个随机值  
	if(l==r) 
		return shell[x].size()?calc(k,shell[x][bug[x]]):0 ;
	
	
	int mid=(l+r)>>1,ans=0;
	if(pos<=mid) ans=upd(x<<1,l,mid,pos,k);
	else ans=upd(x<<1|1,mid+1,r,pos,k);
	
	return max(ans , shell[x].size()?calc(k,shell[x][bug[x]]) : 0);//返回存在凸包中的可行方案 
}


signed main()
{
//	freopen("paper1.in","r",stdin);
	
	read(n);
	for(int i=1;i<=n;i++)
	{
		
		read(opt);
		re[i].id=i;  re[i].opt=opt;
		if(opt!=2)
		{
			read(X), read(Y);
			re[i].x=X;
			re[i].y=Y;
		}
		if(opt==2)
		{
			read(X);
			ed[X]=i;// 记录删除点的结束时间 
		}
	}
	
	for(int i=1;i<=n;i++) if(!ed[re[i].id]&&re[i].opt==1) ed[re[i].id]=n;// 如果没有被删除 存活到最后一个操作时间 
	
	sort(re+1,re+n+1,cmp);// 按规则排序 
	
	for(int i=1;i<=n;i++) 
		if(re[i].opt==1) build(1,1,n,re[i].id,ed[re[i].id],make(re[i].x,re[i].y)); //建立时间段中存在点集 
	
	
	make_shell(1,1,n);// 将点集转化为凸包 
	
	for(int i=1;i<=n;i++)
		if(re[i].opt==3) 
			ans[re[i].id]=upd(1,1,n,re[i].id,make(re[i].x,re[i].y)); // 查询 
		
	
	for(int i=1;i<=n;i++) if(ans[i]) wr(ans[i]),putchar('\n');
	
	return 0;
	
}
/*
10
1 1 1
3 9 10
1 1 10
2 1
2 3
1 4 5
1 10 5
1 8 8
2 8
3 10 6
*/

改试卷（凸壳维护） - llwwll - 博客园