bzoj 4311: 向量 — 线段树分治+凸包

  • 2017-12-25
  • 0
  • 0

4311: 向量

Time Limit: 20 Sec  Memory Limit: 512 MB

Description

你要维护一个向量集合,支持以下操作:
1.插入一个向量(x,y)
2.删除插入的第i个向量
3.查询当前集合与(x,y)点积的最大值是多少。如果当前是空集输出0

Input

第一行输入一个整数n,表示操作个数
接下来n行,每行先是一个整数t表示类型,如果t=1,输入向量
(x,y);如果t=2,输入id表示删除第id个向量;否则输入(x,y),查询
与向量(x,y)点积最大值是多少。
保证一个向量只会被删除一次,不会删没有插入过的向量

Output

对于每条t=3的询问,输出一个答案

Sample Input

5
1 3 3
1 1 4
3 3 3
2 1
3 3 3

Sample Output

18
15

HINT

n<=200000 1<=x,y<=10^6

Source

姜大爷讲完,感觉题解好巧妙

首先我们对于删除操作可以用线段树分治来实现

然后问题的怎么查询

对于一个向量的最优值,是在与该向量垂直的线中,在距离最远的线上的点的点积

所以我们可以维护出凸包,然后在凸包上三分

那么,我们第一种想法是线段树分治时合并凸包,或平衡树维护凸包?

但是这个太难了,作为蒟蒻我当然不会了qaq

所以我们可以在线段树上每一个点维护一个凸包,在查询的时候去找从根到叶子节点路径上每一个的最优值去取一个max就好啦

最后时间复杂度O(nlog²n)

 

评论

还没有任何评论,你来说两句吧