V2AS问路
模板库 ~ Template library
阅读原文时间：2023年07月09日阅读：3

TOC

建议使用 Ctrl+F 搜索 .

目录

Updating…

语言：C++ .

因为时间错乱，所以 Code Style 混乱 .

未注明作者的都是自己写的 .

NOI Linux 1.0

bashrc

  • title x：设置标题为 x

  • compile x：编译 x.cpp 并写入到可执行文件 x

  • compilerun x：compile x 并运行 x

    function title() {
    if [[ -z "$ORIG" ]]; then
    ORIG=$PS1
    fi
    TITLE="[\e]2;$*\a]"
    PS1=${ORIG}${TITLE}
    }

    compile() {
    g++ $1.cpp -lm -O2 -Wall -Wextra -std=c++14 -fsanitize=address,undefined -o $1
    }

    compilerun() {
    compile $1
    ./$1
    }

Bash 命令：

  • source ~/.bashrc：快速应用 bashrc
  • alias x=y：设置 y 的别名为 x，等号没有空格 .
  • unalias x：取消 x 这个别名

vimrc

注意插入前先按 i！！

https://www.cnblogs.com/fushao2yyj/p/8404511.html，tabstop 改成 4 .

nanorc

注意反人类 nano 的快捷键

nano 快捷键

  • 保存：Ctrl + O 保存 .
  • 复制一整行：Alt + 6
  • 剪贴一整行：Ctrl + K
  • 复制／剪贴多行或者一行中的一部分：先将光标移动到需要复制／剪贴的文本的开头，按 Ctrl + 6 或 Alt + A 做标记，然后移动光标到待复制／剪贴的文本末尾 . 这时选定的文本会反白，然后按复制一行的方法复制 . Ctrl + 6 取消 .
  • 粘贴：Ctrl + U
  • 搜索：Ctrl + W 然后输入搜索单词，Alt + W 跳转下一个
  • 退出：Ctrl + X，然后输入 Y 表示保存修改，N 不保存 . Ctrl + C 取消 .

Ref. https://zhuanlan.zhihu.com/p/259380222 .

set tabsize 4       # 设置制表符宽度
set autoindent      # 允许自动缩进
set cut             # 设置 CTRL-K 可以剪贴到行末
set noconvert       # 不要转换 DOS/UNIX 换行符
set nowrap          # 不要自动换行
set nohelp          # 不显示下面两行帮助 （Alt+X 显示）
set morespace       # 隐藏标题下的空白行，换取更多编辑空间
set smooth          # 平滑卷屏
set suspend         # 允许 ctrl-z 将 nano 置于后台
set smarthome       # 第一次 Home 跳到行首非空字符，第二次到行首
set tabstospaces    # 展开制表符为空格（如果需要的话）
set mouse           # 允许鼠标
# set linenumbers     # 显示行号（可以在编辑时 ALT-# 切换），NOI Linux 1.0 的 nano 太旧了不支持！
set backupdir path  # 设置备份路径
set backup          # 允许保存备份
set casesensitive   # 搜索使用大小写敏感
set multibuffer     # 使用 CTRL-r 读取文件时，默认读取到新缓存
set nonewlines      # 不在文件末尾添加新行

快速读入 / 快速输出

快速读入 / 快速输出

简易小工具

will update .

Tools

namespace __TYPE__
{
    typedef unsigned short     u16;
    typedef short              i16;
    typedef unsigned           u32;
    typedef int                i32;
    typedef unsigned long long u64;
    typedef long long          i64;
    typedef unsigned long long u64;
    typedef i64 ll;
    typedef u64 ull;
};
template<typename T>
inline T chkmax(T& x, const T& y){if (x < y) x = y; return x;}
template<typename T>
inline T chkmin(T& x, const T& y){if (x > y) x = y; return x;}

无序映射器

pool (Mixed)

接口：

构建 pool : T -> unsigned 的映射 .

若 \(M\) 为 pool<T> 类型变量，满足若 \(x\neq y\)，则 \(\operatorname{get}(x)\neq\operatorname{get}(y)\) .

template<typename T>
class pool
{
    unordered_map<T, unsigned> pol;
    unsigned cc;
public:
    pool(){cc = 0;}
    ~pool() = default;
    unsigned get(T x)
    {
        auto ptr = pol.find(x);
        if (ptr == pol.end()){pol[x] = ++cc; return cc;}
        else return ptr -> second;
    }
    unsigned size()const{return cc;}
    void clear(){cc = 0; pol.clear();}
};

简易调试器

普通版

输出至 stderr，检测 ONLINE_JUDGE 宏来控制调试开关 .

#ifdef ONLINE_JUDGE
#define dputs
#define dout
#define dprintf
#else // debug 至 stderr .
#define dputs(x) fputs(x"\n", stderr)
#define dprintf(F...) fprintf(stderr, F)
#define dout cerr
#endif 来自 [C++ Tricks](http://codeforces.com/blog/entry/15643)

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}

文件 IO

文件 IO

#define ifile(x) freopen(x".in", "r", stdin)
#define ofile(x) freopen(x".out", "w", stdout)
#define file(x) {ifile(x); ofile(x);}


#define ifile(x) freopen(#x".in", "r", stdin)
#define ofile(x) freopen(#x".out", "w", stdout)
#define file(x) {ifile(x); ofile(x);}

位运算

BITWISE

namespace BITWISE
{
    using __TYPE__ :: i64;
    inline int ctz(int x){return __builtin_ctz(x);}
    inline int clz(int x){return __builtin_clz(x);}
    inline int ffs(int x){return __builtin_ffs(x);}
    inline int popcnt(int x){return __builtin_popcount(x);}
    inline int lowbit(int x){return x & -x;}
    inline i64 ctzl(i64 x){return __builtin_ctzll(x);}
    inline i64 clzl(i64 x){return __builtin_clzll(x);}
    inline i64 ffsl(i64 x){return __builtin_ffsll(x);}
    inline i64 popcntl(i64 x){return __builtin_popcountll(x);}
    inline i64 lowbitl(i64 x){return x & -x;}
}

Smart Double

Smart Double

GCD

数论只会 GCD

辗转相除法

inline int gcd(int a, int b){return b ? gcd(b, a%b) : a;} Stein 算法 基于值域预处理的快速 GCD

// i don't know that.

快速幂相关

log 快速幂

inline int qpow(int a, int n)
{
    int ans = 1;
    while (n)
    {
        if (n & 1) ans = 1ll * ans * a % P;
        a = 1ll * a * a % P; n >>= 1;
    } return ans;
} 线性筛（指数不变 O(1) 求幂）

inline void linear_sieve(int n)
{
    notprime[1] = true; power[1] = 1;
    for (int i=2;i<=n;i++)
    {
        if (!notprime[i]){plist.emplace_back(i); power[i] = qpow(i, k);}
        for (auto x : plist)
        {
            int now = i*x;
            if (now > n) break;
            notprime[now] = true;
            if (!(i%x)){power[now] = 1ll * power[i] * power[x] % P; break;}
            power[now] = 1ll * power[i] * power[x] % P;
        }
    }
} 光速幂（底数不变 O(1) 求幂）

// 值域 2^31-1
template<int MOD>
struct FastPow
{
private:
    ll p1[66666], p2[66666];
    static ll qpow(ll a,ll n){/**/}
public:
    explicit FastPow(ll a)
    {
        ll t1=a,t2=qpow(t1,65536); p1[0]=p2[0]=1;
        for (int i=1; i<65536; i++) p1[i] = p1[i-1] * t1 % MOD;
        for (int i=1; i<65536; i++) p2[i] = p2[i-1] * t2 % MOD;
    }
    ll operator()(unsigned n){return p2[n>>16] % MOD * p1[n&65535] % MOD;}
};

分数模板类

EI 的取模还原分数

取模还原分数 (by Elegia)

https://blog.csdn.net/EI_Captain/article/details/117172239

pair<int, int> approx(int p, int q, int A) {
  int x = q, y = p, a = 1, b = 0;
  while (x > A) {
    swap(x, y); swap(a, b);
    a -= x / y * b;
    x %= y;
  }
  return make_pair(x, a);
}

逆元

模素数单个逆元 任意模数单个逆元 (exgcd)

ll inv(ll a, ll P){ll x ,y, d = exgcd(a ,P, x, y); return (d == 1) ? x % P : -1;} 线性求一行逆元

整除分块

一维整除分块 二维整除分块

线性筛

线性筛素数、欧拉函数、莫比乌斯函数

inline void linear_sieve(int n)
{
    notprime[1] = true; phi[1] = mu[1] = 1;
    for (int i=2; i<=n; i++)
    {
        if (!notprime[i]){plist.emplace_back(i); phi[i] = i-1; mu[i] = -1;}
        for (auto x : plist)
        {
            int now = i*x;
            if (now > n) break;
            notprime[now] = true;
            if (!(i%x)){phi[now] = phi[i] * x; mu[now] = 0; break;}
            phi[now] = phi[i] * phi[x]; mu[now] = mu[i] * mu[x];
    }
    }
}

扩展欧几里得算法 (exgcd)

传引用的 exgcd

ll exgcd(ll a,ll b,ll& x,ll& y)
{
    if (!b){x = 1; y = 0; return a;}
    ll _ = exgcd(b, a%b, x, y), old_x = x, old_y = y;
    x = old_y; y = old_x - (a/b) * old_y;
    return _;
} 返回 pair 的 exgcd

类欧几里得算法

中国剩余定理 (CRT) & exCRT

BSGS & exBSGS

积性函数筛子

组合数取模

杨辉三角

预处理阶乘及其逆元

Lucas

exLucas

using namespace std;
typedef long long ll;
ll qpow(ll a,ll n,ll p){/**/}
namespace extra_lucas_detail
{
    ll fac(ll n,ll p,ll pk)
    {
        if (!n) return 1;
        ll ans=1;
        for (int i=1;i<pk;i++)
            if (i%p) ans=ans*i%pk;
        ans=qpow(ans,n/pk,pk);
        for (int i=1; i<=n%pk;i++)
            if (i%p) ans=ans*i%pk;
        return ans*fac(n/p,p,pk)%pk;
    }
    ll exgcd(ll a,ll b,ll& x,ll& y){/**/}
    ll inv(ll a,ll P){ll x,y,d=exgcd(a,P,x,y); return (d==1)?x%P:-1;}
    ll C(ll n,ll m,ll p,ll pk)
    {
        if (n<m) return 0;
        ll A=fac(n,p,pk),B=fac(m,p,pk),C=fac(n-m,p,pk),cnt=0;
        for (ll i=n;i;i/=p) cnt+=i/p;
        for (ll i=m;i;i/=p) cnt-=i/p;
        for (ll i=n-m;i;i/=p) cnt-=i/p;
        return A*inv(B,pk)%pk*inv(C,pk)%pk*qpow(p,cnt,pk)%pk;
    }
}
ll exlucas(ll n,ll m,ll p)
{
    using namespace extra_lucas_detail;
    ll ans=0,P=p;
    for (int i=2;(p>1)&&(i*i<=p);i++)
    {
        ll pk=1;
        while (!(p%i)){p/=i; pk*=i;}
        if (pk>1)
        {
            ll now=C(n,m,i,pk);
            ans=(ans+now*(P/pk)%P*inv(P/pk,pk)%P)%P;
        }
    }
    if (p>1)
    {
        ll now=C(n,m,p,p);
        ans=(ans+now*(P/p)%P*inv(P/p,p)%P)%P;
    } return (ans%P+P)%P;
}

伯努利数

斯特林数

Catalan 数

Cantor 展开

LGV 引理

矩阵树定理

矩阵类

Simple Graph

Simple Graph

template<typename T>
struct Graph
{
    typedef vector<pair<int, T> > _;
    _ g[N];
    inline void addedge(int u, int v, ll w){g[u].emplace_back(make_pair(v, w));}
    inline void ade(int u, int v, ll w){addedge(u, v, w); addedge(v, u, w);}
    inline _ edges(const unsigned& id)const{return g[id];}
    inline _& edges(const unsigned& id){return g[id];}
    inline _ operator [] (const unsigned& id)const{return edges(id);}
    inline _& operator [] (const unsigned& id){return edges(id);}
    inline void clear(){for (int i=0; i<N; i++) g[i].clear();}
};

单源最短路径 (SSSP)

无负权：

Dijkstra 堆优化

struct Node
{
    int idx, d;
    Node(int _=0, int __=0){idx = _; d = __;}
    inline bool operator <(const Node& a)const{return d>a.d;}
};
void dijkstra(int s)
{
    memset(dis, 0x3f, sizeof dis);
    memset(vis, false, sizeof vis);
    priority_queue<Node> q; dis[s]=0; q.push(Node(s, dis[s]));
    while (!q.empty())
    {
        auto now = q.top(); q.pop();
        int u = now.idx;
        if (vis[u]) continue;
        vis[u] = true;
        for (auto _ : g[u])
        {
            int v = _.first, w = _.second;
            if (vis[v]) continue;
            if (dis[v] > dis[u]+w){dis[v] = dis[u]+w; q.push(Node(v, dis[v]));}
        }
    }
}

有负权 / 判负环：

Bellman-Ford

Bellman-Ford：

// a 存边
bool bellman_ford(int s)
{
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0; int t = 0;
    for (int i=1; i<n; i++)
        for (int j=0; j<m; j++)
        {
            int u = a[j].u, v = a[j].v, w = a[j].w;
            if (dis[v] > dis[u] + w) dis[v] = dis[u] + w;
        }
    for (int i=0; i<m; i++)
    {
        int u = a[j].u, v = a[j].v, w = a[j].w;
        if (dis[v] > dis[u] + w) return false;
    } return true;
}

SPFA：

// 入队次数超过 n 则有负环
inline void spfa(int x)
{
    memset(dis, 0x3f, sizeof dis); memset(vis, 0, sizeof vis);
    queue<int> q; vis[x] = true; dis[x] = 0; q.push(x);
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        for (auto e : g[u])
        {
            int v = e.first, w = e.second;
            if (dis[v] > dis[u] + w){dis[v] = dis[u] + w;  if (!vis[v]) q.push(v), vis[v] = true;}
        } vis[now] = false;
    }
} EI Magic (by Elegia)

https://www.cnblogs.com/Elegia/p/16122335.html

Bonus: 差分约束 .

多源最短路径

Floyd 全源最短路 Johnson 全源最短路

最短路图

最短路图

假装求最短路的函数是 SSSP(Graph, distance, u) .

k 短路

A* 持久化可并堆

同余最短路

跳楼机

给定 \(x,y,z,h\)，问有多少个 \(k\in[1,h]\) 使得 \(k=px+qy+rz\)，其中 \(p,q,r\) 是变量 .

using namespace std;
const int N=1e5+500;
typedef unsigned long long ull;
typedef long long ll;
ll x,y,z,h,dis[N];
bool vis[N];
typedef vector<pair<ll,ll> > graph[N];
graph g;
inline void addedge(ll u,ll v,ll w){g[u].push_back(make_pair(v,w));}
struct node
{
    int idx; ll dis;
    node(int _=0,ll __=0){idx=_; dis=__;}
    bool operator <(const node& u)const{return dis>u.dis;}
};
void dijkstra(int s){/**/}
int main()
{
    scanf("%lld%lld%lld%lld",&h,&x,&y,&z);
    if ((x==1)||(y==1)||(z==1)){printf("%lld",h); return 0;}
    if (x>y) swap(x,y);
    if (y>z) swap(y,z);
    if (x>z) swap(x,z);
    if (x>y) swap(x,y);
    if (y>z) swap(y,z);
    if (x>z) swap(x,z);
    for (int i=0;i<x;i++) addedge(i,(i+y)%x,y),addedge(i,(i+z)%x,z);
    dijkstra(0); ll ans=0;
    for (int i=0;i<x;i++)
        if (h>=dis[i]) ans+=(h-dis[i]-1)/x+1;
    printf("%lld",ans);
    return 0;
}

欧拉图 / 欧拉路

欧拉图判定 找一条欧拉路

一般图支配树

一般图支配树

https://www.luogu.com.cn/record/54432641

using namespace std;
typedef long long ll;
const int N=205000,M=20*N;
int n,m;
int head[N],shead[N],ihead[N],rhead[N],ver[M],nxt[M],tot=-1;
int siz[N],father[N],fa[N];
int dfn[N],id[N],low[N],sdom[N],idom[N],cnt;
void addedge(int head[],int u,int v){ver[++tot]=v; nxt[tot]=head[u]; head[u]=tot;}
void init(int n){for (int i=1;i<=n;i++) sdom[i]=low[i]=fa[i]=i;}
void dfs1(int u)
{
    dfn[u]=++cnt; id[cnt]=u;
    for (int i=head[u];~i;i=nxt[i])
    {
        int v=ver[i];
        if (dfn[v]) continue;
        father[v]=u; dfs1(v);
    }
}
int get(int u)
{
    if (u==fa[u])return u;
    int root=get(fa[u]);
    if (dfn[sdom[low[fa[u]]]]<dfn[sdom[low[u]]]) low[u]=low[fa[u]];
    return fa[u]=root;
}
void tarjan()
{
    int v;
    for (int i=cnt;i>1;i--)
    {
        int u=id[i];
        for (int j=rhead[u];~j;j=nxt[j])
        {
            v=ver[j];
            if (!dfn[v]) continue;
            get(v);
            if (dfn[sdom[low[v]]]<dfn[sdom[u]]) sdom[u]=sdom[low[v]];
        }
        addedge(shead,sdom[u],u);
        fa[u]=father[u];
        u=father[u];
        for (int j=shead[u];~j;j=nxt[j])
        {
            v=ver[j]; get(v);
            if (sdom[low[v]]==u) idom[v]=u;
            else idom[v]=low[v];
        }
        shead[u]=-1;
    }
    for (int i=2;i<=cnt;i++)
    {
        int u=id[i];
        if (idom[u]!=sdom[u]) idom[u]=idom[idom[u]];
    }
}
void dfs2(int u)
{
    siz[u]=1;
    for(int i=ihead[u];~i;i=nxt[i])
    {
        int v=ver[i];
        dfs2(v);
        siz[u]+=siz[v];
    }
}
int main()
{
    memset(head,-1,sizeof head);
    memset(ihead,-1,sizeof ihead);
    memset(rhead,-1,sizeof rhead);
    memset(shead,-1,sizeof shead);
    scanf("%d%d",&n,&m);
    for (int i=1,u,v;i<=m;i++){scanf("%d%d",&u,&v); addedge(head,u,v); addedge(rhead,v,u);}
    init(n);
    dfs1(1);
    tarjan();
    for (int i=2;i<=n;i++)
        if (idom[i]) addedge(ihead,idom[i],i);
    dfs2(1);
    for (int i=1;i<=n;i++) printf("%d ",siz[i]);
    return 0;
}

最小生成树 (MST)

Kruskal Prim Boruvka

连通性 (Tarjan)

2-SAT

Floyd

全源最短路

见 全源最短路 - Floyd .

传递闭包

bool dp[N][N];
void Floyd()
{
    for (int k=1; k<=n; k++)
        for (int i=1; i<=n; i++)
            for (int j=1; j<=n; j++)
                dp[i][j] = dp[i][j] | (dp[i][k] & dp[k][j]);
} 最小环

二分图

图的匹配

Prufer 序列

网络流

DAG 上问题

拓扑排序 支配树

https://www.luogu.com.cn/record/54416499

int lca(int p1,int p2)
{
    if (dep[p1]<dep[p2]) swap(p1,p2);
    for (int i=18;i>=0;i--)
        if (dep[f[p1][i]]>=dep[p2]) p1=f[p1][i];
    if (p1==p2) return p2;
    for (int i=18;i>=0;i--)
        if (f[p1][i]!=f[p2][i]) p1=f[p1][i],p2=f[p2][i];
    return f[p1][0];
}
void topsort()
{
    queue<int> q;
    for (int i=1;i<=n;i++)
        if (!deg[i]) q.push(i),father[i]=0;
    while (!q.empty())
    {
        int u=q.front(),fa=father[u]; q.pop();
        addedge(shead,fa,u);
        f[u][0]=fa; dep[u]=dep[fa]+1;
        for (int i=1;i<=22;i++) f[u][i]=f[f[u][i-1]][i-1];
        for (int i=head[u];~i;i=nxt[i])
        {
            int v=ver[i]; --deg[v];
            if (!deg[v]) q.push(v);
            if (father[v]==-1) father[v]=u;
            else father[v]=lca(father[v],u);
        }
    }
}

树上问题 - 最近公共祖先 (LCA)

倍增 LCA

int n,m,s,dep[N],f[N][LgN+10];
bool vis[N];
inline void dfs(int now,int fa)
{
    f[now][0]=fa; dep[now]=dep[fa]+1; int s=g[now].size();
    for (int i=1;i<=LgN;i++) f[now][i]=f[f[now][i-1]][i-1];
    for (int i=0;i<s;i++)
        if (g[now][i]!=fa) dfs(g[now][i],now);
}
inline int lca(int p1,int p2)
{
    if (dep[p1]<dep[p2]) swap(p1,p2);
    for (int i=18;i>=0;i--)
        if (dep[f[p1][i]]>=dep[p2]) p1=f[p1][i];
    if (p1==p2) return p2;
    for (int i=18;i>=0;i--)
        if (f[p1][i]!=f[p2][i]) p1=f[p1][i],p2=f[p2][i];
    return f[p1][0];
} Tarjan 算法离线 LCA 树剖求 LCA

namespace LCA
{
    int fa[N], dep[N], siz[N], son[N], top[N], dfn[N], rnk[N], cc;
    void dfs1(int u)
    {
        siz[u] = 1;
        for (auto v : g[u])
        {
            if (fa[u] == v) continue;
            dep[v] = dep[u] + 1;
            fa[v] = u;
            dfs1(v);
            siz[u] += siz[v];
            if (!son[u]|| (siz[v] > siz[son[u]])) son[u] = v;
        }
    }
    void dfs2(int u, int t)
    {
        top[u] = t;
        rnk[++cc] = u; dfn[u] = cc;
        if (!son[u]) return ;
        dfs2(son[u], t);
        for (auto v : g[u])
            if ((v != son[u]) && (v != fa[u])) dfs2(v, v);
    }
    int lca(int u, int v)
    {
        while (top[u] != top[v])
        {
            if (dep[top[u]] > dep[top[v]]) u = fa[top[u]];
            else v = fa[top[v]];
        }
        return dep[u] > dep[v] ? v : u;
    }
}

树上问题

树的直径与重心 树链剖分 (HLD)

LOJ #139

树上问题 - 树同构判定

字符串 Hash

BKDR Hash

Trie 相关

普通 Trie 01 Trie 压缩 Trie

Manacher

Manacher

KMP

KMP

typedef char str[N];
typedef long long ll;
str s1, s2;
int l1, l2, nxt[N], f[N];
void getnxt()
{
    nxt[1] = 0; int j = 0;
    for (int i=2; i<=l2; i++)
    {
        while (j && (s2[i] != s2[j+1])) j = nxt[j];
        if (s2[i] == s2[j+1]) ++j;
        nxt[i] = j;
    }
}
void kmp()
{
    int j = 0;
    for (int i=1; i<=l1; i++)
    {
        while ((j==l2) || (j && (s1[i] != s2[j+1]))) j = nxt[j];
        if (s1[i] == s2[j+1]) ++j;
        f[i] = j;
    }
}

Border Theory

Border 树

// 上接 KMP
getnxt();
for (int i=1; i<=l; i++) G.ade(i, nxt[i]);

Z Algorithm

Z Algorithm

AC 自动机

AC Automaton

// Sig 字符集（
// 此处字符集为小写字母（'a' ~ 'z'）
const int N = 1e6 + 50, Sig = 26;
struct AC
{
    int tr[N][Sig], fail[N], mark[N], cc, root;
    inline void insert(string s)
    {
        int u = root, l = s.length();
        for (int i=0; i<l; i++)
        {
            if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++cc;
            u = tr[u][s[i] - 'a'];
        } ++mark[u];
    }
    inline void build()
    {
        queue<int> q; fail[root] = root;
        for (int i=0; i<Sig; i++)
        {
            if (tr[root][i]){q.push(tr[root][i]); fail[tr[root][i]] = root;}
            else tr[root][i] = root;
        }
        while (!q.empty())
        {
            int u = q.front(); q.pop();
            for (int i=0; i<Sig; i++)
            {
                if (tr[u][i]){fail[tr[u][i]] = tr[fail[u]][i]; q.push(tr[u][i]);} // trie
                else tr[u][i] = tr[fail[u]][i]; // automaton
            }
        }
    }
    inline int query(string s)
    {
        int u = root, ans = 0, l = s.length();
        for (int i=0; i<l; i++)
        {
            u = tr[u][s[i] - 'a'];
            for (int j = u; j && ~mark[j]; j = fail[j]){ans += mark[j]; mark[j] = -1;}
        } return ans;
    }
    inline void clear(){memset(tr, 0, sizeof tr); memset(mark, 0, sizeof mark); cc = 0;}
    AC(){root = cc = 0;}
}ac; AC Automaton + fail 树

const int N = 1e6 + 50, Sig = 26;
int n;inline int trans(const char& c){return c - 'a';}
struct SimpleGraph
{
    vector<int> g[N];
    inline void addedge(int u,int v){g[u].emplace_back(v);}
    inline void ade(int u,int v){addedge(u, v); addedge(v, u);}
    vector<int>& operator [](const int& idx){return g[idx];}
    inline vector<int>& out_edges(int u){return g[u];}
};
struct AC
{
    SimpleGraph FT; // fail tree
    int tr[N][Sig], fail[N], ed[N], siz[N], cc, root;
    inline void insert(int id, string s)
    {
        int u = root, l = s.length();
        for (int i=0; i<l; i++)
        {
            int _ = trans(s[i]);
            if (!tr[u][_]) tr[u][_] = ++cc;
            u = tr[u][_]; ++siz[u];
        } ed[id] = u;
    }
    inline void build()
    {
        queue<int> q;
        for (int i=0; i<Sig; i++)
        {
            if (tr[root][i]){q.push(tr[root][i]); fail[tr[root][i]] = root;}
            else tr[root][i] = root;
        }
        while (!q.empty())
        {
            int u = q.front(); q.pop();
            for (int i=0; i<Sig; i++)
            {
                if (tr[u][i]){q.push(tr[u][i]); fail[tr[u][i]] = tr[fail[u]][i];}
                else tr[u][i] = tr[fail[u]][i];
            } FT.addedge(fail[u], u);
        }
    }
    void dfs(int u){for (int v : FT[u]) dfs(v), siz[u] += siz[v];}
    inline void query(string s){dfs(0);}
    AC(){cc = root = 0;}
}ac;

后缀数组 (SA)

后缀树 (ST)

后缀平衡树

后缀自动机 (SAM)

回文自动机 (PAM)

最小表示法

链表

链表

// 我不会链表

单调数据结构

单调栈 单调队列

ST 表

ST 表

// 传入一个 Functor 给 op，要求：
// 1. op(x, x) = x                （可重复贡献）
// 2. op(x, op(y, z)) = op(op(x, y), z) （结合律）
template<typename T, typename op>
struct ST
{
    typedef unsigned U;
    T f[N][LgN+10];
    template<typename rit>
    inline void reset(rit fst, rit sec)
    {
        const U n = sec - fst;
        for (U i=1; i<=n; i++) f[i][0] = *(fst + (i-1));
        for (U j=1; (1u<<j)<=n; j++)
            for (U i=1; i+(1u<<j)-1u<=n; i++) f[i][j] = op()(f[i][j-1], f[i + (1<<(j-1))][j-1]);
    }
    inline T query(U l, U r)const{U _ = log2(r-l+1); return op()(f[l][_], f[r-(1<<_)+1][_]);}
    template<typename rit>
    ST(rit fst, rit sec){init(fst, sec);}
    ST()  = default;
    ~ST() = default;
}; ST 表，但是查询最值位置

// 传入一个 Functor 给 op，要求：
// 1. op(x, x) = x            （可重复贡献）
// 2. op(x, op(y, z)) = op(op(x, y), z) （结合律）
template<typename T, typename op>
struct ST
{
    typedef unsigned U;
    T f[N][LgN+10]; U pos[N][LgN+10];
    template<typename rit>
    inline void reset(rit fst, rit sec)
    {
        const U n = sec - fst;
        for (U i=1; i<=n; i++){f[i][0] = *(fst + (i-1)); pos[i][0] = i;}
        for (U j=1; (1u<<j)<=n; j++)
            for (U i=1; i+(1u<<j)-1u<=n; i++)
            {
                if (op()(f[i][j-1], f[i+(1<<(j-1))][j-1])){f[i][j] = f[i][j-1]; pos[i][j] = pos[i][j-1];}
                else{f[i][j] = f[i+(1<<(j-1))][j-1]; pos[i][j] = pos[i+(1<<(j-1))][j-1];}
            }
    }
    inline T query(U l, U r)const{U _ = log2(r-l+1); return op()(f[l][_], f[r-(1<<_)+1][_]);}
    inline U querypos(U l, U r)const{U _ = log2(r-l+1);return op()(f[l][_], f[r-(1<<_)+1][_]) ? pos[l][_] : pos[r-(1<<_)+1][_];}
    template<typename rit>
    ST(rit fst, rit sec){init(fst, sec);}
    ST()  = default;
    ~ST() = default;
};

树状数组

树状数组 - 单点加区间查 树状数组 - 区间加单点查 树状数组 - 区间加区间查

线段树

普通线段树 (Segment Tree)

区间赋值，区间 min .

struct SMT
{
#define ls u << 1
#define rs u << 1 | 1
    struct Node{int l, r, m, lazy;}tr[4*N];
    inline void pushup(int u){tr[u].m = min(tr[ls].m, tr[rs].m);}
    inline void pushdown(int u)
    {
        if (!tr[u].lazy) return ;
        tr[ls].m = tr[rs].m = tr[u].lazy;
        tr[ls].lazy = tr[rs].lazy = tr[u].lazy;
        tr[u].lazy = 0;
    }
    void build(int u, int l, int r)
    {
        tr[u].l = l; tr[u].r = r;
        if (l == r){tr[u].m = w[rnk[l]]; return ;}
        int mid = (l + r) >> 1;
        build(ls, l, mid); build(rs, mid+1, r);
        pushup(u);
    }
    void change(int u, const int& l, const int& r, const int& x)
    {
        int L = tr[u].l, R = tr[u].r;
        if ((l <= L) && (R <= r)){tr[u].m = tr[u].lazy = x; return ;}
        pushdown(u);
        int mid = (L + R) >> 1;
        if (l <= mid) change(ls, l, r, x);
        if (r > mid) change(rs, l, r, x);
        pushup(u);
    }
    int query(int u, const int& l, const int& r)
    {
        int L = tr[u].l, R = tr[u].r;
        if ((l <= L) && (R <= r)) return tr[u].m;
        pushdown(u);
        int ans = INF, mid = (L + R) >> 1;
        if (l <= mid) chkmin(ans, query(ls, l, r));
        if (r > mid) chkmin(ans, query(rs, l, r));
        return ans;
    }
#undef rs
#undef ls
}T; 线段树合并

雨天的尾巴

using namespace std;
const int N = 1e5+50;
typedef long long ll;
typedef pair<int, int> pii;
template<typename T>
inline int chkmin(T& a, const T& b){if (a > b) a = b; return a;}
template<typename T>
inline int chkmax(T& a, const T& b){if (a < b) a = b; return a;}
int n, m, root[N], ans[N];
vector<int> g[N], G;
inline void addedge(int u, int v){g[u].emplace_back(v);}
inline void ade(int u, int v){addedge(u, v); addedge(v, u);}
struct Query{int x, y, z;}q[N];
namespace LCA{/*树剖 LCA*/}
struct Node //
{
    int p, cnt;
    Node(int _, int __) : p(_), cnt(__){}
    Node() = default;
    bool operator < (const Node& rhs)const{return (cnt == rhs.cnt) ? p > rhs.p : cnt < rhs.cnt;}
    Node operator + (const Node& rhs)const{return Node(max(p, rhs.p), cnt+rhs.cnt);}
    Node& operator += (const Node& rhs){return *this = *this + rhs;}
};
struct SMF
{
    int ch[40*N][2], cc;
    Node v[40*N];
    inline void pushup(int u){v[u] = max(v[ch[u][0]], v[ch[u][1]]);}
    inline void insert(int& u, int l, int r, Node _)
    {
        if (!u) u = ++cc;
        if (l == r){v[u] += _; return ;}
        int mid = (l + r) >> 1, p = _.p;
        if (p <= mid) insert(ch[u][0], l, mid, _);
        else insert(ch[u][1], mid+1, r, _);
        pushup(u);
    }
    inline void merge(int& x, int y, int l, int r) // this m
    {
        if (!x || !y){x += y; return ;}
        if (l == r){v[x] += v[y]; return ;}
        int mid = (l + r) >> 1;
        merge(ch[x][0], ch[y][0], l, mid);
        merge(ch[x][1], ch[y][1], mid+1, r);
        pushup(x);
    }
}T;
vector<Node> mdf[N];
int R;
void dfs(int u)
{
    for (int v : g[u])
        if (v != LCA::fa[u]){dfs(v); T.merge(root[u], root[v], 1, R);}
    for (auto e : mdf[u]) T.insert(u, 1, R, e);
    if (T.v[u].p) ans[u] = G[T.v[u].p - 1];
}
inline int discrete(int w){return lower_bound(G.begin(), G.end(), w) - G.begin()+1;}
int main()
{
    using namespace LCA;
    scanf("%d%d", &n, &m);
    for (int i=1, u, v; i<n; i++){scanf("%d%d", &u, &v); ade(u, v);}
    dep[1] = 1; dfs1(1); dfs2(1, 1);
    for (int i=1; i<=m; i++) scanf("%d%d%d", &q[i].x, &q[i].y, &q[i].z), ++q[i].z, G.emplace_back(q[i].z);
    stable_sort(G.begin(), G.end());
    G.erase(unique(G.begin(), G.end()), G.end());
    R = G.size()+1;
    for (int i=1; i<=m; i++)
    {
        int x = q[i].x, y = q[i].y, z = discrete(q[i].z), _ = lca(x, y);
        mdf[x].emplace_back(Node(z, 1));  mdf[y].emplace_back(Node(z, 1));
        mdf[_].emplace_back(Node(z, -1)); mdf[fa[_]].emplace_back(Node(z, -1));
    }
    for (int i=1; i<=n; i++) T.insert(root[i], i, i, Node());
    dfs(1);
    for (int i=1; i<=n; i++) printf("%d\n", max(0, ans[i]-1));
    return 0;
} 线段树分裂

李超线段树 (Li-chao Tree)

HEOI2013 Segment

using namespace std;
const int N=2e5+500;
typedef pair<double,int> pdi;
struct line{double k,b;}p[N];
int s[N],cnt,n;
double calc(int id,int d){return p[id].b+p[id].k*d;}
void add(int x0,int y0,int x1,int y1)
{
    ++cnt;
    if (x0==x1){p[cnt].k=0; p[cnt].b=max(y0,y1);}
    else{p[cnt].k=1.0*(y1-y0)/(x1-x0); p[cnt].b=y0-p[cnt].k*x0;}
}
void update(int root,int cl,int cr,int l,int r,int u)
{
    int v=s[root],mid=(cl+cr)>>1;
    bool UgV=calc(u,mid)>calc(v,mid);
    if ((r<cl)||(cr<l)) return ;
    if ((l<=cl)&&(cr<=r))
    {
        if (cl==cr) // leaf
        {
            if (UgV) s[root]=u;
            return ;
        }
        if (p[v].k<p[u].k)
        {
            if (UgV){s[root]=u; update(root<<1,cl,mid,l,r,v);}
            else update(root<<1|1,mid+1,cr,l,r,u);
        }
        else if (p[v].k>p[u].k)
        {
            if (UgV){s[root]=u; update(root<<1|1,mid+1,cr,l,r,v);}
            else update(root<<1,cl,mid,l,r,u);
        }
        else{if (p[u].b>p[v].b) s[root]=u;}
        return ;
    }
    update(root<<1,cl,mid,l,r,u);
    update(root<<1|1,mid+1,cr,l,r,u);
}
pdi Max(const pdi& A,const pdi& B)
{
    if (A.first==B.first) return A.second>B.second?B:A;
    else return A.first>B.first?A:B;
}
pdi query(int root,int l,int r,int d)
{
    if ((r<d)||(d<l)) return make_pair(0.0,0);
    int mid=(l+r)>>1; pdi ans=make_pair(calc(s[root],d),s[root]);
    if (l==r) return ans;
    return Max(ans,Max(query(root<<1,l,mid,d),query(root<<1|1,mid+1,r,d)));
}
int main()
{
    scanf("%d",&n); int opt,x0,y0,x1,y1,k,lastans=0;
    while (n--)
    {
        scanf("%d",&opt);
        if (!opt)
        {
            scanf("%d",&k); k=(k+lastans-1+39989)%39989+1; // no UB
            printf("%d\n",lastans=query(1,1,39989,k).second);
        }
        else
        {
            scanf("%d%d%d%d",&x0,&y0,&x1,&y1);
            x0=(x0+lastans-1+39989)%39989+1; x1=(x1+lastans-1+39989)%39989+1;
            y0=(y0+lastans-1+1000000000)%1000000000+1;
            y1=(y1+lastans-1+1000000000)%1000000000+1;
            if (x0>x1) swap(x0,x1),swap(y0,y1);
            add(x0,y0,x1,y1);
            update(1,1,39989,x0,x1,cnt);
        }
    } return 0;
} 吉司机线段树 (Segment Tree beats!) 兔队线段树 (楼房重建)

从《楼房重建》出发浅谈一类使用线段树维护前缀最大值的算法

using namespace std;
const int N=1e5+500,M=1<<18|7;
typedef long long ll;
int n,q,id[M],cnt[M];
ll h[N];
bool gt(int p1,int p2)
{
    if (!p2) return h[p1];
    return h[p1]*p2>h[p2]*p1;
}
void build(int u,int l,int r)
{
    id[u]=l; cnt[u]=1;
    if (l==r) return ;
    int mid=(l+r)>>1;
    build(u<<1,l,mid); build(u<<1|1,mid+1,r);
}
int calc(int u,int l,int r,int p)
{
    if (l==r) return gt(l, p);
    int mid=(l+r)>>1;
    if (gt(id[u<<1],p)) return calc(u<<1,l,mid,p)+cnt[u];
    else return calc(u<<1|1,mid+1,r,p);
}
void modify(int u,int l,int r,int p)
{
    if (l==r) return ;
    int mid=(l+r)>>1;
    if (p<=mid) modify(u<<1,l,mid,p);
    else modify(u<<1|1,mid+1,r,p);
    id[u]=gt(id[u<<1|1],id[u<<1])?id[u<<1|1]:id[u<<1];
    cnt[u]=calc(u<<1|1,mid+1,r,id[u<<1]);
}
int main()
{
    scanf("%d%d",&n,&q); build(1,1,n);
    int p,x;
    while (q--)
    {
        scanf("%d%d",&p,&x);
        h[p]=x; modify(1,1,n,p);
        printf("%d\n",calc(1,1,n,0));
    }
}

平衡树

普通平衡树：

AVL 树

using namespace std;
const int N=1e5+15;
struct AVLTree
{
private:
    struct Node{int l,r,val,height,size;}avl[N];
    int cnt,root;
    inline void newnode(int &now,int val){avl[now=++cnt].val=val; avl[cnt].size=1;}
    inline void update(int now)
    {
        avl[now].size=avl[avl[now].l].size+avl[avl[now].r].size+1;
        avl[now].height=std::max(avl[avl[now].l].height,avl[avl[now].r].height)+1;
    }
    inline int BF(int now){return avl[avl[now].l].height-avl[avl[now].r].height;}
    inline void lrotate(int &now)
    {
        int r=avl[now].r; avl[now].r=avl[r].l; avl[r].l=now; now=r;
        update(avl[now].l); update(now);
    }
    inline void rrotate(int &now)
    {
        int l=avl[now].l; avl[now].l=avl[l].r; avl[l].r=now; now=l;
        update(avl[now].r); update(now);
    }
    inline void check(int &now)
    {
        int nf=BF(now);
        if (nf>1)
        {
            int lf=BF(avl[now].l);
            if (lf>0) rrotate(now);
            else lrotate(avl[now].l),rrotate(now);
        } else if (nf<-1)
        {
            int rf=BF(avl[now].r);
            if(rf<0) lrotate(now);
            else rrotate(avl[now].r),lrotate(now);
        } else if (now) update(now);
    }
    void ins(int &now,int val)
    {
        if (!now) newnode(now,val);
        else if(val<avl[now].val) ins(avl[now].l,val);
        else ins(avl[now].r,val);
        check(now);
    }
    int find(int &now,int fa)
    {
        int ret;
        if (!avl[now].l){ret=now; avl[fa].l=avl[now].r;}
        else{ret=find(avl[now].l,now); check(now);}
        return ret;
    }
    void del(int &now,int val)
    {
        if (val==avl[now].val)
        {
            int l=avl[now].l,r=avl[now].r;
            if (!l||!r) now=l+r;
            else
            {
                now=find(r,r);
                if (now!=r) avl[now].r=r;
                avl[now].l=l;
            }
        }
        else if (val<avl[now].val) del(avl[now].l,val);
        else del(avl[now].r,val);
        check(now);
    }
public:
    inline void ins(int val){ins(root,val);}
    inline void del(int val){del(root,val);}
    int getrank(int val)
    {
        int now=root,rank=1;
        while (now)
        {
            if (val<=avl[now].val) now=avl[now].l;
            else{rank+=avl[avl[now].l].size+1; now=avl[now].r;}
        } return rank;
    }
    int getval(int rank)
    {
        int now=root;
        while (now)
        {
            if (avl[avl[now].l].size+1==rank) break;
            else if (avl[avl[now].l].size>=rank) now=avl[now].l;
            else{rank-=avl[avl[now].l].size+1; now=avl[now].r;}
        } return avl[now].val;
    }
    inline int pre(int x){return getval(getrank(x)-1);}
    inline int nxt(int x){return getval(getrank(x+1));}
}BST; Splay

Zig-Zag:

using namespace std;
const int N=1e5+15;
struct ZigZag_SplayTree
{
private:
    struct Node{int l,r,val,size,cnt;}spl[N];
    int cnt,root;
    inline void newnode(int& now,int& val){spl[now=++cnt].val=val; ++spl[cnt].size; ++spl[cnt].cnt;}
    inline void update(int now){spl[now].size=spl[spl[now].l].size+spl[spl[now].r].size+spl[now].cnt;}
    inline void zig(int& now)
    {
        int l=spl[now].l; spl[now].l=spl[l].r; spl[l].r=now; now=l;
        update(spl[now].r); update(now);
    }
    inline void zag(int& now)
    {
        int r=spl[now].r; spl[now].r=spl[r].l; spl[r].l=now; now=r;
        update(spl[now].l); update(now);
    }
    void Splay(int x,int& y)
    {
        if (x==y) return ;
        int& l=spl[y].l,&r=spl[y].r;
        if (x==l) zig(y);
        else if(x==r) zag(y);
        else
        {
            if (spl[x].val<spl[y].val)
            {
                if (spl[x].val<spl[l].val) Splay(x,spl[l].l),zig(y),zig(y);
                else Splay(x,spl[l].r),zag(l),zig(y);
            }
            else
            {
                if (spl[x].val>spl[r].val) Splay(x,spl[r].r),zag(y),zag(y);
                else Splay(x,spl[r].l),zig(r),zag(y);
            }
        }
    }
    inline void delnode(int now)
    {
        Splay(now,root);
        if (spl[now].cnt>1) spl[now].size--,spl[now].cnt--;
        else if (spl[root].r)
        {
            int p=spl[root].r;
            while (spl[p].l) p=spl[p].l;
            Splay(p,spl[root].r); spl[spl[root].r].l=spl[root].l; root=spl[root].r; update(root);
        }
        else root=spl[root].l;
    }
    void ins(int& now,int& val)
    {
        if (!now) newnode(now,val),Splay(now,root);
        else if (val<spl[now].val) ins(spl[now].l,val);
        else if (val>spl[now].val) ins(spl[now].r,val);
        else{++spl[now].size; ++spl[now].cnt; Splay(now,root);}
    }
    void del(int now,int& val)
    {
        if (spl[now].val==val) delnode(now);
        else if (val<spl[now].val) del(spl[now].l,val);
        else del(spl[now].r,val);
    }
public:
    inline void ins(int val){ins(root,val);}
    inline void del(int val){del(root,val);}
    int getrank(int val)
    {
        int now=root,rank=1;
        while (now)
        {
            if (spl[now].val==val){rank+=spl[spl[now].l].size; Splay(now,root); break;}
            if (val<=spl[now].val) now=spl[now].l;
            else{rank+=spl[spl[now].l].size+spl[now].cnt; now=spl[now].r;}
        } return rank;
    }
    int getval(int rank)
    {
        int now=root;
        while (now)
        {
            int lsize=spl[spl[now].l].size;
            if (lsize+1<=rank&&rank<=lsize+spl[now].cnt){Splay(now,root); break ;}
            else if (lsize>=rank) now=spl[now].l;
            else{rank-=lsize+spl[now].cnt; now=spl[now].r;}
        } return spl[now].val;
    }
    inline int pre(int x){return getval(getrank(x)-1);}
    inline int nxt(int x){return getval(getrank(x+1));}
}BST; 替罪羊树

using namespace std;
const int N=1e5+15;
struct tzy
{
private:
    static constexpr double alpha=0.75;
    struct Node
    {
        int l,r,val;
        int size,fact;
        bool exist;
    }tr[N];
    int cnt,root;
    inline void newnode(int &now,int val){now=++cnt; tr[now].val=val; tr[now].size=tr[now].fact=1; tr[now].exist=true;}
    inline bool imbalence(int now){return (max(tr[tr[now].l].size,tr[tr[now].r].size)>tr[now].size*alpha)||
                                          (tr[now].size-tr[now].fact>tr[now].size*0.3);                   }
    vector<int> v;
    void ldr(int now)
    {
        if (!now) return;
        ldr(tr[now].l);
        if (tr[now].exist) v.push_back(now);
        ldr(tr[now].r);
    }
    void lift(int l,int r,int &now)
    {
        if (l==r){now=v[l]; tr[now].l=tr[now].r=0; tr[now].size=tr[now].fact=1; return ;}
        int m=(l+r)>>1;
        while ((l<m)&&(tr[v[m]].val==tr[v[m-1]].val)) --m;
        now=v[m];
        if (l<m) lift(l,m-1,tr[now].l);
        else tr[now].l=0;
        lift(m+1,r,tr[now].r);
        tr[now].size=tr[tr[now].l].size+tr[tr[now].r].size+1;
        tr[now].fact=tr[tr[now].l].fact+tr[tr[now].r].fact+1;
    }
    void rebuild(int &now)
    {
        v.clear(); ldr(now);
        if (v.empty()){now=0; return ;}
        lift(0,v.size()-1,now);
    }
    void update(int now,int end)
    {
        if (!now) return;
        if (tr[end].val<tr[now].val) update(tr[now].l,end);
        else update(tr[now].r,end);
        tr[now].size=tr[tr[now].l].size+tr[tr[now].r].size+1;
    }
    void check(int &now,int end)
    {
        if (now==end) return;
        if (imbalence(now)){rebuild(now); update(root,now); return ;}
        if (tr[end].val<tr[now].val) check(tr[now].l,end);
        else check(tr[now].r,end);
    }
    void ins(int &now,int val)
    {
        if (!now){newnode(now,val); check(root,now); return ;}
        ++tr[now].size; ++tr[now].fact;
        if (val<tr[now].val) ins(tr[now].l,val);
        else ins(tr[now].r,val);
    }
    void del(int now,int val)
    {
        if (tr[now].exist&&tr[now].val==val){tr[now].exist=false; tr[now].fact--; check(root,now); return ;}
        tr[now].fact--;
        if (val<tr[now].val) del(tr[now].l,val);
        else del(tr[now].r,val);
    }
public:
    inline void ins(int val){ins(root,val);}
    inline void del(int val){del(root,val);}
    int getrank(int val)
    {
        int now=root,rank=1;
        while (now)
        {
            if (val<=tr[now].val) now=tr[now].l;
            else {rank+=tr[now].exist+tr[tr[now].l].fact; now=tr[now].r;}
        } return rank;
    }
    int getval(int rank)
    {
        int now=root;
        while (now)
        {
            if (tr[now].exist&&tr[tr[now].l].fact+tr[now].exist==rank) break;
            else if (tr[tr[now].l].fact>=rank) now=tr[now].l;
            else {rank-=tr[tr[now].l].fact+tr[now].exist; now=tr[now].r;}
        } return tr[now].val;
    }
    inline int pre(int x){return getval(getrank(x)-1);}
    inline int nxt(int x){return getval(getrank(x+1));}
}BST; fhq-Treap

using namespace std;
const int N=1e5+15;
static mt19937 rnd(19260817);
struct fhq_treap
{
private:
    struct Node{int l,r,val,size,key;}fhq[N];
    int cnt,root;
    inline int newnode(int val){fhq[++cnt].val=val; fhq[cnt].key=rnd(); fhq[cnt].size=1; return cnt;}
    inline void update(int now){fhq[now].size=fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;}
    void split(int now,int val,int& x,int& y)
    {
        if (!now) x=y=0;
        else
        {
            if (fhq[now].val<=val){x=now; split(fhq[now].r,val,fhq[now].r,y);}
            else{y=now; split(fhq[now].l,val,x,fhq[now].l);}
            update(now);
        }
    }
    int merge(int x,int y)
    {
        if (!x||!y) return x+y;
        if (fhq[x].key>fhq[y].key){fhq[x].r=merge(fhq[x].r,y); update(x); return x;}
        else{fhq[y].l=merge(x,fhq[y].l); update(y); return y;}
        return 0;
    }
#define def1 static int x,y;
#define def2 static int x,y,z;
public:
    inline void ins(int val){def1; split(root,val,x,y); root=merge(merge(x,newnode(val)),y);}
    inline void del(int val)
    {
        def2;
        split(root,val,x,z); split(x,val-1,x,y);
        y=merge(fhq[y].l,fhq[y].r); root=merge(merge(x,y),z);
    }
    inline int getrank(int val){def1; split(root,val-1,x,y); int ans=fhq[x].size+1; root=merge(x,y); return ans;}
    inline int getval(int rank)
    {
        int now=root;
        while (now)
        {
            if (fhq[fhq[now].l].size+1==rank) break;
            else if (fhq[fhq[now].l].size>=rank) now=fhq[now].l;
            else{rank-=fhq[fhq[now].l].size+1; now=fhq[now].r;}
        } return fhq[now].val;
    }
    inline int pre(int val)
    {
        def1;
        split(root,val-1,x,y); int now=x;
        while (fhq[now].r) now=fhq[now].r;
        int ans=fhq[now].val; root=merge(x,y); return ans;
    }
    inline int nxt(int val)
    {
        def1;
        split(root,val,x,y); int now=y;
        while (fhq[now].l) now=fhq[now].l;
        int ans=fhq[now].val; root=merge(x,y); return ans;
    }
#undef def1
#undef def2
}BST; Treap SBT

using namespace std;
const int N=2e5+5;
typedef long long ll;
struct SBT
{
private:
    struct node{int l,r,val,size;}sbt[N];
    int cnt,root;
    inline void lrotate(int& now)
    {
        int r=sbt[now].r;
        sbt[now].r=sbt[r].l; sbt[r].l=now;
        sbt[r].size=sbt[now].size; sbt[now].size=sbt[sbt[now].l].size+sbt[sbt[now].r].size+1;
        now=r;
    }
    inline void rrotate(int& now)
    {
        int l=sbt[now].l;
        sbt[now].l=sbt[l].r; sbt[l].r=now;
        sbt[l].size=sbt[now].size; sbt[now].size=sbt[sbt[now].l].size+sbt[sbt[now].r].size+1;
        now=l;
    }
    void maintain(int& t,bool fl)
    {
        if (!fl)
        {
            if (sbt[sbt[sbt[t].l].l].size>sbt[sbt[t].r].size) rrotate(t);
            else if (sbt[sbt[sbt[t].l].r].size>sbt[sbt[t].r].size) lrotate(sbt[t].l),rrotate(t);
            else return ;
        }
        else
        {
            if (sbt[sbt[sbt[t].r].r].size>sbt[sbt[t].l].size) lrotate(t);
            else if (sbt[sbt[sbt[t].r].l].size>sbt[sbt[t].l].size) rrotate(sbt[t].r),lrotate(t);
            else return ;
        }
        maintain(sbt[t].l,false); maintain(sbt[t].r,true);
        maintain(t,true); maintain(t,false);
    }
    void ins(int& t,int& v)
    {
        if (t)
        {
            ++sbt[t].size;
            if (v<sbt[t].val) ins(sbt[t].l,v);
            else ins(sbt[t].r,v);
            maintain(t,v>=sbt[t].val);
        }
        else
        {
            ++cnt; t=cnt;
            sbt[t].val=v; sbt[t].size=1;
            sbt[t].l=sbt[t].r=0;
        }
    }
    int del(int& t,int v)
    {
        int ans=0; --sbt[t].size;
        if ((v==sbt[t].val)||((v<sbt[t].val)&&!sbt[t].l)||((v>sbt[t].val)&&!sbt[t].r))
        {
            ans=sbt[t].val;
            if (!sbt[t].l||!sbt[t].r) t=sbt[t].l+sbt[t].r;
            else sbt[t].val=del(sbt[t].l,sbt[t].val+1);
            return ans;
        }
        else
        {
            if (v<sbt[t].val) return del(sbt[t].l,v);
            else return del(sbt[t].r,v);
        }
    }
    bool find(int& t,int& v)
    {
        if (!t) return 0;
        if (v<sbt[t].val) return find(sbt[t].l,v);
        else return (sbt[t].val==v)||find(sbt[t].r,v);
    }
    int getval(int& t,int k) // recursion
    {
        if (k==sbt[sbt[t].l].size+1) return sbt[t].val;
        if (k<=sbt[sbt[t].l].size) return getval(sbt[t].l,k);
        else return getval(sbt[t].r,k-1-sbt[sbt[t].l].size);
    }
    int getrank(int& t,int& v) // recursion
    {
        if (!t) return 1;
        if (v<=sbt[t].val) return getrank(sbt[t].l,v);
        else return sbt[sbt[t].l].size+1+getrank(sbt[t].r,v);
    }
public:
    SBT(){cnt=root=0; sbt[0].size=0;}
    inline void ins(int val){ins(root,val);}
    inline void del(int val){del(root,val);}
    inline int getval(int rk){return getval(root,rk);}
    inline int getrank(int val){return getrank(root,val);}
    inline int pre(int x){return getval(getrank(x)-1);}
    inline int nxt(int x){return getval(getrank(x+1));}
}BST; vector

using namespace std;
struct VectorTree
{
private:
    vector<ll> v;
public:
#define LWBp lower_bound(v.begin(),v.end(),val) // pointer
#define LWB  LWBp-v.begin()                     // value
    inline void clear(){v.clear();}
    VectorTree(){clear();}
    inline void ins(ll val){v.insert(LWBp,val);}
    inline void del(ll val){v.erase(LWBp,LWBp+1);}
    inline int getrank(ll val){return LWB+1;}
    inline ll getval(unsigned rk){return v[rk-1];}
    inline ll pre(ll x){return getval(getrank(x)-1);}
    inline ll nxt(ll x){return getval(getrank(x+1));} // suf
    inline size_t size(){return v.size();}
#undef LWBp
#undef LWB
}BST;

文艺平衡树：

Splay

const int N = 3e5+500;
int n, m, val[N];
struct Splay
{
    int root, fa[N], ch[N][2], siz[N], lazy[N],  cc;
    inline void pushup(int u){siz[u] = siz[ch[u][0]] + siz[ch[u][1]] + 1;}
    inline bool son(int u){return u == ch[fa[u]][1];}
    inline void rotate(int x)
    {
        int y = fa[x], z = fa[y], chk = son(x);
        ch[z][son(y)] = x; fa[x] = z;
        ch[y][chk] = ch[x][chk^1]; fa[ch[x][chk^1]] = y;
        ch[x][chk^1] = y; fa[y] = x;
        pushup(y); pushup(x);
    }
    inline void splay(int x, int to = 0)
    {
        while (fa[x] != to)
        {
            int y = fa[x];
            if (fa[y] != to) rotate(son(y) == son(x) ? y : x);
            rotate(x);
        } if (!to) root = x;
    }
    inline void pushdown(int x)
    {
        if (lazy[x])
        {
            lazy[ch[x][0]] ^= 1; lazy[ch[x][1]] ^= 1;
            swap(ch[x][0], ch[x][1]);
            lazy[x] = 0;
        }
    }
    inline void insert(int k)
    {
        int x = root, f = 0;
        while (x && (k != val[x])){f = x; x = ch[x][k > val[x]];}
        x = ++cc;
        if (f) ch[f][k > val[f]] = x;
        fa[x] = f; ch[x][0] = ch[x][1] = lazy[x] = 0;
        siz[x] = 1; val[x] = k;
        splay(x);
    }
    inline int kth(int k)
    {
        int x = root;
        while (true)
        {
            pushdown(x);
            if (k > siz[ch[x][0]] + 1){k -= siz[ch[x][0]] + 1; x = ch[x][1];}
            else if (k <= siz[ch[x][0]]) x = ch[x][0];
            else return x;
        }
    }
    inline void reverse(int l, int r)
    {
        int p = kth(l-1), s = kth(r+1);
        splay(p); splay(s, p);
        lazy[ch[s][0]] ^= 1;
    }
    inline void ldr(int x)
    {
        if (!x) return ;
        pushdown(x);
        ldr(ch[x][0]);
        if ((val[x] > 1) && (val[x] < n+2)) printf("%d ", val[x]-1);
        ldr(ch[x][1]);
    }
    Splay(){root = cc = 0;}
}T;
// T.reverse(l+1, r+1) fhq-Treap

const int N=1e5+15;
static mt19937 rnd(19260817);
struct revfhq
{
private:
    struct Node{int l,r,val,size; bool reversed;}fhq[N];
    int cnt,root;
    inline int newnode(int val){fhq[++cnt].val=val; fhq[cnt].size=1; fhq[cnt].reversed=false; return cnt;}
    inline void update(int now){fhq[now].size=fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;}
    inline void pushdown(int now)
    {
        swap(fhq[now].l,fhq[now].r);
        fhq[fhq[now].l].reversed^=1; fhq[fhq[now].r].reversed^=1;
        fhq[now].reversed=false;
    }
    void split(int now,int siz,int &x,int &y)
    {
        if (!now) x=y=0;
        else
        {
            if (fhq[now].reversed) pushdown(now);
            if (fhq[fhq[now].l].size<siz){x=now; split(fhq[now].r,siz-fhq[fhq[now].l].size-1,fhq[now].r,y);}
            else{y=now; split(fhq[now].l,siz,x,fhq[now].l);}
            update(now);
        }
    }
    int merge(int x,int y)
    {
        if(!x||!y) return x+y;
        if (int(rnd())%(fhq[x].size+fhq[x].size)<fhq[x].size)
        {
            if (fhq[x].reversed) pushdown(x);
            fhq[x].r=merge(fhq[x].r,y); update(x); return x;
        }
        else
        {
            if (fhq[y].reversed) pushdown(y);
            fhq[y].l=merge(x,fhq[y].l); update(y); return y;
        }
        return 0;
    }
public:
    inline void reverse(int l,int r)
    {
        static int x,y,z;
        split(root,l-1,x,y); split(y,r-l+1,y,z);
        fhq[y].reversed^=1; root=merge(merge(x,y),z);
    }
    inline void ldr(int now)
    {
        if (!now) return ;
        if (fhq[now].reversed) pushdown(now);
        ldr(fhq[now].l); printf("%d ",fhq[now].val); ldr(fhq[now].r);
    }
    inline void ldr(){ldr(root);}
    inline void insLE(int i){root=merge(root,newnode(i));}
}BST;

二逼平衡树：

珂朵莉树 (ODT)

k-D Tree

动态树

持久化数据结构

背包 DP

多项式乘法

高精度

正整数高精 整数高精 浮点数高精

见 此题 附件 .

浮点数高精 - plus int128

偏序

三维偏序

CDQ 分治

using namespace std;
const int N=2e5+500;
typedef long long ll;
int n,m,k,cnt[N],ans[N];
struct Node{int a,b,c;}a[N];
struct Answer{int a,b,c,cnt,ans;}b[N];
template<typename T>
struct FenwickTree{/*这里应有一个树状数组*/};
FenwickTree<int> e;
bool cmp1(const Node& x,const Node& y)
{
    if (x.a==y.a)
    {
        if (x.b==y.b) return x.c<y.c;
        return x.b<y.b;
    } return x.a<y.a;
}
bool cmp2(const Answer& x,const Answer& y)
{
    if (x.b==y.b) return x.c<y.c;
    return x.b<y.b;
}
void cdq(int l,int r)
{
    if (l==r) return ;
    int mid=(l+r)>>1;
    cdq(l,mid); cdq(mid+1,r);
    sort(b+l,b+mid+1,cmp2);
    sort(b+mid+1,b+r+1,cmp2);
    int j=l;
    for (int i=mid+1;i<=r;i++)
    {
        while ((b[i].b>=b[j].b)&&(j<=mid)){e.add(b[j].c,b[j].cnt); ++j;}
        b[i].ans+=e.query(b[i].c);
    }
    for (int i=l;i<j;i++) e.add(b[i].c,-b[i].cnt);
}
int main()
{
    scanf("%d%d",&n,&k); e.resize(k);
    for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c);
    sort(a+1,a+1+n,cmp1);
    int cc=0;
    for (int i=1;i<=n;i++)
    {
        ++cc;
        if ((a[i].a!=a[i+1].a)||(a[i].b!=a[i+1].b)||(a[i].c!=a[i+1].c))
        {
            ++m;
            b[m].a=a[i].a; b[m].b=a[i].b; b[m].c=a[i].c;
            b[m].cnt=cc; cc=0;
        }
    }
    cdq(1,m);
    for (int i=1;i<=m;i++) ans[b[i].ans+b[i].cnt-1]+=b[i].cnt;
    for (int i=0;i<n;i++) printf("%d\n",ans[i]);
    return 0;
} k-D Tree bitset

悬线法

矩形面积并

自适应辛普森积分

自适应辛普森积分

牛顿迭代

牛迭

模拟退火 (SA)

SA

Fibonacci 数列

统一了线性递推的简单做法

递推 矩阵快速幂 扩域 斐波那契循环节

邪门算法

Dancing Links (DLX) Berlekamp-Massey 算法 (BM) 动态图连通性

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章

第15章 高并发服务器编程（1）_非阻塞I/O模型
探讨Service Mesh中一种更高效的代理模式
主席树+二分 p4602

4

LeetCode 周赛上分之旅 #49 再探内向基环树

5

文心一言 VS 讯飞星火 VS chatgpt （104）-- 算法导论10.1 2题

6

hdu6138（后缀数组）

7

hdu2825（AC 自动机）

8

Dlang 并行化

9

文心一言 VS 讯飞星火 VS chatgpt （87）-- 算法导论8.2 4题

10

LeetCode 周赛上分之旅 #44 同余前缀和问题与经典倍增 LCA 算法