【备忘录】

zhzkiller · 2023-10-10 10:22:45 · 个人记录

Never Stop Upd

离散化

预备

a[n] 原数组。

b[m] 去重数组。

back[n] 备用数组。

代码

void discrete()
{
    memcpy(back,a,sizeof(a));
    sort(back+1,back+n+1);
    for(int i=1;i<=n;i++) if(back[i]!=back[i-1]) b[++m]=back[i];
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+m+1,a[i])-b;
}

并查集

预备

fa[x] 代表元素值。

代码

for(int i=1;i<=n;i++) fa[i]=i;

int find(int x)
{
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}

void merge(int x,int y)
{
    fa[find(x)]=find(y);
}

莫队

树上莫队走欧拉序。

莫队预备

结构体 itv：

l 区间左端点。

r 区间右端点。

id 区间编号。

lca 区间端点的 LCA 节点（树上莫队专有）。

first[x] 树上节点 x 在欧拉序第一次出现点。

last[x] 树上节点 x 在欧拉序后一次出现点。

rev[x] 区间点 x 对应的树上节点。

莫队代码

inline bool cmp(interval a,interval b)
{
    return ((a.l/t)^(b.l/t))?a.l<b.l:(((a.l/t)&1)?a.r<b.r:a.r>b.r);
}

void dfs(int x)
{
    first[x]=++tot;
    rev[tot]=x;
    d[x]=d[f[x][0]]+1;
    for(int i=h[x];i;i=edg[i].ne)
    {
        int y=edg[i].to;
        if(y==f[x][0]) continue;
        f[y][0]=x;
        for(int j=1;j<=16;j++) f[y][j]=f[f[y][j-1]][j-1];
        dfs(y);
    }
    last[x]=++tot;
    rev[tot]=x;
}

点分治

树的重心预备

• rt 当前节点。

• fa 当前节点的父亲节点。

• G 所求重心节点。

• siz 当前子树大小。

• size 已经覆盖子树大小。

• sonsize 某一子树大小。

树的重心代码

int getG(int rt,int fa,int& G,int siz)
{
    int size=1;
    int g=0;
    for(int i=h[rt];i;i=edg[i].ne)
    {
        int y=edg[i].to;
        if(y==fa||vis[i]) continue;
        int sonsize=getG(y,rt,G,siz);
        size+=sonsize;
        g=max(g,sonsize);
    }
    g=max(g,siz-size);
    if(g<=siz/2) G=rt;
    return size;
}

KMP

预备

• ne[i] 下标为 i 的 next 指针。

• f[i] 下标为 i 的匹配长度。

代码

for(int i=2,j=0;i<=n;i++)
{
    while(j&&a[i]!=a[j+1]) j=ne[j];
    if(a[i]==a[j+1]) j++;
    ne[i]=j;
}

for(int i=1,j=0;i<=n;i++)
{
    while(j&&(j==n||b[i]!=a[j+1])) j=ne[j];
    if(b[i]==a[j+1]) j++;
    f[i]=j;
    //if(f[i]==n) ......
}

笛卡尔树

满足二叉搜索树和堆性质的二叉树，节点保存二元组 (k,w)。

性质

• 如果 (k,w) 互不相同，则笛卡尔树形态唯一。

• 若以数组下标为 k，则每个子树的下标是一段连续的区间。

• 一个点的子树就是以这个点为极值的极长的区间（大根堆为最大值，小根堆为最小值）。

• 笛卡尔树的中序遍历即为原数组。

预备

• 结构体 t：