奇怪的数据结构 - JoishBadeR - Holy Sh*t

<[Sdoi2014]向量集>,<SdoiR1D2T2 Problem Vset>

Description

要求一个数据结构，支持：

A：在容器末尾插入一个向量(x,y)

Q：询问容器(l,r)的区间里的所有向量，与向量(x,y)点积最大的是多少

操作数N在4*10^5范围内，保证答案在64位整数范围内，强制在线

A类数据：30分，N<=1000

B类数据：10分，插入向量横坐标单增且总是询问整个区间

C类数据：20分，插入向量坐标单增

D类数据：10分，总是询问整个区间

E类数据：20分，离线

F类数据：10分，无特殊条件

Description:

有10^5个点10^5个操作。

每个点有两个属性：权值和颜色(颜色值小于C)。

操作分为四种：1.CW修改一个点的权值。2.CC修改一个点的颜色。3.QS询问u->v路径上与u颜色相同的点的权值和。4.QM询问u->v路径上与u颜色相同的点的权值极值。保证u和v的颜色相同

数据范围：

1,2 N,Q<=10^3,C<=10^2 无

3,4 N,Q<=10^5,C<=10^2 链；无CC操作

5 N,Q<=10^5,C<=10^2 无CC，QM操作

6,7 N,Q<=10^5,C<=10^2 无CC 操作

8,9 N,Q<=10^5,C<=10^2 链

10~12 N,Q<=10^5,C<=10 无

13~16 N,Q<=10^5,C<=10^5 无QM操作

17~20 N,Q<=10^5,C<=10^5 无

左偏树是一种不需要证明的可并堆(呸)

建树O(NlgN) - O(N)

合并O(lgN)

删除O(1)

个人复习用品