牛客练习赛102

A

对所有消息做一下前缀和，对每个人的消息做一下前缀和，分别判断是否有长度为 \(a,b\) 的连续段

B

考虑当前已经算出来前 \(i-1\) 个操作的最大值 \(x\)，那么第 \(i\) 个操作会把答案变为 \(\max(x+a_i,x \cdot b_i)\)

但是答案可能会爆ll，所以需要记录一下\(x\) 是否曾经大于 \(10^9\)，如果曾经大于 \(10^9\) 的话，只要 \(b_i \ne 1\)，那么就会选择 \(b_i\)

C

bool operator < (T a, T b) {
    return a.r == b.r ? a.l < b.l : a.r < b.r;
}

排了个序跑暴力就过了？

D

换根dp，分别dfs两遍

ll f[N], g[N]; // f: 子树中连通块个数；g: 与u相连的连通块个数 
void dfs(int u, int fa) {
    f[u] = g[u] = 1;
    for(int i = head[u] ; i ; i = rest[i]) {
        int v = to[i];
        if(v == fa) continue;
        dfs(v, u);
        ll newf = (f[u] + f[v] + g[u] * g[v] % mod) % mod;
        ll newg = (g[u] + g[u] * g[v] % mod) % mod;
        f[u] = newf;
        g[u] = newg;
        ans[id[i]][a[id[i]] == v ? 0 : 1] = f[v];
    }
//    printf("%d: f=%lld g=%lld\n", u, f[u], g[u]);
}

ll h[N], w[N]; // h: 不选子树的方案数；w: 不选子树包含u的方案数 

void dfs2(int u, int fa) {
    vector<ll> pre, sub;
    ll allsum = 0;
    for(int i = head[u] ; i ; i = rest[i]) {
        int v = to[i];
        if(v == fa) continue;
        pre.push_back((g[v] + 1) % mod);
        sub.push_back((g[v] + 1) % mod);
        allsum = (allsum + f[v]) % mod;
    }
    
    int n = pre.size(), idx = 0;
    for(int i = 1 ; i < n ; ++ i) pre[i] = pre[i - 1] * pre[i] % mod;
    for(int i = n - 2 ; i >= 0 ; -- i) sub[i] = sub[i + 1] * sub[i] % mod;
    for(int i = head[u] ; i ; i = rest[i]) {
        int v = to[i];
        if(v == fa) continue;
        ll cnt = (idx ? pre[idx - 1] : 1) * (idx + 1 < n ? sub[idx + 1] : 1) % mod * w[u] % mod; // 与u连通，不经过v子树的方案数 
        ll cutans = (cnt + h[u] - w[u] + allsum - f[v]) % mod;
        ans[id[i]][a[id[i]] == u ? 0 : 1] = cutans;
        
        w[v] = (cnt + 1) % mod;
        h[v] = (cutans + w[v]) % mod;
        
        ++ idx;
    }
    
    for(int i = head[u] ; i ; i = rest[i]) {
        int v = to[i];
        if(v == fa) continue;
        dfs2(v, u);
    }
}

E

F