#P4311. 向量

    ID: 3527 传统题 1000ms 512MiB 尝试: 817 已通过: 204 难度: 8 上传者: 标签>难度分类提高+/省选-离线与分治线段树分治活跃时间区间挂树计算几何凸包排序与序列处理单调栈叉积点积查询排序同向双指针归并排序CF2400

向量

向量

题目描述

维护一批二维向量,开始时为空。每次插入都有独立的编号,即它是第几次插入操作。两次插入的坐标可以相同。

操作 含义
1 x y 插入向量 (x,y)(x,y)
2 i 删除第 ii 次插入的向量
3 x y 在当前所有向量 (a,b)(a,b) 中查询 ax+byax+by 的最大值。若没有向量,答案为 00

输入格式

第一行一个整数 nn,表示操作数。随后 nn 行,每行一个操作。每次删除所指定的向量均已插入且尚未删除。

输出格式

每个查询输出一行一个整数。

样例 #1

样例输入 #1

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

样例输出 #1

18
15

数据规模与约定

1≤n≤2000001\le n\le200000,1≤x,y≤1061\le x,y\le10^6。