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

C. 炮火轰炸

Statement

Solution

Code

int n,q;
map<pair<int,int>,int> mp; 
pair<int,int> p[N];//炮击点
int m;
pair<int,int> g[N];//“关键点”
int xx[]={0,0,1,1,1,-1,-1,-1},yy[]={1,-1,1,0,-1,1,0,-1};
map<int,vector<int>> p_x,p_y;//炮击点坐标
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        mp[{x,y}]=-1;
        p[i]={x,y};
        p_x[y].push_back(x);
        p_y[x].push_back(y);
    }
    for(auto& [x,v]:p_x){
        sort(v.begin(),v.end());
    }
    for(auto& [x,v]:p_y){
        sort(v.begin(),v.end());
    }
    for(int i=1;i<=n;i++){
        int x=p[i].first,y=p[i].second;
        for(int k=0;k<8;k++){
            pii pn={x+xx[k],y+yy[k]};
            if(!mp[pn]){
                g[++m]=pn;
                mp[pn]=m;
            }
        }
    }
    vector<int> qv;
    for(int i=1;i<=q;i++){
        int x,y;cin>>x>>y;
        if(mp[{x,y}]>0)qv.push_back(mp[{x,y}]);
        else{
            g[++m]={x,y};
            mp[{x,y}]=m;
            qv.push_back(mp[{x,y}]);
        }
    }
    for(int i=0;i<=m;i++){
        fa[i]=i;
    }
    for(int i=1;i<=m;i++){
        int x=g[i].first,y=g[i].second;
        auto ix2=lower_bound(p_x[y].begin(),p_x[y].end(),x);
        auto iy2=lower_bound(p_y[x].begin(),p_y[x].end(),y);
        if(ix2==p_x[y].begin()||ix2==p_x[y].end()||iy2==p_y[x].begin()||iy2==p_y[x].end()){
            merge(i,0);
        }
        if(iy2!=p_y[x].end()&&mp[{x,*iy2-1}]>0)merge(i,mp[{x,*iy2-1}]);
        if(ix2!=p_x[y].end()&&mp[{*ix2-1,y}]>0)merge(i,mp[{*ix2-1,y}]);
        if(iy2!=p_y[x].begin()&&mp[{x,*(iy2-1)+1}]>0)merge(i,mp[{x,*(iy2-1)+1}]);
        if(ix2!=p_x[y].begin()&&mp[{*(ix2-1)+1,y}]>0)merge(i,mp[{*(ix2-1)+1,y}]);
    }
    int fa0=find(0);
    for(int i:qv){
        if(fa0==find(i))puts("NO");
        else puts("YES");
    }
    return 0;
}

D. 数字积木

Statement

给定一棵有 $n$ 个结点的树，每个结点的权值构成排列 $\{0,1,\ldots,n-1\}$
对树上所有连通子图，计算其结点权值集合的 $\mathrm{MEX}$ 的总和，结果对 $10^9+7$ 取模。$1 \le n \le 2 \times 10^5$ 。

Solution

考虑从小到大枚举 $\mathrm{MEX}$ 值，因为要使得 $\mathrm{MEX}=k$ ，一定让 $[0,k-1]$ 全部在子图里，这个过程中符合要求的子图的个数一定是单调不增的。

我们以 $0$ 为根执行树状 dp ，dp[u] 表示以 $u$ 为根的子树的个数。

$\mathrm{MEX}$ 从 $k$ 到 $k+1$ 的过程中，新增了一个必须要连进子图的点 $k$ ，它与已有的必须连的子图之间形成了一个链，在这个链上做处理去除不合法的子图：

while(!vis[u]){
    Div(tmp,dp[u]+1);
    for(int v:G[u]){
        if(v==f[u])continue;
        Mul(tmp,dp[v]+1);
    }
    vis[u]=1;
    u=f[u];
}

由于这个过程涉及到模意义下的任意除法，我们需要进行零计数，维护当前乘积中为 $0$ 的因子数量 zero，以及所有非零因子的乘积。这样删除/加入一个因子时不需要逆元除以 0。

Code

#define int long long
const int N = 2e5+100;
const int mod = 1e9+7;
int inv(int x){return qpow(x,mod-2);}
inline void add(int &a,int b){a=(a+b)%mod;}
inline void mul(int &a,int b){a=(a*b)%mod;}
void dfs(int u,int fa){
    dp[u]=1;

    f[u]=fa;
    for(int v:G[u]){
        if(v==fa)continue;
        dfs(v,u);
        mul(dp[u],dp[v]+1);
    }
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        id[a[i]]=i;
    }
    for(int i=1;i<=n-1;i++){
        int u,v;cin>>u>>v;
        G[a[u]].push_back(a[v]);
        G[a[v]].push_back(a[u]);
    }
    dfs(0,-1);
    int tmp=dp[0];
    int zero=0;
    auto Div=[&](int &a,int b){
        if(b%mod==0)zero--;
        else a=(a*inv(b))%mod;
    };
    auto Mul=[&](int &a,int b){
        if(b%mod==0)zero++;
        else a=(a*b)%mod;
    };
    auto Val=[&](){
        if(zero)return 0LL;
        else return tmp;
    };
    int ans=0;
    vis[0]=1;
    for(int x=1;x<=n-1;x++){
        add(ans,Val());
        int u=x;
        while(!vis[u]){
            Div(tmp,dp[u]+1);
            for(int v:G[u]){
                if(v==f[u])continue;
                Mul(tmp,dp[v]+1);
            }
            vis[u]=1;
            u=f[u];
        }
    };
    add(ans,Val());
    cout<<ans<<'\n';
    return 0;
}

G.

Statement

给定一个数组 $a$，求对于所有可能的起点 $s \in [1, n]$，向右遍历并在当前累加和 $\ge a_i$ 时不断累加 $a_i$ 所能得到的总和，$n \le 2 \times 10^6$。

Solution

从小到大遍历 $i$，令 $v_s$ 为以 $s$ 为起点，以 $i$ 为终点时的答案。

那么每次遍历到一个新的 $i$，对于所有 $s$ 使得 $v_s \ge a_i$ ，令 $v_s \coloneqq v_s + a_i$ 。这个操作需要 FHQ Treap 维护。

FHQ Treap

Treap = Tree + Heap 。
二叉搜索树有一个性质：左子树的所有节点值 < 根节点值 < 右子树的所有节点值。如果我们把所有的 val 存在一棵 BST 里，当我们需要找 $\ge a_i$ 的数时，顺着树根找就能轻松把树按值分割。

如果插入的数据是有序的，会退化成一条链表，每次操作的时间复杂度从 $O(\log n)$ 退化成 $O(n)$。

为了防止 BST 退化，我们给每个节点额外随机分配一个 rnd。
我们在维护 BST 性质（按 val 排序）的同时，强制要求树的形态必须满足父节点的优先级 > 子节点的优先级（即形成一个堆）。可以证明只要优先级随机分配，树的期望高度就一定是 $O(\log n)$。

我们以 $a_i$ 为分界把树分裂成两部分 $x$ 和 $y$ ，对大于等于 $a_i$ 的那部分（ $y$ ）执行区间修改（使用 lazytag），再把 $x$ 、$a_i$、$y$ 三部分合并回去。

分裂 (Split)

按阈值 $v$，把一棵树拆成 $\le v$ 的 $X$ 树和 $> v$ 的 $Y$ 树。
自顶向下：

• 若当前节点 $\le v$：它和左子树全归 $X$。接下来去切它的右子树。
• 若当前节点 $>v$：它和右子树全归 $Y$。接下来去切它的左子树。

利用传引用 (&)，在向下递归的过程中，顺手把断开的树枝接到了正确的父节点上。

合并 (Merge)

前提是 $X$ 树里的所有值，必须已经 $\le Y$ 树里的所有值。
自顶向下：

• 比较 $X$ 和 $Y$ 根节点的 rnd。
• 若 $X$ 优先级大：$X$ 当新根。将 $X$ 的右子树和 $Y$ 树继续往下合并。
• 若 $Y$ 优先级大：$Y$ 当新根。将 $X$ 树和 $Y$ 的左子树继续往下合并。

Code

#include<bits/stdc++.h>
#define int long long
const int N = 2e6+100;
using namespace std;
int build(int v,int id){
    ++cnt;
    ls[cnt]=rs[cnt]=0;
    val[cnt]=v;
    b[cnt]=0;
    rnd[cnt]=rand();
    idx[cnt]=id;
    return cnt;
}
void pushdown(int p){
    if(b[p]){
        if(ls[p])val[ls[p]]+=b[p];b[ls[p]]+=b[p];
        if(rs[p])val[rs[p]]+=b[p];b[rs[p]]+=b[p];
        b[p]=0;
    }
}
void split(int p,int v,int &x,int &y){
    if(!p){
        x=y=0;return;
    }
    pushdown(p);
    if(val[p]<=v){
        x=p;
        // 分裂出来的 <= v 的那部分，我们要直接挂到 p 的右儿子上
        // 分裂出来的 > v 的那部分，归入 y
        split(rs[p],v,rs[p],y);
    }else{
        y=p;
         // 同理，分裂 p 的左子树 (ls[p])
        // <= v 的部分归 x 树，传 x
        // > v 的部分重新接回 p 的左儿子，传 ls[p]
        split(ls[p],v,x,ls[p]);
    }
}
int merge(int x,int y){
    if(!x||!y)return x|y;
    if(rnd[x]>rnd[y]){
        pushdown(x);
        rs[x]=merge(rs[x],y);
        return x;
    }else{
        pushdown(y);
        ls[y]=merge(x,ls[y]);
        return y;
    }
}
void getans(int p){
    if(!p)return;
    pushdown(p);
    ans[idx[p]]=val[p];
    getans(ls[p]);
    getans(rs[p]);
}
void solve(){
    cin>>n;
    cnt=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int root=0;
    for(int i=1;i<=n;i++){
        int x,y;
        split(root,a[i]-1,x,y);
        val[y]+=a[i];b[y]+=a[i];
        int z=build(a[i],i);
        root=merge(merge(x,z),y);
    }
    getans(root);
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<" ";
    }
    cout<<'\n';
}