2026牛客寒假营 第一场 补题笔记

I. AND vs MEX

statement

给定区间 $[l,r]$，可以任意次操作从区间中选若干个数字，把它们的按位与加入集合 $S$，求 $\operatorname{MEX}{(S)}$ 的最大值。$l \le r < 2^{30}$ 。

Solution

首先显然答案最大是 $r+1$ 。
如果 $l=0$，那么显然答案可以取到 $r+1$；如果 $l,r$ 二进制位数相同，那么所有数的最高位一定是 $1$ ，答案只能是 $0$ 。
如果 $r$ 比 $l$ 的二进制位数高出至少 $2$ 位，那么我们一样可以构造出 $[0,l-1]$ 的数，答案为 $r+1$ 。
最麻烦的是 $r$ 比 $l$ 只高一位的情况。
我们可以构造出 $[0,p=r-\operatorname{highbit}(r)]$之间的数 和大于 $l_p$ 的数（定义 $l_p$ 为 $l$ 只保留开头连续的 $1$，比如 $l=11101001$ 时，$l_p=11100000$）。

Code

void solve(){
    cin>>l>>r;
    if(l==0){
        cout<<r+1<<'\n';
        return;
    }
    int n=lg2(l),m=lg2(r);
    if(n==m){
        cout<<0<<'\n';
        return;
    }
    if(m-n>=2){
        cout<<r+1<<'\n';
        return;
    }
    int p=r-(1<<m);
    if(l-p<=1){
        cout<<r+1<<'\n';
        return;
    }
    int lp=0;
    for(int i=n;i>=0;i--){
        if(!(l&(1<<i))){
            break;
        }else{
            lp+=(1<<i);
        }
    }
    if(lp-p<=1){
        cout<<r+1<<'\n';
    }else{
        cout<<p+1<<'\n';
    }
}

D. Sequence Coloring

Statement

给定一个长度为 $n$ 的序列，其中 $a_i > 0$ 表示白色元素，$a_i = 0$ 表示黑色元素。初始你可以选择任意至多 $k$ 个白色元素将其变为红色。从第 $1$ 秒开始的每一秒，所有当前的红色元素会同步进行扩散。位置 $i$ 的红色元素会将右侧区间 $[i+1, \min(n, i+a_i)]$ 内的所有白色元素染成红色（黑色元素不会被染红，也不阻碍扩散）。求出最短时间使得所有的白色元素最终被染红。$n \le 5 \times 10^5$ 。

Solution

对时间进行二分。

Code

#define int long long
int n,k,a[N],nxt[N]={};
bool check(int t){
    int cnt=0;
    for(int i=1;i<=n;){
        if(a[i]==0){
            i++;
            continue;
        }
        int j=i;
        for(int k=1;k<=t;k++){
            if(j>n)break;
            j=nxt[j];
        }
        cnt++;
        i=j+1;
    }
    return cnt<=k;
}
void solve(){
    cin>>n>>k;
    int cnt=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i])cnt++;
        nxt[i]=max(nxt[i-1],a[i]+i);
    }
    if(cnt<=k){
        cout<<0<<endl;
        return;
    }
    int l=0,r=n+1;
    while(l<r){
        int mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<(l>n?-1:l)<<endl;
}

F. Permutation Counting

Statement

有一个长度为 $n$ 的隐藏排列 $p$ ，给定 $m$ 条约束 $(l_i,r_i,k_i)$ 代表 $[p_{l_i},p_{r_i}]$ 的最大值为 $k_i$，求符合约束的排列的个数，答案对 $998244353$ 取模。$n,m \le 2 \times 10^6$ 。

Solution

从小到大枚举 $k$ ,对于 $k$ 对应的若干个区间，显然 $k$ 一定要放在这些区间的交集上，而小于 $k$ 的数则应该放在这些区间的并集里（一定可以把这个并集放满，否则答案不存在）。

那么我们需要一个数据结构来维护某个区间内有多少个空位，并且这个数据结构应该支持一次性的区间赋值（被赋值之后就不会回去）。我们可以使用并查集，一个点被赋值就把它和它的父亲节点合并，查询时从区间左端点往右跳，经过的集合个数就是答案。

Code

#define int long long
const int mod = 998244353;
using namespace std;
const int N = 2e6+10;
int n,m;
bool vis[N]={};int la[N],ra[N],lb[N],rb[N],fa[N];
inline int find(int x){
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
inline int query(int l,int r){
    int u=l,ret=0;
    while(u<r){
        if(find(u)==u){
            u++;ret++;
        }else{
            u=find(u);
        }
    }
    return ret+(int)(find(r)==r);
}
inline void modify(int l,int r){
    int u=l;
    while(u<r){
        if(find(u)==u){
            fa[u]=find(u+1);
        }
        u=find(u);
    }
    if(find(r)==r){
        fa[r]=find(r+1);
    }
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n+1;i++){
        la[i]=-1e8,ra[i]=1e8;
        lb[i]=1e8,rb[i]=-1e8;
        fa[i]=i;
        vis[i]=0;
    }
    for(int i=1;i<=m;i++) {
        int l,r,x;cin>>l>>r>>x;
        vis[x]=1;
        la[x]=max(la[x],l);ra[x]=min(ra[x],r);
        lb[x]=min(lb[x],l);rb[x]=max(rb[x],r);
    }
    int remain=0;
    int ans=1;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            remain++;continue;
        }
        if(la[i]>ra[i]){
            puts("0");
            return;
        }
        ans=ans*query(la[i],ra[i])%mod;
        int cnt=query(lb[i],rb[i]);
        modify(lb[i],rb[i]);
        ans=ans*A(remain,cnt-1)%mod;
        remain-=cnt-1;
        if(ans==0)break;
    }
    ans=ans*fac[remain]%mod;
    cout<<ans<<'\n';
}

J. MST Problem

Statement

有一个 $n$ 个点的无向完全图，连接 $(u,v)$ 的边权为 $a_u+a_v$ ，删去 $m$ 条边，求最小生成树的边权和。$n,m \le 3 \times 10^5$ 。

Solution

线段树优化 Prim 。线段树维护：

namespace tr{
    pii V[N*4];// 还未加入连通块的权值最小的点
    pii E[N*4];// 能连到连通块的权值最小的边
    int b[N*4];// 懒标记，当前区间的所有点都能连到的 连通块里的最小点
};

如何处理删边？每次将一个新的点加入连通块，被删去的包含它的边将 $[1,n]$ 分割成若干个区间，对这些边进行区间修改即可，由于删边总和为 $m$ 条，区间修改的次数也是合理的。

Code

#include<bits/stdc++.h>
#define pii pair<int,int>
#define int long long
using namespace std;
const int N = 3e5+100;
int n,m,a[N];
int si,s;
namespace tr{
    pii V[N*4],E[N*4];
    int b[N*4];
};
using namespace tr;
void push_up(int p){
    V[p]=min(V[p*2],V[p*2+1]);
    E[p]=min(E[p*2],E[p*2+1]);
}
void build(int l,int r,int p){
    b[p]=1e18;
    if(l==r){
        V[p]={a[l],l};
        E[p]={1e18,l};
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,p*2);
    build(mid+1,r,p*2+1);
    push_up(p);
}
void push_down(int p){
    for(int son=p*2;son<=p*2+1;son++){
        if(b[son]>b[p]){
            b[son]=b[p];
            if(E[son].first>b[son]+V[son].first){
                E[son]={b[son]+V[son].first,V[son].second};
            }
        }
    }
}
void merge(int l,int r,int p,int x){
    if(l==r){
        V[p]={1e18,x};
        E[p]={1e18,x};
        return;
    }
    int mid=(l+r)/2;
    push_down(p);
    if(x<=mid)merge(l,mid,p*2,x);
    if(x>mid)merge(mid+1,r,p*2+1,x);
    push_up(p);
}
void modify(int s,int t,int l,int r,int p,int x){
    if(s<=l&&r<=t){
        if(b[p]<=x)return;
        b[p]=x;
        if(E[p].first>x+V[p].first){
            E[p]={x+V[p].first,V[p].second};
        }
        return;
    }
    int mid=(l+r)/2;
    push_down(p);
    if(s<=mid)modify(s,t,l,mid,p*2,x);
	if(t>=mid+1)modify(s,t,mid+1,r,p*2+1,x);
	push_up(p);
}
vector<int> G[N];
void solve(){
    cin>>n>>m;
    si=0,s=1e18;
    for(int i=1;i<=n;i++){
        G[i].clear();
        G[i].push_back(i);
        cin>>a[i];
        if(a[i]<s){
            s=a[i];si=i;
        }
    }
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1;i<=n;i++)sort(G[i].begin(),G[i].end());
    build(1,n,1);
    int ans=0;
    int u=si;
    for(int i=1;i<=n-1;i++){
        merge(1,n,1,u);
        int l=1;
        for(int v:G[u]){
            int r=v-1;
            if(l<=r){
                modify(l,r,1,n,1,a[u]);
            }
            l=v+1;
        }
        if(l<=n){
            modify(l,n,1,n,1,a[u]);
        }
        u=E[1].second;
        ans+=E[1].first;
        if(ans>=1e18){
            break;
        }
    }
    cout<<(ans>=1e18?-1:ans)<<'\n';
}
signed main(){
    int T;cin>>T;while(T--)solve();
    return 0;
}