头像

Aigrl

初中信息学竞赛生,喜欢社会学书籍,热爱抽象数学,通常在摸鱼




离线:21分钟前


最近来访(714)
用户头像
啦啦啦...
用户头像
努力学习鸭
用户头像
hncsxzx
用户头像
封禁用户
用户头像
Confidentinvincible
用户头像
白月光L
用户头像
2010
用户头像
OI
用户头像
Abel51
用户头像
姚亦曦
用户头像
缘沁园春
用户头像
huohaha
用户头像
青城不良人
用户头像
TheGiao
用户头像
昕丶羽
用户头像
老老老帅比
用户头像
acwing_7845
用户头像
zhr123
用户头像
Q.c
用户头像
无为自在


Aigrl
21分钟前

笔记汇总


$AC$ 自动机是 以 Trie 的结构为基础,结合 KMP 的思想 建立的。

简单来说,建立一个 AC 自动机有两个步骤:

  1. 基础的 Trie 结构:将所有的模式串构成一棵 Trie。
  2. KMP 的思想:对 Trie 树上所有的结点构造失配指针。

然后就可以利用它进行 多模式串匹配 了。

失配指针

与$next$串的对比:

  1. 共同点:两者同样是在失配的时候用于跳转的指针。
  2. 不同点:next 指针求的是最长 Border(即最长的相同前后缀),而 fail 指针指向所有模式串的前缀中匹配当前状态的最长后缀。

即在失配后跳到其它分支上的与其真后缀相等的最长真前缀的末尾上。

实现

建树

tr[u][c] 从u往后加一个字符$c$到达的结点

void build() {
  for (int i = 0; i < 26; i++)
    if (tr[0][i]) q.push(tr[0][i]); 
  while (q.size()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      if (tr[u][i])
        fail[tr[u][i]] = tr[fail[u]][i];
        // tr[u][i] 的
        q.push(tr[u][i]);
      else
        tr[u][i] = tr[fail[u]][i];
    }
  }
}


分享 Trie

Aigrl
36分钟前

一棵用边来表示字母,插入时动态开点的树(降低时间复杂度),

它可以用较少的空间储存字符串,且查询效率较高,同时维护了字符串的前后缀。



分享 KMP

Aigrl
45分钟前

KMP 是可以在文本串$s$中快速查找模式串$p$的一种算法。

部分匹配表

$pmt[i]$ 就是,从 $p[0]$ 往后数、同时从 $p[i]$ 往前数相同的位数,在保证前后缀相同的情况下,最多能数多少位。(但要 小于 $p$的长度)

线性规划题,真前缀后缀的前缀和都往后添加。

故而可以用前缀去匹配后缀。

此过程还可以顺带求出前面的部分匹配表,即失配后往前移动模式串到未失配且最优时,

正确且复杂度为 $O(2n)$

匹配

若失配,则直到模式串成功匹配或移到头时继续。

因为每当 $j$ 往后移了,则之后 $i$ 必定往后移动(部分决定 $j$ 到底可以往前移几位),

算法正确,且时间复杂度为 $O(2n)$



活动打卡代码 AcWing 2815. 三维偏序

Aigrl
1小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

int n, m;
struct Data
{
    int a, b, c, s, res;    // s 是单点的贡献(即所有重复数据)

    bool operator< (const Data& t) const
    {
        if (a != t.a) return a < t.a;
        if (b != t.b) return b < t.b;
        return c < t.c;
    }
    bool operator== (const Data& t) const
    {
        return a == t.a && b == t.b && c == t.c;
    }
}q[N], w[N];
int tr[M], ans[N];  // 可以用权值线段树替换

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int v)
{
    for (int i = x; i < M; i += lowbit(i)) tr[i] += v;
}

int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

// 归并排序
void merge_sort(int l, int r)
{
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);

    // 双指针统计区间合并时的贡献
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)  // 边界
        if (q[i].b <= q[j].b) add(q[i].c, q[i].s), w[k ++ ] = q[i ++ ];
        else q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ];
    // q[i].b > q[j].b,仅当 q[i].a < q[j].a,则统计此时贡献
    while (i <= mid) add(q[i].c, q[i].s), w[k ++ ] = q[i ++ ];
    // i 余下的仍然要加入树,以便于后面清空树状数组
    while (j <= r) q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ];
    // 统计贡献,此时都是满足的
    for (i = l; i <= mid; i ++ ) add(q[i].c, -q[i].s);  // 清空树状数组
    for (i = l, j = 0; j < k; i ++, j ++ ) q[i] = w[j];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        q[i] = {a, b, c, 1};
    }
    sort(q, q + n);

    int k = 1;
    for (int i = 1; i < n; i ++ )
        if (q[i] == q[k - 1]) q[k - 1].s ++ ;
        else q[k ++ ] = q[i];

    merge_sort(0, k - 1);
    for (int i = 0; i < k; i ++ )
        ans[q[i].res + q[i].s - 1] += q[i].s;

    for (int i = 0; i < n; i ++ ) printf("%d\n", ans[i]);

    return 0;
}



Aigrl
2天前

笔记汇总


离线算法 具有 判定困难、全局判定 的特点。

分治,是一种将大的问题拆分成小问题解决的算法。

在修改、询问相互独立的前提下,我们可以用分治统计满足序数关系点对的数量。

逆序对的数量

这是一道二维偏序的模板题,由于是序数关系,且不用强制在线,让其中一个条件有序是有必要的,

所以我们可以靠排序降一维(避免高级数据结构),并用树状数组或权值线段树解决。

但是,如果我们是按双关键字排序呢?

回归本题,为什么分治可以统计点对的数量?

因为序列可以划分成很多部分,大的是小部分的组合,

如果双关键字排序的话,满足条件的都必定在左边(必要不充分)

我们可以不断的划分,然后对于右区间中每个点,统计左区间中符合其它偏序关系的点的个数。

这可以用双指针算法解决。

CDQ分治大致就是这两个基本形式:多维偏序降维动态修改转换成静态修改统一查询

只要问题能转化成这两个形式,那就可以考虑用CDQ分治了。

实现

一维偏序

排序可判叙述关系

二维偏序

双关键字排序降维,归并排序加双指针统计第二关键字可造成贡献。

注意第一关键字顺序不完全决定第二关键字顺序。

三维偏序

在统计贡献时对左区间建树,以统计左区间对右区间造成的贡献(区间内是已统计过的)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

int n, m;
struct Data
{
    int a, b, c, s, res;    // s 是单点的贡献(即所有重复数据)

    bool operator< (const Data& t) const
    {
        if (a != t.a) return a < t.a;
        if (b != t.b) return b < t.b;
        return c < t.c;
    }
    bool operator== (const Data& t) const
    {
        return a == t.a && b == t.b && c == t.c;
    }
}q[N], w[N];
int tr[M], ans[N];  // 可以用权值线段树替换

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int v)
{
    for (int i = x; i < M; i += lowbit(i)) tr[i] += v;
}

int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

// 归并排序
void merge_sort(int l, int r)
{
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);

    // 双指针统计区间合并时的贡献
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)  // 边界
        if (q[i].b <= q[j].b) add(q[i].c, q[i].s), w[k ++ ] = q[i ++ ];
        else q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ];
    // q[i].b > q[j].b,仅当 q[i].a < q[j].a,则统计此时贡献
    while (i <= mid) add(q[i].c, q[i].s), w[k ++ ] = q[i ++ ];
    // i 余下的仍然要加入树,以便于后面清空树状数组
    while (j <= r) q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ];
    // 统计贡献,此时都是满足的
    for (i = l; i <= mid; i ++ ) add(q[i].c, -q[i].s);  // 清空树状数组
    for (i = l, j = 0; j < k; i ++, j ++ ) q[i] = w[j];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        q[i] = {a, b, c, 1};
    }
    sort(q, q + n);

    int k = 1;
    for (int i = 1; i < n; i ++ )
        if (q[i] == q[k - 1]) q[k - 1].s ++ ;
        else q[k ++ ] = q[i];

    merge_sort(0, k - 1);
    for (int i = 0; i < k; i ++ )
        ans[q[i].res + q[i].s - 1] += q[i].s;

    for (int i = 0; i < n; i ++ ) printf("%d\n", ans[i]);

    return 0;
}



Aigrl
2天前

笔记汇总


之前所讲的状压$DP$是不完全的,现在补全。

最短Hamilton路径

Hamilton路径,是常见的$NP$类问题,在这样一个图上跑状压$DP$,属于集合式状压。

连通性$DP$的状态压缩表示的是每个点的 位置关系

集合类$DP$的状态压缩表示的是每个点的 是否存在

我们知道它的初始及目标,那中间过程也应有较小的初始及目标。

为了避免写图论,以及路径缺漏重复,我们将初始到任意一点的所有路径视为集合,

基础是不重复的,由归纳知所有路径也不会缺漏重复,证必 qwq。

回归插头。

由于我们直接将部分点暴力压缩,阶段间的状态复杂度过大,故而提出了按格枚举的插头$DP$。

简单来说,就是一个拼图,但为了避免原来与新的部分可能性过多,故多用于 限制较少的连通性 $DP$ 问题。

即同时满足容易判断所受限制(多米诺覆盖),新部分 可能状态数 较少。

个人不建议将它与轮廓线$DP$分开理解,或许可以叫拼图$DP$。

我们不需要存下全图的状态表示,仅需要存下可能影响答案的哪些状态表示(已知与未知的桥梁)。

插头DP

插头$DP$在判断一个格子是否与连通块相连方面,有两种表示方法。

以连通块数量为编号的 最小表示法

以块上类型为编号的 括号表示法,满足 两两配对、路径间不可交叉(具体分析)

一般复杂度远小于预估最坏复杂度,但空间复杂度略高。

插头$DP$ 的难点是状态分析,一般包括

$[$ 格点状态 $×$ 邻入边状态 $×$ 邻出边状态$][$格点 $,$ 邻入边 $,$ 邻出边不矛盾 $]$

在同时你还需要维护更新原连通块的编号信息,算是很难的了。

记得 哈希表 $+$ 滚动数组 $+$ 有效性优化




Aigrl
2天前

笔记汇总


在讲这个算法之前,我必须要讲一下 动态规划为什么应该存在?

首先,它可以求出我们需要的答案,而这个答案不是由交互得出的,它可以类比于在茫茫海洋搜索一个特定的数字。

其次,它是实用的,可以适用于不同的数据大小。

每当我们遇到一个题目,都可以先对它进行归纳。

如果你可以找到其中的关联,那它就是动态规划,或者说,递推式。

你或许会发现,所谓的各色算法都是没有存在必要的,它们都是一类,它们都是文身(引用 3b1b)

而状压$DP$,实质是一种多阶段少决策的最优化问题。

它通常是一种 $NP$ 问题,主要基于两方面 连通性集合

我们都知道连通性是拓扑学的概念,在计算机中和图论关系颇大,

状压$DP$ 正是在图中选取结点状态压缩并进行之后转移的过程。

首先,为什么要先状态压缩?:因为它 没有 拓扑关系,如不然,会爆空间,再者请不要试图找到 $P$ 类解法,它并没有一个可以单点延伸的初态。

我们关心的,只有如何找到一种覆盖答案且可转移的表示方式。

所以,你可以发现,只要我们将它压缩了,初态变大了,转移就简单了,当然为了便于转移的过程,它的转移通常少决策且少状态(单点)。

线性指的是单点顺延,这里是集合的顺延,或许可以说是二维结构吧?

这样可以便于你设计不会被错误覆盖的状态,你只要考虑它会转移到的阶段以及用一个可以表示所有单点状态的进制就行了。

在这过程中,模拟样例,减枝去叶。

至于集合,它只关心点是否存在,很难理解为什么有些人认为它更难(同情形下限制少简单)。

总的来说,认清初始和目标,中间转移过程除了点还可以是集合。

二进制




Aigrl
4天前

笔记汇总


和主席树一样,树套树采用 动态开点 的方式减少空间。

同样的,树套树采用与点分离的 永久化标记 处理区间的修改信息。

这类运用在 强制在线 是必要的。

如二维空间的修改查询,可采用 线段树套线段树

不同区间序数关系查询,无修改时可用 线段树套权值线段树(效率较高)

有修改时若 非序数上(如在序列上某处)的修改只能用 线段树套平衡树

线段树 是静态结构,平衡树 是动态结构,如果有结构上的改变,

我们则将 平衡树 作为外层。

实现(树上线段树)

即树上每一个结点都是一棵线段树(未开点的),

这主要是为了 $log$ 处理多维信息,也是 线段树合并 所常考的模型之一。

类似的还有 树上桶 $O(n)$

实现(线段树套线段树)

第一层线段树是一个区间,其中每一个结点都是一棵线段树(未开点的)

为了避免 $O(n)$ 复杂度的操作,所以在区间修改和查询时,

无论是内层还是外层都要标记永久化,标记与结点分离,查询时作为 函数附加值 携带。

所以结点上线段树也是 结点所代表的区间上 融合成的二维区间。




Aigrl
5天前

笔记汇总


树链剖分是一种将 树上路径 转化成 线性路径,并用 线段树 做区间运算的算法。

一棵树所蕴含信息大于同长线段蕴含的信息,如果要将线段树压至线段上,就需要将树划分。

划分必定与树的倾向有关。

性质

通过构造,树里的任意一条路径都可以转化成 $O(logn)$ 段连续区间。

所以树上点的编号要尽量的连续,如此,需要先对结点进行划分,如,

子树节点少的的代表是轻儿子,多的的代表是重儿子。

因为在同点下层子节点中只有一个重儿子,如果想要连续,顺着重儿子很有价值(因为一顺到底)

但树上存在很多的轻儿子,为了让两儿子融洽,故而创立了重链(轻头重身),

对于任意的一条路径,其起点和终点有,祖孙关系,同祖关系。

若是祖孙关系,则它们在一条链上,因为任意点要么是头要么是身,

易知,所有非叶子结点都在一条长大于一的路径中,

而另一点的最劣解,为全走轻点,而最佳构造是完全二叉树,其点至多为 $logn$,即树的深度。

若是同祖关系,则最大可为 $2logn$,因为这是最佳构造,所以也是最大的划分。

我们对结点按照重儿子优先来先序遍历,并赋予线性空间的编号(子树内编号连续)

因为区间操作需要知道涉及的区间,我们仿照并查集建立代表元。

实现

找到所有应修改(查询)的区间($O(logn)$),用线段树修改(查询)($O(log^2n)$)

找应修改区间的操作类似 $LCA$,但不需要倍增数组(逐一由代表元往上升)

这需要我们维护深度(类似 $LCA$)、代表元及其父亲(用来上升)。

我们每次都走深度较低的指针,线段树在线修改/查询(方便判边界)。

最后的重链要退出后再加,免得加两次。

步骤一

预处理所有节点的 重儿子 以及子树内 节点的数量 和 每个节点的 父节点

//dfs1预处理
void dfs1(int u, int father, int depth)
{
    dep[u] = depth, fa[u] = father, sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        dfs1(j, u, depth + 1);  // 先要知道子树大小才能知道谁是重儿子
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j; // 重儿子son是子树节点最多的儿子
    }
}

步骤二

树链剖分,找出每个节点所属 重链顶点dfs序的编号,并建立 u 到 id 的 w 映射

//dfs2做剖分(t是重链的顶点)
void dfs2(int u, int t)
{
    id[u] = ++ cnt, nw[cnt] = w[u], top[u] = t; 
    // 编号; 被编号点的线性空间映射; 代表元;
    if (!son[u]) return; //叶节点结束
    dfs2(son[u], t); //重儿子重链剖分
    //处理轻儿子
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j); //轻儿子的重链顶点就是他自己
    }
}

维护树上两个点的路径

void update_path(int u, int v, int k)   // u->v的路径上所有节点权值加k
{
    while (top[u] != top[v])    //向上爬找到相同重链;同时维护所有经过的重链
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);  // 全部由下往上利于辨认边界
        update(1, id[top[u]], id[u], k);    //dfs序原因,上面节点的id必然小于下面节点的id
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    update(1, id[v], id[u], k); //在同一重链中,处理剩余区间
}

拓展

因为子树内编号连续,维护子树大小就可以区间修改这一部分了。

维护以一个节点为根节点的子树

void update_tree(int u, int k) //子树全部加上k
{
    update(1, id[u], id[u] + sz[u] - 1, k); //由于dfs序的原因,可以利用子树节点个数直接找到区间
}

拓展用途

可以维护区间满足及不满足信息量(信息总量 $-$ 满足信息量)

id[u] - id[top[x]] + 1 // 单条重链上的信息总量



Aigrl
7天前

笔记汇总


线段树合并是一种在 $O(plogn)$ 时间内合并两棵权值线段树的算法。

我们采用动态开点的方式表示线段树来降低合并难度。

实现

有空则指空,无空则建新。

要求值域相同,否则重构。

因为$0$拿来判空点,所以建点下标从$1$开始。

合并后原结点的左右指针要有修改。