数据结构口胡记录

cqbzlzh / 2023-08-16 / 原文

数据结构口胡记录

114514天没写博客了（悲）

Bear and Bad Powers of 42

$tag$：线段树，势能分析

原问题不好直接做，考虑转化维护信息

首先可以发现42的幂次并不多,所以每次操作3到停止的次数并不多，因此可以用线段树多次打区间加标记。

问题转化为看一个区间内是否存在42的倍数，因为区间不存在42的倍数等价于区间每个数与它到下一个42次幂的差的最小值不为0，考虑维护这个差值即可。

每次打完标记后若有小于零的差值，就暴力递归到这些叶子节点，修改其到下一个幂次的差值，实际上因为42幂次分布稀疏，差值跨过0的次数并不多，所以复杂度正确。

注意到一个有区间推平标记的节点可以等价于叶子节点一样修改，不用往下递归，就避免推平可能造成一个区间的差值反复横跳。

Naive Operations思路类似，简单很多。

前进四

$tag$：吉司机线段树，离线处理

$n\log n^2$的方法显然，但是过不了。

发现修改的本质是对于后缀取$min$，需要维护时间和位置两个维度，因此考虑离线询问，按照位置排序，建一棵维护当前位置每个时间后缀最小值的$Sgt$，支持区间取$min$和询问单点被取$min$时被修改次数，直接吉司机即可。

Tree Generator™

$tag$：线段树

首先括号序列有一个性质：一个连续的括号序列去掉所有匹配的括号对后剩下的就是树上两点之间的链长。

因此题意转化为求出原序列的一个子区间使其非匹配括号数量最多。将(转化为1，)转化为-1，可以直接用线段树以类似GSS的方式维护，记录强制/非强制选择左右端点和的最大值分类讨论$pushup$即可。

    struct Node{
        int l,r;
        int sum,lmx,rmn,ans,lmd,rmd,md;
    }t[MAXN<<2];
    void pushup(int p){
        t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
        t[p].lmx=max(t[p<<1].lmx,t[p<<1].sum+t[p<<1|1].lmx);
        t[p].rmn=min(t[p<<1|1].rmn,t[p<<1|1].sum+t[p<<1].rmn);
        t[p].lmd=max(t[p<<1].lmd,max(t[p<<1|1].lmd-t[p<<1].sum,t[p<<1].md+t[p<<1|1].lmx));
        t[p].rmd=max(t[p<<1|1].rmd,max(t[p<<1].rmd+t[p<<1|1].sum,t[p<<1|1].md-t[p<<1].rmn));
        t[p].md=max(t[p<<1].md+t[p<<1|1].sum,t[p<<1|1].md-t[p<<1].sum);
        t[p].ans=max(max(t[p<<1].ans,t[p<<1|1].ans),max(t[p<<1|1].lmd-t[p<<1].rmn,t[p<<1].rmd+t[p<<1|1].lmx));
    }

Escape Through Leaf

$tag$：李超线段树，数据结构合并

李超树合并板子题，记住有这个东西就行了。

[NOI2022] 众数

$tag$：线段树，数据结构

当位置和值域询问分离的时候，考虑用位置有关的基本数据结构维护。

$deque$空间大，不要随便乱开，可以用$list$替代,$list$的$splice$可以$O(1)$插入。

V

$tag$：吉司机线段树，维护函数

转化标记的思想比较神仙。

首先正常的带区间加的吉司机线段树是$n\log n^2$的。

设标记$(val,mx)$表示先加$val$再对$mx$取$max$，三个操作可以分别表示为$(x,-INF)$,$(-x,0)$,$(-INF,x)$，而两个标记是直接可以合并成$(a.val+b.val,max(a.mx+b.val,b.mx))$的。

$f(x)$为值$x$经过标记后的值，不难发现是一个先平行于$x$轴再斜率为1的折线，取两条折线的最大值仍然是一条折线的形式，因此可以比$max$维护区间标记历史最值。

直接用线段树维护标记即可。

同时这种方式也可以推广，~~感觉比吉司机树好写还更快~~。

[BJOI2014] 大融合

$tag$：$LCT$

$LCT$维护子树信息。

因为$Splay$中虚边是认父不认子的，考虑对于每个节点定义$siz[x]$为其子树大小,$siz2[x]$为其虚儿子子树大小之和，那么$pushup$的时候有$siz[x]=siz[ls]+siz[rs]+siz2[x]+1$。

其中$siz2[x]$应该在断开或者加入一条虚边时得到更新，发现只有$access$和$link$中会出现加虚边，然后就做完了。

[NOI2021] 轻重边

$tag$：树链剖分，线段树

修改时不好直接维护于链相连的边，因此考虑从点入手。我们可以将每次链的操作转化为对链上点的操作，每次对链上的点区间赋一种新的颜色，那么那么两个点之间是重边等价于两个点的颜色相同，写一棵支持区间赋值和询问区间相邻元素相同的个数线段树就行了。

注意询问时答案与合并的顺序有关，两个节点向上爬时需分别维护两条链上的答案，最后再合并起来，以及注意两条链合并起来时应该是判断$lval$相同与否。

struct Node{
    int l,r,ans;
    int lval,rval,tag;
    void pushup(Node x,Node y){
        ans=x.ans+y.ans;
        if (x.rval==y.lval) ans++;
        lval=x.lval;rval=y.rval;
    }
}t[MAXN<<2];

int query(int x,int y){
    Sgt::Node ansx,ansy;
    ansx.ans=ansy.ans=0;
    ansx.lval=-114514;ansx.rval=-114515;
    ansy.lval=-114516;ansy.rval=-114517;
    while(top[x]!=top[y]){
        if (dep[top[x]]>dep[top[y]]){
            ansx.pushup(Sgt::query(1,dfn[top[x]],dfn[x]),ansx);
            x=fa[top[x]];
        }
        else{
            ansy.pushup(Sgt::query(1,dfn[top[y]],dfn[y]),ansy);
            y=fa[top[y]];
        }
    }
    if (dfn[x]>dfn[y]) ansx.pushup(Sgt::query(1,dfn[y],dfn[x]),ansx);
    else ansy.pushup(Sgt::query(1,dfn[x],dfn[y]),ansy);
    int res=ansx.ans+ansy.ans;
    if (ansx.lval==ansy.lval) res++;
    return res;
}

同时，维护链及其相邻节点还可以用毛毛虫剖分来做，以后有时间再来补。

[SDOI2017] 树点涂色

$tag$：$LCT$

首先因为每次加入的都是一种新的颜色，并且是直接将$x$到根节点染色，所以有每种颜色的点在树上构成一条链，且深度单调递增。

再由于每次修改都是一个点到根节点，可以发现如果直接用$LCT$维护原树，每次修改一直接$access$到根，那么某个点的答案就是向上跳到根时所经过的虚边的数量。

考虑魔改$LCT$，用$LCT$每条实链维护一个颜色段，那么在$access$的时候，$ch[x][1]$所在子树由于断边答案全部加一，$y$所在子树答案全部加一。由于已经用$LCT$维护了颜色段，还需要其它数据结构维护答案，直接树剖+区间加区间最大值线段树即可。

对于询问2答案即为$ans(x)+ans(y)-2*ans(lca(x,y))+1$。

P7739 [NOI2021] 密码箱

$tag$：线段树，矩阵乘法，动态dp

首先考虑$f$，假设前面几项得到的答案分数形式$ \frac{x}{y} $ 为$(x,y)$，那么下一项应该是$(y,y\times a_{i}+x)$，可以用矩阵乘法加速。

那么有

\[ \left[\begin{array}{c} x & y \\ \end{array}\right] \times \left[\begin{array}{c} 0 & 1\\ 1 & a_i\\ \end{array}\right] = \left[\begin{array}{c} y & y\times a_i+x\\ \end{array}\right] \]

再尝试将$W,E$两种操作用矩乘形式表示出来

$W$很简单：

\[ \left[\begin{array}{c} 0 & 1\\ 1 & a_i \end{array}\right] \times \left[\begin{array}{c} 1 & 1\\ 0 & 1 \end{array}\right] = \left[\begin{array}{c} 0 & 1\\ 1 & a_i+1 \end{array}\right] \]

再考虑$E$,按照最后一位的值分类讨论。

若最后一位不是1,那么有

\[ \left[\begin{array}{c} 0 & 1\\ 1 & a_i \end{array}\right] \times \left[\begin{array}{c} 1 & -1\\ 0 & 1 \end{array}\right] \times \left[\begin{array}{c} 1 & 1\\ 0 & 1 \end{array}\right] \times \left[\begin{array}{c} 1 & 1\\ 0 & 1 \end{array}\right] = \left[\begin{array}{c} 0 & 1\\ 1 & a_i \end{array}\right] \times \left[\begin{array}{c} 0 & -1\\ 1 & 2 \end{array}\right] \]

在考虑最后一位为1的情况，发现此时序列操作后为$(x+1,1)$，与最后一位不为1的序列$(x,0,1,1)$经过$f$计算后结果都为$\frac{x+1}{x+2}$，故二者转移矩阵是相同的。

那么考虑用平衡树维护$W,E$构成的操作序列，发现值取反和位置翻转标记维护思想可以采用[HNOI2011] 括号修复 / [JSOI2011]括号序列的思想，对于一个节点维护其在当前，值取反，位置翻转，值和位置同时翻转的矩阵子树乘积。$pushtag$的时候直接打标记,将当前值和对应取反操作的矩阵交换，另外两个矩阵也交换即可。

Little Pony and Lord Tirek

$tag$：分块，颜色段均摊

由颜色段均摊可以得到，我们在一个区间没有被推平标记$tag$时可以直接暴力修改后打上$tag$，有$tag$时考虑$O(1)$计算答案再更新标记即可，复杂度是正确的。

对于这道题，考虑分块，难点在于如何快速计算答案。可以预处理出$sum_{p,t}$表示第$p$个块在被推平为$0$后第$t$秒的和，显然$t$只用处理到$1e5$。单独考虑块内每个值在每个时刻的贡献，设$k_i=\lfloor \frac{m_i}{r_i} \rfloor$发现时间在$[1,k_i]$这个数的贡献为$r_i$，在$k_i+1$时刻贡献为$m_i \% r_i$，此后的贡献都为0。发现每次修改时贡献的二次差分只会修改3个位置。最后块内两次前缀和就可以求出$sum_{p,t}$

再维护每个块一个上次修改的时间$tim_p$,$pushdown$时块内下传完推平标记后再暴力将每个$a_i$修改即可。

void build(){
    len=sqrt(n);block=n/len;
    if (len*block!=n) block++;
    for (int i=1;i<=block;i++){
        L[i]=R[i-1]+1;
        R[i]=min(i*len,n);
        for (int j=L[i];j<=R[i];j++) belong[j]=i;
        memset(delta,0,sizeof delta);
        for (int j=L[i];j<=R[i];j++){
            if (!r[j]) continue;
            int t=m[j]/r[j],val=m[j]%r[j];
            delta[1]+=r[j];delta[t+1]-=r[j]-val;delta[t+2]-=val;
        }        
        for (int j=1;j<MAXN;j++) delta[j]+=delta[j-1];
        for (int j=1;j<MAXN;j++) delta[j]+=delta[j-1];
        for (int j=1;j<MAXN;j++) sum[i][j]=delta[j];
    }
}

void pushdown(int p,int t){
    if (tag[p]){
        for (int i=L[p];i<=R[p];i++) a[i]=0;
        tag[p]=0;
    }
    int d=t-tim[p];
    for (int i=L[p];i<=R[p];i++){
        a[i]=min((ll)m[i],a[i]+1ll*d*r[i]);
    }
    tim[p]=t;
}

ll query(int t,int l,int r){
    int q=belong[l],p=belong[r];
    ll ans=0;
    if (q==p){
        pushdown(q,t);
        for (int i=l;i<=r;i++){
            ans+=a[i];
            a[i]=0;
        }
        return ans;
    }
    ans+=query(t,l,R[q]);
    ans+=query(t,L[p],r);
    for (int i=q+1;i<p;i++){
        if (tag[i]){
            int d=min(100000,t-tim[i]);
            ans+=sum[i][d];
        }
        else ans+=query(t,L[i],R[i]);
        tag[i]=1;tim[i]=t;
    }
    return ans;
}