蝶恋花（互测赛）题解

· · 题解

补题题号：U468736 - U468741

A.声渐悄

Subtask.1

博弈相关暴搜，或许需要子集枚举之类的东西，我没研究。

Subtask.3

考虑先手如何取最优，发现可以构造使得剩余的物品两两相邻，这样后手选择时每两个就必定会剩下一个，下一轮自己就可以选。按 n 对 3 取模的结果讨论发现答案为 2\lfloor\frac n3\rfloor+[n \bmod 3\ne0]。

最难做

我们先假设第一轮先手剩下一段长为 3 的连续段 a,b,c 不取。那么若 b\ge a+c，则直接取走 b 一定更优；否则 b<a+c，后手一定会先取 a+c，这样自己下一次取时也会取走 b，第一轮就取走 b 整体不劣。

所以先手可以在剩余连续段长度不超过 2 的前提下达到最优，因此进行 DP，设 f_i 表示先手第一轮取第 i 个时，前 i 个中先手能够获得的最大收益。转移为 f_i=\max(f_{i-2},f_{i-3}+\min(a_{i-2},a_{i-1}))+a_i。

意义即为中间留下一个则必为后手的，留两个的话后手会取较大的，自己可以获得较小的。答案为 \max(f_n,f_{n-1})，处理一下边界即可通过，时空复杂度 O(n)。

n=read();
for(int i=1;i<=n;i++) f[i]=a[i]=read();
for(int i=3;i<=n;i++) f[i]=max(f[i-2],f[i-3]+min(a[i-2],a[i-1]))+a[i];
print(max(f[n],f[n-1]));

B.乱红飞

Subtask.1

把 2^n 个点全建出来，直接树形 DP。设 f_u 表示以 u 为根的子树中包含 u 的连通块种类数，那么 f_u=\prod_{v\in son_u}(f_v+1)，也就是每个子树中选连通块的 f_v 种方案和不选的 1 种方案，乘法原理乘起来即可，时空复杂度 O(2^d)。代码我没写。

Subtask.2

发现对于满二叉树，同一层的点的子树结构完全相同，所以设 g_i 表示第 i 层点的 f 值，由于都有两个儿子，有 g_i=(g_{i+1}+1)^2，答案为 g_1。代码我没写，但是离正解已经很近了。

最难做

注：这里 s 字符串的下标为 [0,d-1]。

同 Subtask.2 一样，考虑把同一层的点按结构分类。这里按照该子树在第 d 层的点的情况分类，设第 0 类为第 d 层无结点的点，第 1 类为第 d 层结点全满的点，第 2 类为第 d 层部分有结点的点。显然每层最多只有一个第 2 类点。

那么设 g_{i,j},j\in[0,2] 表示第 i 层第 j 种点的 f 值，边界为 g_{d,1}=1。显然当 j\le 1 时有 g_{i,j}=(g_{i+1,j}+1)^2，问题在于 g_{i,2} 是怎么来的。

考虑算出第 i 层的第 2 类点在第 d 层的点数，发现这个数量是 s 的第 i 位直到结尾所表示的二进制数。那么从后往前第一个 1 处就是首次出现第 2 类点的层数。

在出现第 2 类点后，若 s_i=1，说明上一层的 2 类点并上了一个 1 类点，s_i=0 说明并上了一个 0 类点。因此有 g_{i,2}=(g_{i+1,2}+1)(g_{i+1,s_i}+1)，注意最终答案还要分讨一下。时空复杂度 O(d)。

cin>>d>>s,g[d][1]=1; bool tf=false;
for(int i=d-1;i>=1;i--)
{
    g[i][0]=(g[i+1][0]+1)*(g[i+1][0]+1)%mod,g[i][1]=(g[i+1][1]+1)*(g[i+1][1]+1)%mod;
    if(tf) g[i][2]=(g[i+1][2]+1)*(g[i+1][s[i]-'0']+1)%mod;
    else if(s[i]-'0') tf=true,g[i][2]=(g[i+1][1]+1)*(g[i+1][0]+1)%mod;
}
if(s[0]=='1') cout<<g[1][1]<<'\n';
else if(tf) cout<<g[1][2]<<'\n';
else cout<<g[1][0]<<'\n';

C.恨千缕

Subtask.1.2

考虑暴力，也就是记录下每缕思绪是否存在以及出现的时间，每次查询时枚举所有思绪判断是否符合题意，时间复杂度 O(nm)。代码我没写。

Subtask.3

根据题面中的形式化题意，第 j 天若第 i 缕思绪存在，则其状态与 (j-st_i) 对 p=(x_i+y_i) 取模的值有关。同时由于 st_i 是定值，所以本质上只与 j 对 p 取模的值有关。由于这个模数在本 Subtask 里很小，考虑开 p^2 大小的数组存储答案。

设 f_{p,i} 表示对 p 取模值为 i 的天数目前的答案。思绪出现时枚举 [0,p-1] 作为 i \bmod p 的结果，判断一下会对哪些余数造成贡献，存储在二维数组里，消失时把贡献撤销即可。查询只需要枚举 p，将所有 f_p 的贡献求和，时间复杂度 O(pm)，空间复杂度 O(p^2)。可以参考 Subtask.4 后的代码。

最难做

发现每缕思绪本质上是向若干个区间贡献 1，所以考虑维护差分序列，在处理到第 i 天时把前面的差分值加过来即可。但问题在于区间个数是 O(\frac{m}{x_i+y_i}) 级别的，可能会被卡到 O(m^2)，只能做 (x_i+y_i) 较大的。

同时由于Subtask.3 中的做法只能做 (x_i+y_i) 较小的，因此考虑按 (x_i+y_i) 分治，超过 B 的用差分做法，不超过 B 的用 Subtask.3 中的做法，时间复杂度为 O(mB+\frac{m^2}{B})，分析一下可得 B=\sqrt{m} 时最优，为 O(m\sqrt{m})。

考虑到 O(mB) 全部跑满，而 O(\frac{m^2}B) 完全跑不满，可以适当调低 B，但 std 仍使用了 B=\sqrt m。

n=read(),m=read(),B=sqrt(m/2);
for(int i=1;i<=n;i++) x[i]=read(),y[i]=read();
for(int i=1;i<=m;i++)
{
    int opt=read(),k=read(),tr=0,mo=(x[k]+y[k]);
    if(mo<=B)
    {
        if(opt==1)
        {
            st[k]=i; 
            for(int j=0;j<mo;j++) if(((j-st[k])%mo+mo)%mo>=x[k]) f[mo][j]++;
        }
        else for(int j=0;j<mo;j++) if(((j-st[k])%mo+mo)%mo>=x[k]) f[mo][j]--;
    }
    else
    {
        if(opt==1) 
        {
            st[k]=i;
            for(int j=i;j+x[k]<=m;j+=mo)
            {
                s[j+x[k]]++;
                if(j+mo<=m) s[j+mo]--;
            }
        }
        else for(int j=(i-st[k])/mo*mo+st[k];j+x[k]<=m;j+=mo)
        {
            if(j+x[k]>=i) s[j+x[k]]--;
            else s[i]--;
            if(j+mo<=m)
            {
                if(j+mo>=i) s[j+mo]++;
                else s[i]++;
            }
        }
    }
    for(int j=2;j<=B;j++) tr+=f[j][i%j];
    s[i]+=s[i-1],print(tr+s[i]),putchar('\n');
}

D.寄彩笺

Subtask.1

暴力枚举，分别枚举 A,B，对每个 B 在每个 A 中暴力查找个数。事实上这个点可以接受 O(k^{n+m}nm) 的复杂度。代码我没写。

正解思路

考虑求每个 B 在 A 中贡献的次数，但也不能暴力枚举 B，所以要用某种东西给 B 分类，使得同一类的 B 对答案的贡献相同。

先考虑 B 可重叠的贡献次数，这里长度 len=m，也就是在长为 n 的 A 中有 (n-len+1) 种位置，钦定这些位置后其他位置随便填。所以长为 len 的字符串可重叠的贡献次数为 (n-len+1)k^{n-len}。

接着考虑去掉重叠算多的贡献次数，发现前后两次会重叠当且仅当 B 的一段前缀与 B 的一段后缀相同，即若 B=STS，那么 STSTS 出现时就会导致重叠。这里 S,T 均为字符串，重叠部分 S 即为 B 的 border。

问题在于，若 border 长度超过 m 的一半导致其本身有重叠，或 border 有多个，就无法使用唯一的 STS 形式求解。然而，可以发现由于 border 完全相同，以上两种情况均会导致串内有三个或以上相同字符，而这在 B 中是不会出现的，具体见下图：

所以可以保证字符串没有或仅有一个 border，有则不会自己重叠，那么可以用唯一 border 的长度作为开头说的分类方式。枚举 border 的长度 x，从 k 个字母中选出 x 个作为 border S。用剩余的 (k-x) 个字母，每个使用不超过两次构成 border 中间的串 T，乘法原理乘起来就是这种 B 的总数量。

之后容斥求答案，即加上 STS 的贡献，减去 STSTS 的贡献，再加上 STSTSTS 的贡献，以此类推直到 STSTS\cdots TS 长度超过 n 时停止。当然这里的贡献均可重叠，这样能保证最终贡献的量为不重叠出现的次数。

这里要枚举 ST 的重复次数 i，但由于对于长度 x 只会枚举约 \frac nx 个次数，且 x 不会取满 [1,n]，所以复杂度不超过调和级数的 O(n\ln n)。注意特判无解，并单独处理一下没有 border 的情况即可。代码里的 p 数组记录的是 k 的若干次方。

if(k*2<m||n<m)
{
    cout<<0;
    return 0;
}
res=sol(k,m)*p[n-m]%mod*(n-m+1)%mod; int now=1;
for(int x=1;x*2<=m;x++) 
{
    now=now*(k-x+1)%mod;
    int ta=now*sol(k-x,m-2*x)%mod,w=1;
    for(int i=2; ;i++)
    {
        w*=-1;
        int len=m+(m-x)*(i-1);
        if(len>n) break;
        res=(res+ta*p[n-len]%mod*(n-len+1)%mod*w+mod)%mod;
    }
}
cout<<res;

但是还有一处没有解决，即 Sol 函数解决用 tk 种字母，每种字母使用不超过两次，组成的长为 tm 的字符串种类数，其中 tk\in [k-\lfloor\frac m2\rfloor,k],tm\in[m\bmod2,m]，以下给出解法：

Subtask.2.3

考虑 DP，设 f_{i,j} 表示长为 i 的字符串，其中 j 个字母使用了 2 次，剩余 (i-2j) 个字母使用了 1 次的方案数。转移只需要讨论第 i 个字符是否使用过，从 f_{i-1} 转移过来即可，答案为 \sum f_{tm,j}。

由于每次的 tk 不相同，每次都要重新用 O(m^2) 的时间复杂度 DP，O(m) 次询问的总时间复杂度为 O(m^3)。（由于跑不满，搬题人在原赛时写这个把 m\le2000 全卡过去了，所以这里最后开了 m\le3000）

int sol(int k,int m)
{
    f[0][0]=1; int res=0;
    for(int i=1;i<=m;i++) for(int j=0;j*2<=i;j++)
    {
        f[i][j]=f[i-1][j]*(k-(i-1-j))%mod;
        if((j-1)*2<=i-1) f[i][j]=(f[i][j]+f[i-1][j-1]*(i-1-2*(j-1))%mod)%mod;
    }
    for(int i=0;i*2<=m;i++) res=(res+f[m][i])%mod;
    return res;
}

最难做

枚举字符串中出现 2 次的字符数量 i，考虑组合计算方案数，结果为 \binom {tk}i \times \frac{A_{tm}^{2i}}{2^i}\times A_{tk-i}^{tm-2i}，前两项选出 i 个字符出现两次并安排好位置，最后一项对每个剩下的位置依次不重复地选一个剩下的字符。

由于 tk\ge k-\lfloor\frac m2\rfloor，考虑预处理 k 的下降幂，即 {fk}_i=\prod_{j=k-i+1}^k j，也就是从 k 开始向下前 i 个数的积，预处理 m 个即可。之后自己展开式子就行，要注意每次的 tk 不同，要把 [tk+1,k] 这一段的积约掉。

p[0]=p2[0]=fr[0]=fk[0]=1;
for(int i=1;i<=n;i++) p[i]=p[i-1]*k%mod,p2[i]=p2[i-1]*2%mod;
for(int i=1;i<=m;i++) fr[i]=fr[i-1]*i%mod;
for(int i=1;i<=min(m,k);i++) fk[i]=fk[i-1]*(k-i+1)%mod;
int sol(int tk,int tm)
{
    int res=0;
    for(int i=0;i*2<=tm;i++) if(tm-i<=tk)
    {
        int ts=1,dt=k-tk,dk=inv(fk[dt]);
        ts=ts*(fk[i+dt]*dk%mod)%mod*inv(fr[i])%mod;
        ts=ts*(fr[tm]*inv(fr[tm-i*2])%mod*inv(p2[i])%mod)%mod;
        ts=ts*(fk[tm-i+dt]*dk%mod*inv(fk[i+dt]*dk%mod)%mod)%mod;
        res=(res+ts)%mod;
    }
    return res;
}

F.重霄九

Subtask.1

每次询问直接对子树内每个点分别 O(n) 判断是否合法，时间复杂度 O(qn^2)。代码我没写。

Subtask.2-4

考虑类似线段树维护每个结点子树内的最大值，最小值和子树内合法结点的数量，修改时修改点权后将其到根路径上的所有结点依次重新维护，时间复杂度 O(qd)，d 为树的最大深度。由于数据随机时二叉树的期望深度为 O(\log n)，O(q\log n) 的时间复杂度可以通过。

struct tree
{
    int lc[N],rc[N],a[N],s[N],mx[N],mn[N],fa[N];
    bool f[N];
    void pushup(int u)
    {
        int tl=lc[u],tr=rc[u];
        mx[u]=max(max(mx[tl],mx[tr]),a[u]),mn[u]=min(min(mn[tl],mn[tr]),a[u]);
        f[u]=(a[u]>=mx[tl]&&a[u]<=mn[tr]&&f[tl]&&f[tr]),s[u]=s[tl]+s[tr]+f[u];
    }
    void build(int u)
    {
        if(lc[u]) build(lc[u]);
        if(rc[u]) build(rc[u]);
        pushup(u);
    }
    void change(int u,int x)
    {
        a[u]=mx[u]=mn[u]=x;
        while(u) pushup(u),u=fa[u];
    }
}T;
signed main()
{
    n=read(),Q=read();
    for(int i=1;i<=n;i++) T.lc[i]=read(),T.rc[i]=read(),T.fa[T.lc[i]]=T.fa[T.rc[i]]=i;
    for(int i=1;i<=n;i++) T.a[i]=T.mx[i]=T.mn[i]=read();
    T.mx[0]=-inf,T.mn[0]=inf,T.s[0]=0,T.f[0]=1,T.build(1);
    while(Q--)
    {
        int opt=read(),x=read();
        if(opt==1) 
        {
            int y=read();
            T.change(x,y);
        }
        else print(T.s[x]),putchar('\n');
    }
    return 0; 
}

最难做

发现树的形态不变，那么若子树是二叉搜索树，其中最大值和最小值的位置是确定的，分别为其最靠右和最靠左的结点。这里最靠某方向的点是指从根节点一直走该方向的儿子，直到这个儿子为空时所停的点。

同时若点 i 是二叉搜索树，那么其左右子树一定均为二叉搜索树，所以相对应的最值位置是固定的。可以预处理出每个结点左子树最靠右的结点 lx_i 和右子树最靠左的结点 rx_i。

根据定义，这个点合法只需要其左右儿子均合法且 a_{lx_i}\le a_i\le a_{rx_i}。同时由于每个点不可能同时是两个点的 lx，rx 也一样，加上其自身的限制，总共不超过 3 条，修改时重新判断一遍即可。

所以只要一棵子树内所有点都满足自身的限制，这棵子树就是二叉搜索树。考虑设 f_i 表示点 i 的限制是否不被满足，即满足则为 0，不满足则为 1，那么子树内所有点都满足限制当且仅当子树内 f_i 的和为 0。

考虑维护这个子树和 c_i，那么每个 f_i 都会给其到根的路径上点的 c_i 贡献，而答案为子树内 c_i=0 的个数，也就是子树内最小值为 0 时的最小值个数。所以用树剖 + 线段树实现路径加，同时维护子树最小值及个数即可，时间复杂度 O(q\log^2n)。

#include<iostream>
#include<vector> 
#define pii pair<int,int>
using namespace std; 
const int N=2e5+10;
int n,q,a[N],lc[N],rc[N],lx[N],rx[N],rm[N],lm[N],f[N];
void ini(int u)
{
    if(!u) return;
    ini(lc[u]),ini(rc[u]);
    rm[u]=rm[rc[u]],lm[u]=lm[lc[u]];//lm 和 rm 分别表示最靠左和最靠右的结点 
    if(!rm[u]) rm[u]=u;
    if(!lm[u]) lm[u]=u;
    lx[u]=rm[lc[u]],rx[u]=lm[rc[u]];
}
vector <int> lim[N],edge[N]; 
int ct,siz[N],de[N],fa[N],son[N],id[N],top[N],aa[N],tw[N]; 
void dfs(int u,int fat)
{
    fa[u]=fat,de[u]=de[fat]+1,siz[u]=1,tw[u]=f[u];
    for(int v:edge[u])
    {
        dfs(v,u),siz[u]+=siz[v],tw[u]+=tw[v];
        if(siz[son[u]]<siz[v]) son[u]=v;
    }
} 
void dfsb(int u,int to)
{
    top[u]=to,id[u]=++ct,aa[ct]=tw[u];
    if(!son[u]) return;
    dfsb(son[u],to);
    for(int v:edge[u]) if(v!=son[u]) dfsb(v,v);
}
struct sgmtt
{
    int t=1,lc[N*2],rc[N*2],tag[N*2]; pii a[N*2]; //最小值及个数 
    void pt(int u,int k) {a[u].first+=k,tag[u]+=k;}
    void pushdown(int u) {if(tag[u]) pt(lc[u],tag[u]),pt(rc[u],tag[u]),tag[u]=0;}
    void pushup(pii &u,pii tl,pii tr)
    {
        u.first=min(tl.first,tr.first),u.second=0;
        if(tl.first==u.first) u.second+=tl.second;
        if(tr.first==u.first) u.second+=tr.second;
    }
    void build(int u,int l,int r)
    {
        if(l==r) {a[u]={aa[l],1}; return;}
        int mid=(l+r)/2;
        lc[u]=++t,build(t,l,mid);
        rc[u]=++t,build(t,mid+1,r);
        pushup(a[u],a[lc[u]],a[rc[u]]);
    }
    void add(int u,int l,int r,int ll,int rr,int k)
    {
        if(l>=ll&&r<=rr) {pt(u,k); return;}
        int mid=(l+r)/2; pushdown(u);
        if(ll<=mid) add(lc[u],l,mid,ll,rr,k);
        if(rr>mid) add(rc[u],mid+1,r,ll,rr,k);
        pushup(a[u],a[lc[u]],a[rc[u]]);
    }
    pii check(int u,int l,int r,int ll,int rr)
    {
        if(l>=ll&&r<=rr) return a[u];
        int mid=(l+r)/2; pushdown(u);
        if(rr<=mid) return check(lc[u],l,mid,ll,rr);
        if(ll>mid) return check(rc[u],mid+1,r,ll,rr);
        pii res;
        pushup(res,check(lc[u],l,mid,ll,rr),check(rc[u],mid+1,r,ll,rr));
        return res;
    }
}T;
void addrt(int x,int k)
{
    while(top[x]!=1) T.add(1,1,n,id[top[x]],id[x],k),x=fa[top[x]];
    T.add(1,1,n,1,id[x],k);
} 
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>lc[i]>>rc[i];
    ini(1),a[0]=-1,a[n+1]=n+1;
    for(int i=1;i<=n;i++) cin>>a[i],lim[i].push_back(i);
    for(int i=1;i<=n;i++)
    {
        if(lc[i]) edge[i].push_back(lc[i]);
        if(rc[i]) edge[i].push_back(rc[i]);
        if(lx[i]) lim[lx[i]].push_back(i);
        if(rx[i]) lim[rx[i]].push_back(i);
        else rx[i]=n+1;
        f[i]=!(a[lx[i]]<=a[i]&&a[rx[i]]>=a[i]);
    }
    dfs(1,0),dfsb(1,1),T.build(1,1,n);
    while(q--)
    {
        int opt,x; cin>>opt>>x;
        if(opt==2)
        {
            pii te=T.check(1,1,n,id[x],id[x]+siz[x]-1);
            cout<<(te.first?0:te.second)<<'\n';
        }
        else
        {
            int y; cin>>y;
            for(int i:lim[x]) addrt(i,-f[i]);
            a[x]=y;
            for(int i:lim[x]) f[i]=!(a[lx[i]]<=a[i]&&a[rx[i]]>=a[i]),addrt(i,f[i]);
        }
    }
    return 0;
}

Ex.凭阑意

以下设 a_i 的值域为 V。

Subtask.1.2

发现答案上界为 \max a_i，因为 p=\max a_i 时，最大值变为 0，其他值不变，一定不会有相同元素。所以从小到大枚举 p，O(n) 用桶判重即可，总时间复杂度 O(Vn)。代码我没写。

Subtask.3

转换条件，发现 a_i\equiv a_j\bmod p 等价于 p\mid (a_i-a_j)，也就是说若存在 \left|a_i-a_j\right| 是 p 的倍数，则 p 不合法。所以可以 O(n^2) 枚举差值，再从小到大找倍数中没有差值的数。由于枚举倍数的时间复杂度为 O(V\ln V)，总时间复杂度为 O(n^2+V\ln V)。

for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(a[j]>a[i]) f[a[j]-a[i]]=1;
for(int i=1;i<=V;i++)
{
    for(int j=i*2;j<=V;j+=i)
    {
        f[i]|=f[j];
        if(f[i]) break;
    } 
    if(!f[i]) {print(i);break;}
}

Subtask.4

同 Subtask.3 思路相同，从小到大判断数是否能作为 p，同样枚举倍数来判断，时间复杂度 O(V\ln V)。现在的问题在于如何快速判断 a 中是否存在 x 作为差值。

考虑使用 bitset 优化，开值域大小的 bitset B 记录每个值是否存在，那么存在 x 作为差值当且仅当 B 左移或右移 x 位后按位与 B 的结果中有 1。

再开个数组记忆化，保证每个 x 只 check 一遍，时间复杂度 O(\frac{V^2}w)，总时间复杂度 O(V\ln V+\frac{V^2}w)。这也是最后一个 Subtask 值域缩小到 10^5 的原因，得到满分需要把后两个 Subtask 拼起来。

bitset <M> bs;
bool vis[N],ma[N];
bool check(int x)
{
    if(!vis[x])
    {
        vis[x]=1;
        if(((bs>>x)&bs).count()) ma[x]=1;
        else ma[x]=0;
    }
    return ma[x];
}
void solb()
{
    for(int i=1;i<=n;i++) bs[a[i]]=1;
    for(int i=2;i<=V/10;i++)// V/10 即为本 Subtask 的值域 10^5 
    {
        bool tf=true;
        for(int j=i;j<=V/10;j+=i) if(check(j)) {tf=false; break;}
        if(tf) {print(i); break;}
    }
}