Solved: 5/13 Rank:59

H

队友写的。签到题就不补了。

L

给定 n 个人，m 个不同的车站，求把人安排到车站中的方案数，考虑人的排列顺序以及强制每一个车站都要有人。

m \leq n \leq 10^5

经典组合问题。我们首先考虑对于所有的 n! 种排列来说，每一种排列可以对应的方案数。

发现先把 m 个人分配到车站之后，剩下的 n-m 个人就可以随意分配了。那么这个的方案数插板法一下显然有 \binom{n - m + (m - 1)}{m - 1} = \binom{n-1}{m-1} 就做完了，最终答案就是 n!\binom{n-1}{m-1}。

E

一栋 m 层的楼内有 n 台电梯，第 i 台会在 a_i 时刻启动并开始以 1 层 / 秒的速度上升。

你可以在所有电梯开始前将 2\to m-1 之间某些层的按钮按下，这样第一个到这层的电梯就会在这时暂停一秒。

求使第 i 台电梯第一个到楼顶的最小操作次数。

n \leq 5\times 10^5,m \leq 10^9

记录每个点的操作次数为 t_i，我们考虑以上问题实际上是一个偏序问题：对于两台电梯 i,j，我们需要满足以下条件则 j 先到达

• 若 i < j，那么有 a_i + \Delta + 1 \geq a_j
• 若 i > j，那么有 a_i + \Delta \geq a_j

按照 a_i 从小到大排序，维护一个树状数组就过了。时间复杂度 \mathcal{O}(n\log n)

const int N = 1e6 + 10;
int t[N],n,m,ans[N],tr[N];
int lowbit(int x) {return x & (-x);}
void modify(int x,int v) {for (;x <= n;x += lowbit(x)) tr[x] += v;}
int query(int x) {
    int ans = 0;
    for (;x;x -= lowbit(x)) ans += tr[x];
    return ans;
}
pii p[N];

signed main() {
    read(n,m);
    for (int i = 1;i <= n;++i) read(t[i]),p[i] = mp(t[i],i);
    sort(p + 1,p + 1 + n);
    int sum = 0;
    for (int i = 1;i <= n;++i) {
        sum += p[i].first;
        ans[p[i].second] = (p[i].first * i) - sum + query(p[i].second);
        modify(p[i].second,1);
    }
    for (int i = 1;i <= n;++i) {
        if (ans[i] > m - 2) puts("-1");
        else printf("%lld\n",ans[i]);
    }
    return 0;
}

I

给定一个 n(n\le 2000) 个节点的树，每个点都有点权 a_i 。

点 x 有 \frac{a_x}{\sum\limits_{i = 1}^{n}{a_i}} 的概率被选择为初始传染源。初始传染源只会有一个。

每个点都有一个概率 p_i （以分数的形式给出），表示，它周围相邻的点，如果有传染源的话。

• 有 p_i 的概率，这个点也变成传染源。
• 有 1-p_i 概率，这个点不会变成传染源，且之后也不会变成传染源。

问，感染恰好 k 个点的概率是多少。 (1\le k \le n)

考虑每个树上的点集。我们发现，一个大小恰好为 k 的点集的贡献即点集所有点的感染概率乘积 \times 邻接点的不被感染概率的积，并且选择点集里其中一个点将它的概率改为初始传染源。

显然树形 DP。 f_{i,j} 表示 i 的点集有 j 个点，不考虑初始传染源的贡献。g_{i,j} 表示 i 的点集有 j 个点，考虑初始传染源的贡献。

那么就有

f_{x,0} = g_{x,0} = (1 - p_x)\\ f_{x,i + j} = \sum\limits_{y\in son_x} f_{x,i} \times f_{y,j} \\ g_{x,i + j} = \sum\limits_{y \in son_x} g_{x,i} \times f_{y,j} + f_{x,i}\times g_{y,j}\\

注意一下 g 的转移，如果 j = 0 的时候就不能算上 f_{y,j} + f_{x,i}\times g_{y,j} 了。时间复杂度 \mathcal{O}(n^2)

const int N = 2e3 + 10;
int a[N],n,b[N],c[N],siz[N],f[N][N],g[N][N],t1[N],t2[N],fat[N];
ll p[N],sum,ans[N];
vector <int> G[N];

ll ffpow(ll a,ll b) {
    ll ans = 1;
    for (;b;b >>= 1) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
    }
    return ans;
}

void DP(int x,int fa) {
    siz[x] = 1;fat[x] = fa;
    f[x][1] = p[x];g[x][1] = a[x] * sum % mod;
    for (auto y : G[x]) {
        if (y != fa)  {
            DP(y,x);
            memset(t1,0,sizeof t1);memset(t2,0,sizeof t2);
            for (int i = 0;i <= siz[x];++i) {
                for (int j = 0;j <= siz[y];++j) {
                    if (!i && !j) continue;
                    t1[i + j] = (t1[i + j] + f[x][i] * f[y][j] % mod) % mod;
                    t2[i + j] = (t2[i + j] + g[x][i] * f[y][j] % mod) % mod;
                    if (j) {
                        t2[i + j] = (t2[i + j] + f[x][i] * g[y][j] % mod) % mod;
                    }
                }
            }
            for (int i = 0;i <= siz[x] + siz[y];++i) f[x][i] = t1[i];
            for (int i = 0;i <= siz[y] + siz[x];++i) g[x][i] = t2[i];
            siz[x] += siz[y];
        }
    }
    f[x][0] = g[x][0] = (1 - p[x] + mod);
}

signed main() {
    read(n);
    for (int i = 1;i < n;++i) {
        int x,y;read(x,y);
        G[x].emplace_back(y);G[y].emplace_back(x);
    }
    for (int i = 1;i <= n;++i) {
        read(a[i],b[i],c[i]);
        p[i] = b[i] * ffpow(c[i],mod-2) % mod;
        sum = (sum + a[i]) % mod;
    }
    sum = ffpow(sum,mod - 2);
    DP(1,1);
    for (int i = 1; i<= n;++i) {
        ans[i] = g[1][i];
        for (int j = 2;j <= n;++j) {
            ans[i] = (ans[i] + g[j][i] * (1 - p[fat[j]] + mod) % mod) % mod;
        }
    }
    for (int i = 1;i <= n;++i) printf("%lld\n",ans[i]);
    return 0;
}

C

给定一张 DAG，你需要构造一组点权令所有 1\to n 的路径权值相等。

n,m\leq 10^5

我们考虑从 1 出发到每个点的路径长 d_x，那么考虑对于一个点 x,所有 \forall (y,x)\in E 都需要满足 d_y 相等。

不难想到并查集。缩点之后注意到点权为正，那么不能出现环，所以生成的东西必然还是一个 DAG。这里注意特判一下，然后之后我们就可以在这张新图上求出每个点的 d_x 力。考虑对于 (x,y)\in E,令 w_y = d_{y} - d_x 即可。

const int N = 5e5 + 10;
int n,m,f[N],d[N],dp[N];
vector <int> G[N],buc[N];
vector <pii> edg;

int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);}

void solve() {
    read(n,m);
    for (int i = 1;i <= n;++i) f[i] = i,G[i].clear(),buc[i].clear(),d[i] = dp[i] = 0;
    edg.clear();
    for (int i = 1;i <= m;++i) {
        int x,y;read(x,y);edg.push_back(mp(x,y));
        G[y].push_back(x);
    }
    for (int x = 1;x <= n;++x) {
        for (auto y : G[x]) {
            f[find(y)] = find(G[x][0]);
        }
    }
    for (auto e : edg) {
        int x = e.first,y = e.second;
        buc[find(x)].emplace_back(find(y));
        d[find(y)]++;
    }
    int cnt = 0;
    queue <int> q;
    for (int i = 1;i <= n;++i) {
        //printf("%d %d\n",find(i),i);
        if (find(i) == i) {
            ++cnt;
            if (!d[i]) {
                q.push(i);dp[i] = 1;
            }
        }
    }
    while (!q.empty()) {
        int x = q.front();q.pop();
        --cnt;
        for (auto y : buc[x]) {
            dp[y] = max(dp[y],dp[x] + 1);
            if (!--d[y]) {
                q.push(y);
            }
        }
    }
    if (cnt) puts("No");
    else {
        puts("Yes");
        for (int i = 1;i <= n;++i) {
            int ans = dp[find(i)];
            if (i != 1) ans -= dp[find(G[i][0])];
            printf("%d ",ans);
        }
        puts("");
    }
}

B

Coach 说了个 Segment Tree beats 的做法，不会，有会的老哥教教（

upd:我会了！

我们考虑把对 b_i 的修改操作分段。那么只有每次进行 1 操作的时候加上的值才会改变。记录一个 t_i 代表这点上 a_i 经过的时间，那么修改的时候只需要把之前每个时间累积的 c_i 的和搞到旧的 a_i 上再更新 a_i 即可。

实现代码就是这样:

void change(int p,int x,int y,int c) {
    if (tree[p].l >= x && tree[p].r <= y) {
        tree[p].col = c;
        return ;
    }
    pushdown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (x <= mid) change(p << 1,x,y,c);
    if (y > mid) change(p << 1 | 1,x,y,c);
    pushup(p);
}

void query(int p,int x,int y) {
    if (tree[p].l >= x && tree[p].r <= y && tree[p].col) {
        b[tree[p].col] += tree[p].all;//下放操作
        clr(p);
        return ;
    }
    pushdown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (x <= mid) query(p << 1,x,y);
    if (y > mid) query(p << 1 | 1,x,y);
    pushup(p);
}

if (opt == 1) {
    int c;read(c);
    query(1,l,r);
    change(1,l,r,c);
} 

其他操作就很简单了。最后记得下推，可以根据 segtreebeats 的相关理论证明时间复杂度为 \mathcal{O}(n\log^2 n) 的。

const int N = 5e5 + 10;
int n,q,a[N];
ull b[N];

struct node {
    int l,r;
    int tagg;
    ull col,all,tagh,t,tag,sum;
}tree[N<<2];

void addval(int p,ull val) {
    tree[p].tag += val;
    tree[p].sum += (ull)(tree[p].r - tree[p].l + 1) * val;
    tree[p].tagh += val * tree[p].t;
}

void addtime(int p,ull tim) {
    tree[p].all += tim * tree[p].sum;
    tree[p].t += tim;
}

void pushup(int p) {
    tree[p].all = tree[p << 1].all + tree[p << 1 | 1].all;
    tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
    tree[p].col = (tree[p << 1].col == tree[p << 1 | 1].col) ? tree[p << 1].col : 0;
}

void clr(int p) {
    tree[p].tagg = 1;
    tree[p].tagh = tree[p].all = tree[p].t = 0;
}

void pushdown(int p) {
    if (tree[p].tagg) {
        clr(p << 1);clr(p << 1 | 1);
        tree[p].tagg = 0;
    }
    if (tree[p].tag) {
        addval(p << 1,tree[p].tag);
        addval(p << 1 | 1,tree[p].tag);
        tree[p].tag = 0;
    }
    if (tree[p].tagh) {
        tree[p << 1].all -= tree[p].tagh * (tree[p << 1].r - tree[p << 1].l + 1);
        tree[p << 1].tagh += tree[p].tagh;
        tree[p << 1 | 1].all -= tree[p].tagh * (tree[p << 1 | 1].r - tree[p << 1 | 1].l + 1);
        tree[p << 1 | 1].tagh += tree[p].tagh;
        tree[p].tagh = 0;
    }
    if (tree[p].t) {
        addtime(p << 1,tree[p].t);
        addtime(p << 1 | 1,tree[p].t);
        tree[p].t = 0;
    }
    if (tree[p].col) {
        tree[p << 1].col = tree[p].col;
        tree[p << 1 | 1].col = tree[p].col;
    }
}

void build(int p,int l,int r) {
    tree[p].l = l,tree[p].r = r;
    if (l == r) {
        tree[p].col = a[l];
        return ;
    }
    int mid = (tree[p].l + tree[p].r) >> 1;
    build(p << 1,l,mid);
    build(p << 1 | 1,mid + 1,r);
    pushup(p);
}

void change(int p,int x,int y,int c) {
    if (tree[p].l >= x && tree[p].r <= y) {
        tree[p].col = c;
        return ;
    }
    pushdown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (x <= mid) change(p << 1,x,y,c);
    if (y > mid) change(p << 1 | 1,x,y,c);
    pushup(p);
}

void modify(int p,int x,int y,ull c) {
    if (tree[p].l >= x && tree[p].r <= y) {
        addval(p,c);
        return ;
    }
    pushdown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (x <= mid) modify(p << 1,x,y,c);
    if (y > mid) modify(p << 1 | 1,x,y,c);
    pushup(p);
}

void query(int p,int x,int y) {
    if (tree[p].l >= x && tree[p].r <= y && tree[p].col) {
        b[tree[p].col] += tree[p].all;
        clr(p);
        return ;
    }
    pushdown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (x <= mid) query(p << 1,x,y);
    if (y > mid) query(p << 1 | 1,x,y);
    pushup(p);
}
signed main() {
    read(n,q);
    for (int i = 1;i <= n;++i) read(a[i]);
    build(1,1,n);
    for (int i = 1;i <= q;++i) {
        int opt,l,r;read(opt,l,r);
        if (opt == 1) {
            int c;read(c);
            query(1,l,r);
            change(1,l,r,c);
        } else {
            ull c;read(c);
            modify(1,l,r,c);
        }
        addtime(1,1);
    }
    query(1,1,n);
    for (int i = 1;i <= n;++i) printf("%llu ",b[i]);
    return 0;
}