杂项
x某人
·
·
个人记录
好吧这里是一个蒟蒻最后的挣扎。
放一些知识点的简要总结，方便赛前观看。
（：现在写是不是有点晚
## Manacher
可以先考虑朴素算法。以每个字符为中心，逐此向左右两边扩展，寻找最大的回文串。
Manacher 其实就是优化的暴力啦。
从左向右依次扩展，扩展产生的新回文串，利用回文串的性质，一定在之前的区域内有一个对称的字符串。
所以在已扩展区间内就不用比较了，未扩展区域还是暴力扫，这样就是线性的！
### 细节：
- 每次要更新扩展区域
- 计算之前要加辅助符号
- 各题有细节不同
[代码参考](https://www.luogu.com.cn/record/83958057)
## AC自动机
就是 $kmp + trie$ 麻（大雾
先建个 $trie$ ，为保证该节点之前的 $fail$ 已确定用 $BFS$ 建。
当前节点指向父亲时字符为 $c$，建自动机时跳 父亲 的 $fail$ ，如果该节点有对应 $c$ 的一条出边，就将当前节点的 $fail$ 指向它。如果没有就一直跳 $fail$，知道满足上述条件或到根节点为止。
匹配的话在之前建 $trie$ 时记录 $end$，从根节点开始，跳文本串下一个字符，一直跳 $fail$，如果 $end$ 跳过了就不用跳了，同时累计答案。
### 细节：
- 压队列一开始要将根节点的子节点压入队列，如果直接压根节点，子节点的 $fail$ 会指向自己。
- 建自动机过程类似于 并查集 的路径压缩，具体实现看代码。（若该节点没有对应字母出边，则将这个出边设成 父亲 $fail$ 的出边节点。
- 拓扑排序优化 [代码参考](https://www.luogu.com.cn/record/84061901)
[博客参考](https://www.luogu.com.cn/blog/juruohyfhaha/solution-p5357)
[代码参考](https://www.luogu.com.cn/record/84009342)
[博客参考](https://www.luogu.com.cn/blog/3383669u/qiang-shi-tu-xie-ac-zi-dong-ji)
## 后缀自动机
最重要的当然是建图。
讲起来挺复杂，记代码就行了吧。
```cpp
void make(int x)
{
int p,q,np,nq;
tot++,point[tot].len=point[last].len+1;
p=last,np=last=tot;
while(!point[p].ch[x]&&p)
{
point[p].ch[x]=np;
p=point[p].fa;
}
if(!p) point[np].fa=1;
else
{
q=point[p].ch[x];
if(point[p].len+1==point[q].len) point[np].fa=q;
else
{
tot++,nq=tot;
for(int i=1;i<=26;i++) point[nq].ch[i]=point[q].ch[i];
point[nq].fa=point[q].fa,point[q].fa=point[np].fa=nq,point[nq].len=point[p].len+1;
while(point[p].ch[x]==q&&p) point[p].ch[x]=nq,p=point[p].fa;
}
}
}
```
### 细节：
- $tot$、$last$ 从 $1$ 开始。
- 具体看代码与 PPT 吧。
## fhqTreep
哈哈哈就只放代码了，总之原理就是那些重要的是打得熟练。
[代码参考](https://www.luogu.com.cn/record/84792203)
[博客参考](https://www.luogu.com.cn/blog/85514/fhq-treap-xue-xi-bi-ji)
## 左偏树
保证堆的性质同时也保证左子树距离大于右子树距离，这样合并时一路合并右子树是最优的。
如果左边距离大于右边交换子树即可。
### 细节
- 在删除左偏树中的最小值时，因为 $x$ 是之前左偏树的根节点，在路径压缩时可能有 $rt$ 的值等于 $x$ ，所以 $rt$[$x$] 也要指向删除后的根节点。
[代码参考](https://www.luogu.com.cn/record/69371186)
[博客参考](https://www.luogu.com.cn/blog/cytus/ke-bing-dui-zhi-zuo-pian-shu)
## 整体二分
离线操作。感觉是个离谱玩意。上代码，考完之后更新。
[代码参考](https://www.luogu.com.cn/record/77593584)
## CDQ分治
同理上代码（嘤嘤嘤时间不够了
树状数组 $+$ 归并排序
[代码参考](https://www.luogu.com.cn/record/77464867)
## 计算几何
代码放这了咕咕咕
```cpp
#include<bits/stdc++.h>
#define pi acos(-1)
using namespace std;
const double eps=1e-8;
int com(double x)
{
if(fabs(x)<eps) return 0;
if(x>0) return 1;
else return -1;
}
struct Point
{
double x,y;
Point operator +(const Point &p) {return Point{p.x+x,p.y+y};}
Point operator -(const Point &p) {return Point{x-p.x,y-p.y};}
Point operator *(double p) {return Point{x*p,y*p};}
Point operator /(double p) {return Point{x/p,y/p};}
bool operator <(const Point &p)
{
if(com(x-p.x)==0) return y<p.y;
else return x<p.x;
}
};
struct line
{
Point x,y,v;
};
struct circle
{
Point o;
double r;
};
double spot(Point q,Point p) {return q.x*p.x+q.y*p.y;}
double length(Point q) {return sqrt(spot(q,q));}
double dis(Point p,Point q) {return length(p-q);}
double project(Point a,Point b,Point c) {return spot(b-a,c-a)/length(b-a);}
double cross(Point p,Point q) {return p.x*q.y-p.y*q.x;}
double area(Point a,Point b,Point c) {return cross(b-a,c-a);}
bool online(Point p,line l)
{
if(com(cross(p,l.v))==0) return 1;
else return 0;
}
bool onsegment(Point p,line l)
{
if(com(cross(p,l.v))==0&&com(spot(p-l.x,p-l.y))<=0) return 1;
else return 0;
}
Point rotate(Point p,double delta)
{
return Point{p.x*cos(delta)-p.y*sin(delta),p.x*sin(delta)+p.y*cos(delta)};
}
//point's shadow on the line
Point pointline(Point p,line l)
{
return l.x+l.v*(spot(p-l.x,l.v)/spot(l.v,l.v));
}
//distant of point and line
double pointlinedis(Point p,line l)
{
return cross(p-l.x,l.v)/length(l.v);
}
//两条直线交点
Point lineline(line l1,line l2)
{
if(com(cross(l1.v,l2.v))==0) return Point{-1,-1};
double x=cross(l2.v,l1.x-l2.x)/cross(l1.v,l2.v);
return l1.x+l1.v*x;
}
int turn(Point p1,Point p2,Point p3)
{
Point v1=p2-p1,v2=p3-p1;
if(com(cross(v1,v2))>0) return 1;
else if(com(cross(v1,v2))<0) return -1;
else return 0;
}
//circle
int in_circle(line l,circle c)
{
double dis=pointlinedis(c.o,l)-c.r;
return com(dis);
}
circle get_circle(Point p1,Point p2,Point p3)
{
Point p=(p1+p2)/2,q=(p1+p3)/2,o;
line l1=line{p,p+rotate(p1-p2,pi/2),rotate(p1-p2,pi/2)};
line l2=line{q,q+rotate(p1-p3,pi/2),rotate(p1-p3,pi/2)};
o=lineline(l1,l2);
return circle{o,dis(o,p1)};
}
```
# 警钟呜呜呜合集
2023.7.3：set 的 lower_bound 函数错写成 find
2023.7.11：[cmp 函数](https://www.luogu.com.cn/discuss/630769)
2023.7.17：kmp 跳 nxt 数组没写 while 写 if（纯纯 sb