Tricks / 性质

AC_Lover · 2025-02-12 19:54:11 · 算法·理论

Trick

曼哈顿\to切比雪夫

(x,y)\to (x+y,x-y) \\ dis(A,B)=\max(|x_i-x_j|,|y_i-y_j|)

区间\mathrm{LCA}深度

\mathrm{depth}_{\mathrm{LCA}([l,r])}=\min_{i=l}^{r-1}\{\mathrm{depth}_{\mathrm{LCA}(i,i+1)}\}

判断序列一个区间内某些数出现次数是否是k的倍数

哈希思想，先给这个数列中每一个数设一个非0的随机权值，数i赋的权值为w_i。搞一个前缀和，统计前缀中每个数出现次数，将这个出现次数对k取模，i出现的次数取模后记为v_i，然后考虑对每一个前缀做一个哈希，记前缀和i的哈希值为has_i=(\sum v_iw_i)\bmod P，其中P为一个大数，取P=2^{64}-1即可。查询区间[l,r]时，若has_r=has_{l-1}，那么就可以近似认为满足条件

这个\mathrm {Trick}很具有启发性

"伪素数":

对于一个数列，如果其中的数值域很大，要将这些数分解不一定要用分解质因数，可以使用伪素数\mathrm {Trick}

伪素数集合\mathcal{P} 的定义是这个集合中的元素可以唯一分解给定数列里的数，并且集合中的元素两两互质。

考虑增量构造\mathcal{P} ，如果要插入一个新的数x，扫描一遍现在的\mathcal {P}，如果有d=\gcd(\mathcal {P}_i,x)>1，那么考虑将\mathcal {P}_i替换成\frac{\mathcal {P}_i}{d},d，这样这两个数依然可以分解\mathcal {P}_i，由于要满足x与\mathcal {P}中的数都互质，令x\leftarrow \frac{x}{d}，因为\gcd(\frac{x}{d},\frac{\mathcal {P}_i}{d})=1，但是此时可能有d=\gcd(\frac{\mathcal {P}_i}{d},d)>1，于是递归处理，具体的，Ins(a,b)表示a为原来\mathcal {P}中的元素，现在要插入b，进行调整。

如果d=\gcd(a,b)>1，说明要继续调整，令a\leftarrow \frac{a}{d},b\leftarrow \frac{b}{d}，然后将b插入\mathcal {P}中，调用Ins(\mathcal {P}_{SZ(\mathcal {P})},d)，调整，然后调用Ins(a,d)，调整。

最后，如果x>1，将x插入即可。

插入后，要将\mathcal {P}更新，将其中的1和重复的数删去

这样维护\mathcal {P}的复杂度是O(n\log V)，单次分解复杂度为O(\log V)

简要代码：

void Ins(int &a,int &b)
{
    int d=gcd(a,b);
    a/=d,b/=d;
    ++psz;
    P[psz]=b;
    if (d==1) return;
    Ins(P[psz],d),Ins(a,d);
}

void Insert(int x)
{
    for (int i=1;i<=psz;i++)
    {
        int d=gcd(P[i],x);
        if (d==1) continue;
        P[i]/=d,x/=d;
        Ins(P[i],d);
    }
    if (x>1) P[++psz]=x;

    int id=0;
    for (int i=1;i<=psz;i++)
    {
        if (P[i]>1)
        {
            P[++id]=P[i];
        }
    }
    psz=id;
    sort(P+1,P+psz+1);
    psz=unique(P+1,P+psz+1)-P-1;
}

\mathrm {Kruskal}重构树

在\mathrm{Kruskal}求最小生成树的算法中，假设要合并以u为根的集合和以v为根的集合，考虑新建一个点\mathrm{rt}，将其作为u和v合并的集合的根，即将其作为u和v的父节点，然后将\mathrm{rt}的点权设为这条边的边权

这样建出来的树就是\mathrm{Kruskal}重构树：

我们记dis(u,v)表示原图中u到v的所有简单路径上的最大边权的最小值

此时有性质：

原图中两点之间的dis

$=$ $\mathrm{Kruskal}$重构树上两点$\mathrm{LCA}$的点权并且原图中与一个点的$dis\le x$的点一定是$\mathrm{Kruskal}$重构树中一个点的子树的叶子节点所以如果我们要对于点$u$求出所有满足$dis(u,v)\le x$的点$v$，可以在$\mathrm{Kruskal}$重构树中从点$u$往上跳，找到最高的满足点权$\le x$的点，这样这个点的子树中的叶子节点就是所有满足条件的点$v$。对于最小值的最大值也是同理，直接求最大生成树即可基本代码： ```cpp void dfs(int u) { if (u<=n) sz[u]=1; for (int i=h[u];i!=-1;i=ne[i]) { int v=e[i]; fa[v][0]=u; dfs(v); sz[u]+=sz[v]; } } void Kruskal() { sort(edge+1,edge+m+1,cmp); for (int i=1;i<=(n<<1);i++) p[i]=i; idx=n; memset(h,-1,sizeof(h)); for (int i=1;i<=m;i++) { int u=edge[i].u,v=edge[i].v,w=edge[i].w; int fu=find(u),fv=find(v); if (fu!=fv) { p[fu]=p[fv]=++idx; add(idx,fu),add(idx,fv); val[idx]=w; fat[fu]=fat[fv]=true; } } for (int i=1;i<=idx;i++) { if (!fat[i]) { dfs(i); } } for (int t=1;t<=20;t++) { for (int i=1;i<=idx;i++) { fa[i][t]=fa[fa[i][t-1]][t-1]; } } } int query(int x,int v) { for (int t=20;t>=0;t--) { int up=fa[x][t]; if (up && val[up] op v) x=up; } return x; } ``` --- ### $\mathrm{ODT}$珂朵莉树颜色均摊用于解决区间覆盖类问题，时间复杂度$O(n\log n)

初始化时插入[1,n+1]

板子：

namespace ODT
{
    struct Node
    {
        int l,r; 
        mutable int v;
        Node(int _l,int _r,int _v) { l=_l,r=_r,v=_v; }
        bool operator < (const Node &o) const { return l<o.l; }
    };
    struct odt
    {
        set<Node> st;
        typedef set<Node>::iterator itr;
        itr split(int x)
        {
            if (x>n) return st.end();
            itr it=--st.upper_bound({x,0,0});
            int l=it->l,r=it->r,v=it->v;
            if (l==x) return it;
            st.erase(it); st.insert({l,x-1,v});
            return st.insert({x,r,v}).first;
        }
        void assign(int l,int r,int v)
        {
            itr rit=split(r+1),lit=split(l); st.erase(lit,rit);
            itr p=st.insert({l,r,v}).first; lit=rit=p;
            while (lit->v==p->v) lit--; lit++;
            while (rit->v==p->v) rit++; rit--;
            l=lit->l,r=rit->r; st.erase(lit,++rit); st.insert({l,r,v});
        }
        PII bel(int x) 
        {
            itr it=--st.upper_bound({x,0,0});
            return {it->l,it->r};
        }
        int ask(int x) 
        {
            itr it=--st.upper_bound({x,0,0});
            return it->v;
        } 
    };

} using namespace ODT;

极小\mathrm{mex}区间

记\mathrm{MEX}(l,r)=\mathrm{mex}\{a_l,\dots,a_r\}

[l,r]$是极小的$\mathrm{mex}$区间表示$[l,r]$满足不存在$[l^\prime,r^\prime]\subset[l,r]$使得$\mathrm{MEX}(l^\prime,r^\prime)=\mathrm{MEX}(l,r)

结论：极小的\mathrm{mex}区间的个数是O(n)级别的，最多只有2n个

可以O(n\log n)求出所有极小\mathrm{mex}区间

记\mathrm{mex}_x表示所有\mathrm{MEX}(l,r)=x的极小\mathrm{mex}区间

考虑枚举x，表示用\mathrm{mex}_{x-1}来更新后面的区间，用L表示l左边第一个x-1出现的位置，R表示r右边第一个x-1出现的位置，然后更新\mathrm{mex}_{\mathrm{MEX}(L,r)},\mathrm{mex}_{\mathrm{MEX}(l,R)}

然后在\mathrm{mex}_x中处理出极小的\mathrm{mex}区间即可。

其中在线求区间\mathrm{mex}可以用主席树O(\log n)，由于极小\mathrm{mex}区间的个数是O(n)级别的，所以总时间复杂度是O(n\log n)

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

using namespace std;

const int N=100010,NLOGN=N*17;
int n;
int a[N];

vector<int> pos[N];
int getL(int l,int x) 
{
    int p=lower_bound(pos[x].begin(),pos[x].end(),l)-pos[x].begin();
    if (!p) return 0;
    return pos[x][p-1];
} 
int getR(int r,int x)
{
    int p=upper_bound(pos[x].begin(),pos[x].end(),r)-pos[x].begin();
    if (p==pos[x].size()) return n+1;
    return pos[x][p];
}

namespace Tr
{
    struct Node
    {
        int lc,rc;
        int mi;
    } tr[N*4+NLOGN];
    int rt[N],idx;  

    int build(int l,int r)
    {
        int u=++idx;
        tr[u].mi=0;
        if (l==r) return u;
        int mid=(l+r)>>1;
        tr[u].lc=build(l,mid);
        tr[u].rc=build(mid+1,r);
        return u;
    }

    void pushup(int u)
    {
        tr[u].mi=1e9;
        if (tr[u].lc) tr[u].mi=min(tr[u].mi,tr[tr[u].lc].mi);
        if (tr[u].rc) tr[u].mi=min(tr[u].mi,tr[tr[u].rc].mi);
    }

    int modify(int p,int l,int r,int x,int v)
    {
        int q=++idx;
        tr[q]=tr[p];
        if (l==r)
        {
            tr[q].mi=v;
            return q;
        }
        int mid=(l+r)>>1;
        if (x<=mid) tr[q].lc=modify(tr[p].lc,l,mid,x,v);
        else tr[q].rc=modify(tr[p].rc,mid+1,r,x,v);
        pushup(q);
        return q;
    }

    int query(int u,int l,int r,int x)
    {
        if (l==r) return l;
        int mid=(l+r)>>1;
        if (tr[tr[u].lc].mi>=x) return query(tr[u].rc,mid+1,r,x);
        else return query(tr[u].lc,l,mid,x);
    }

    int Mex(int l,int r) { return query(rt[r],0,n,l); }
}

using namespace Tr;

struct Range 
{ 
    int l,r; 
    bool operator < (const Range& o) const
    {
        if (l!=o.l) return l>o.l;
        return r<o.r;
    }
}; 
vector<Range> mex[N];

int main()
{
    cin >> n;
    for (int i=1;i<=n;i++) cin >> a[i];
    for (int i=1;i<=n;i++) pos[a[i]].push_back(i);

    rt[0]=build(0,n);
    for (int i=1;i<=n;i++) rt[i]=modify(rt[i-1],0,n,a[i],i);

    for (int i=1;i<=n;i++) 
    {
        if (a[i]) mex[0].push_back({i,i});
        else mex[1].push_back({i,i});
    }

    for (int x=1;x<=n;x++)
    {
        for (Range rg : mex[x-1])
        {
            int l=rg.l,r=rg.r;
            int L=getL(l,x-1),R=getR(r,x-1);
            if (L>0) mex[Mex(L,r)].push_back({L,r});
            if (R<=n) mex[Mex(l,R)].push_back({l,R});
        }
        sort(mex[x].begin(),mex[x].end());

        vector<Range> t;
        int nwr=1e9;
        for (Range rg : mex[x]) 
        {
            int l=rg.l,r=rg.r;
            if (r>=nwr) continue;
            t.push_back(rg);
            nwr=r;
        }
        mex[x]=t;
    }

    return 0;
}

集合哈希

对于需要维护一个集合是否存在等问题时，考虑使用集合哈希。对于集合值域的每个数i赋一个随机的权值w_i，此处可以使用mt19937_64来生成为\mathrm{ull}，然后对于一个集合\{x_1,x_2,\dots ,x_n\}，定义其权值为

\bigoplus_{i=1}^{n}w_{x_i}

然后就可以方便地进行集合加入、删除元素，同时维护整个集合

解递推式

对于形如 x_i=ax_{i-1}+b

考虑设常数c，满足 x_i+c=a(x_{i-1}+c)，解得c=\frac{b}{a-1}

于是x_i+\frac{b}{a-1}=a\left(x_{i-1}+\frac{b}{a-1}\right)

易得x_i+\frac{b}{a-1}=a^n\left(x_0+\frac{b}{a-1}\right)，得到通项

x_i=a^i\left(x_0+\frac{b}{a-1}\right)-\frac{b}{a-1}

二项式反演

通常用于解决 exactly n 类型的问题，即我们知道了满足至少 i 条限制的方案数为 g_i，想要知道恰好满足 i 条限制的方案数 f_n。

我们尝试用 f 表示出 g，显然的，我们从限制中钦定有 i 个限制是满足的，得到

g_i=\sum_{k\ge i} \binom{k}{i} f_k

运用二项式反演，有

f_n=\sum_{k\ge n}(-1)^{k-n}\binom{k}{n}g_k

`list` 链表合并

链表合并是 O(1) 的，即：

void join(list<int> &x,list<int> y) { x.splice(x.end(),y); }

性质

一个字符串存在k-周期等价于S[1,n-k]=S[k+1,n]
固定l，则\gcd_{l\le i\le r}a_i相同的极大r连续段只有O(\log V)个
若a>b，a\bmod b<\frac{a}{2}
V$个点，$E$条边的森林连通块个数是$V-E
a<b<c\Rightarrow \min(a\oplus b,b\oplus c)<a\oplus c
直径具有合并性质
以重心为根，其每个子节点子树大小\le \frac{n}{2}
图总度数是O(m)的，因此可以O(\sqrt{m})-O(\sqrt{m})根号分治。
每个点被扩展次数 \le 这个点的最短路
射线法：点在多边形内部 \Leftrightarrow 从这个点引出一条射线，与多边形有奇数个交点。
\begin{aligned} & \max_{S\subseteq V}\set{d_u\oplus d_v\oplus S}\\ &= \left(\min_{S_1\subseteq V}\set{d_u\oplus S_1}\right)\oplus \left(\max_{S_2\subseteq V}\set{d_v\oplus S_2}\right) \\ \end{aligned}
对于一个边集 S，其将树划分为 k 个连通块 \set{a_1,a_2,\dots,a_k}，则满足条件的生成树个数为：
f(S)=n^{k-2}\prod_{i=1}^k a_i
有 k 个叶子的树可以用 \left\lceil\frac{k}{2}\right\rceil 条路径覆盖。
x^n=\sum_{k}{n\brace k}x^{\underline{k}}