写在前面的话

ETT是一种动态树，它可以支持link，cut，子树修改，子树信息查询，链信息查询。似乎还可以支持换根（？），但是我不会。

P问题

可以在多项式时间内求解的问题。

“P” 代表 “polynomial time” 。

English Version

Order theory

partial order

将$(x_1,y_1)$和$(x_2,y_2)$分别作为$ x$轴和$ y$轴（即将坐标轴旋转，使得$x$轴与$(x_1,y_1)$平行，$y$轴与$(x_2,y_2)$平行，也就是将$(x_1,y_1)$，$(x_2,y_2)$作为单位向量），需要求出其他的点在旋转后的坐标系里的坐标。

如何实现？考虑原来的向量$(x,y)$表示的向量实际上是$xi+yj$，也就是单位向量$i$的$x$倍 + 单位向量$j$的$y$倍。因此，可以设这个点变化后的坐标为$(x’,y’)$，则：

解得

计算几何基础

标签（空格分隔）： 计算几何

有一个二维平面上的点构成的点集。有两种操作：1）加入一个点。2）询问一个点是否在这个点集的凸包内。

方法1：分别维护上凸壳和下凸壳

对于每个凸壳，用一个$set$存下凸壳上的点，把这些点按照横坐标排好序。新加入点的时候，找出横坐标与新加入点最接近的、凸壳上的点，判断是否需要弹掉。查询的时候二分找出对应的位置。

定义

这是一种对两个向量集合定义的运算。对于两个集合$A,B\in R^n$，它们的Minkowski Sum定义为：

定理：三角形的垂心(orthocenter)、重心(centroid)、外心(circumcenter)共线，且重心到垂心的距离等于重心到外心的距离的两倍。过三角形的垂心、重心、外心的直线称为欧拉线(Euler line)。

可以在这里感受一下。

证明：

如果一个卷积长这样：

好像不能够直接用FWT做了呢。但是我们观察，$X\cup Y=S,X\cap Y=\emptyset$等价于：

正确性显然。那么，我们可以枚举集合的大小，然后做或卷积。可以先对所有的进行FWT，然后枚举大小、求和，最后再变换回去。时间复杂度$2^n n^2$，$n$表示元素的数量。

主要都是用来解决有“通配符”、“模糊匹配”等的问题（如果没有这些东西直接kmp多好）。并且这些题目中，“通配符”能够代表的字符数量是一定的，否则就没有办法卷积了。

字符集较小：对每个字符单独考虑是否匹配