B、xay loves monotonicity

题目大意

初始你有两个长度为 $n(1\le n\le 2·10^5)$ 的序列 $a_i,b_i$ 。

序列满足下面的要求： $1\le a_i\le 10^9,b_i\in\{0,1\}$ 。接下来你有三种操作：

把 $a_i$ 赋值成 $x$ 。
把 $[b_l,b_r]$ 这一段区间全部按位取反，即 $01$ 互换。
求在 $[l,r]$ 这个区间中必选 $a_l$ 构成的最长不下降子序列，假设为 $a_1,a_3,a_4$ ，那么我们取出 $b_1,b_3,b_4$ 构成一个 $01$ 串，这个串中有多少个 $01$ 交接处就是这个区间 $[l,r]$ 的答案，你需要回答这样的操作答案是多少？

操作最多有 $2·10^5$ 个。

Solution

考点：线段树区间合并

如果有写过用线段树维护最大连续子段和的读者可能会更好的理解这篇题解。

我们先看操作 $1、2$ 都是线段树的基础操作了，单点更新区间修改，打上 $lazy$ 标记即可，我们重点关注操作 $3$ 。

我们如何快速的找到区间的最长不下降子序列呢？

首先我们把区间映射到线段树的区间上去看，对于线段树节点维护的区间 $[l,r]$ 来说，我们另外定义一下变量 $maxi$ 代表区间最大值， $bit$ 代表这个区间的最长不下降子序列结尾的下标对应的 $b_i$ ， $len$ 代表这个区间的最长不下降子序列长度。

那么对应的我们就要在 $push\_up$ 中维护这 $3$ 个变量，在 $push\_down$ 中往下推 $lazy$ 标记。

我们设计一个函数 $query(rt,l,r,pre\_maxi,pre\_bit)$ 他会帮我们求出在区间 $[l,r]$ 中上一次最大值是 $pre\_maxi$ 并且结尾是 $pre\_bit$ 的答案贡献。

那么我们在线段树从下往上更新的时候，我们可以知道 $maxi[rt]$ 一定会先等于左子数的最大值，接下来拿着左子数的最大值去查询 $\\query(rt<<1|1,\frac{l+r}{2}+1,r,maxi[rt],bit[rt])$ ，就可以用右子树全部可能的点依次更新 $rt$ 的最值和结尾的 $b_i$ ，并且 $query()$ 的返回值就是区间里面它的不下降子序列长度。

但是在 $query()$ 的时候也会遇到区间，如果这个区间的左子树的最大值小于了之前结尾的最大值说明这个左子树对于不下降子序列来说没有一点贡献，直接去找右子树，否则就要先递归一下左子树求出左边的长度，然后更新了之前的最大值再去递归右子树。

但是我们会发现这样复杂度有点高了，我们要仔细的思考我们处理过那些区间信息，哪些信息是待处理的。由于我们的区间是从底向上合并，所以对于任意一棵树来说他的子树一定在之前就是处理完成的，那么我们 $query()$ 查询的本质是 $rt$ 的右子树有没有谁的最值大于 $rt$ 的左子树，那么对于他右子树这些区间，之前一定是经历过 $push\_up$ 了的，所以这些区间的 $len[rt]$ 都是已经算出来的答案了，所以对于区间 $rt$ 的子区间来说，它右子树带来的不下降子序列长度就没需要去重新 $query()$ 了，因为你之前已经维护出了 $len[rt]$ 和 $len[ls]$ ，那么根据我们在 $push\_up$ 里面写的 $len[rt]=len[ls]+query(rs)$ ，我们等价的知道 $query(rs) = len[rt] - len[ls]$ ，这也就在外面找完左边的长度之后重新 $query(rs)$ 的步骤给省去了。

然后求解答案的过程就去线段树区间上找到查询给的区间累加求合即可，时间复杂度 $O(n\log^2n)$ 。

const int N = 2e5 + 7;
int a[N], b[N];

struct SegTree {
#define mid (l+r>>1)
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r

    int maxi[N << 2], len[N << 2];
    int bit[N << 2], lazy[N << 2];

    void push_down(int rt) {
        if (lazy[rt] == 0)    return;
        bit[ls] ^= 1, lazy[ls] ^= 1;
        bit[rs] ^= 1, lazy[rs] ^= 1;
        lazy[rt] = 0;
    }

    int query(int rt, int l, int r, int& pre_max, int& pre_bit) {
        if (l == r) {
            if (maxi[rt] >= pre_max) { // 右子树更新之前父亲的值
                int res = pre_bit != bit[rt];
                if (pre_max == -1)    res = 0; // 说明是第一个点 0/1 都不计算
                pre_max = maxi[rt];
                pre_bit = bit[rt];
                return res;
            }
            return 0;
        }
        push_down(rt);
        if (maxi[ls] >= pre_max) {
            int res = query(lson, pre_max, pre_bit) + len[rt] - len[ls];
            //debug(res);
            pre_max = maxi[rt];
            pre_bit = bit[rt];
            return res;
        }
        else
            return query(rson, pre_max, pre_bit);
    }

    void push_up(int rt, int l, int r) {
        maxi[rt] = maxi[ls];
        bit[rt] = bit[ls];
        len[rt] = len[ls] + query(rson, maxi[rt], bit[rt]); // 用已经计算的ls，再去查询rs可选的更新rt
    }

    void build(int rt, int l, int r) {
        if (l == r) {
            maxi[rt] = a[l];
            bit[rt] = b[l];
            len[rt] = 1;
            lazy[rt] = 0;
            return;
        }
        build(lson);
        build(rson);
        push_up(rt, l, r);
    }

    void update(int rt, int l, int r, int pos, int v) {
        if (l == r) {
            maxi[rt] = v;
            return;
        }
        push_down(rt);
        if (pos <= mid)    update(lson, pos, v);
        else update(rson, pos, v);
        push_up(rt, l, r);
    }

    void update2(int rt, int l, int r, int L, int R) {
        if (L <= l && r <= R) {
            bit[rt] ^= 1;
            lazy[rt] ^= 1;
            return;
        }
        push_down(rt);
        if (R <= mid)    update2(lson, L, R);
        else if (L > mid)    update2(rson, L, R);
        else {
            update2(lson, L, mid);
            update2(rson, mid + 1, R);
        }
        push_up(rt, l, r);
    }

    int get_ans(int rt, int l, int r, int L, int R, int& pre_max, int& pre_bit) {
        if (L <= l && r <= R)    return query(rt, l, r, pre_max, pre_bit);
        push_down(rt);
        if (R <= mid)    return get_ans(lson, L, R, pre_max, pre_bit);
        if (L > mid)    return get_ans(rson, L, R, pre_max, pre_bit);
        return get_ans(lson, L, mid, pre_max, pre_bit) + get_ans(rson, mid + 1, R, pre_max, pre_bit);
    }

}A;



int solve() {
    int n = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
    }
    for (int i = 1; i <= n; ++i) {
        b[i] = read();
    }
    A.build(1, 1, n);
    int Q = read();
    while (Q--) {
        int op = read(), t1 = read(), t2 = read();
        if (op == 1) {
            A.update(1, 1, n, t1, t2);
        }
        else if (op == 2) {
            A.update2(1, 1, n, t1, t2);
        }
        else {
            int pre_max = -1, pre_bit = 0;
            print(A.get_ans(1, 1, n, t1, t2, pre_max, pre_bit));
        }
    }

    return 1;
}

F、xay loves trees

题目大意

给出 $2$ 棵以 $1$ 为根的树，你要在第一棵树上选择若干个点，并且在第二棵树上选择相同编号的点。

现在要求你在第一棵树上选择的点，把他们连接的边全部找出来必须构成一条链；

并且你在第二棵树上选择的点，不能存在任何两个点他们之间有祖先关系，换句话说就是某个点 $u$ 选了，它全部的子树节点都不能选了。

现在要你输出合理的点集最大的点数。

Solution

考点：时间戳+线段树

我们对第二棵树 $dfs$ ，打上时间戳，这样我就知道了每个节点 $u$ 他的全部子树在区间的什么范围内，时间戳它可以用 $[1,2n]$ 这里面若干个子区间，并且时间戳可以让同一个节点的不同子树在完全不相交的区间里面，并且 $u$ 会包含它全部的子树区间。

接着我再去第一棵树上进行 $dfs$ 。

我就假设 $u$ 就是那条链的底部，那么它头顶上最近的产生冲突的点就是我现在能选择的最大答案。

接下来就要去找如何找到它头顶上最近的产生冲突的点，那对应到深度就是最大深度的冲突点在哪里。

考虑线段树维护，我们每次查询区间 $[l_u,r_u]$ 这个区间内第一棵树里面深度最大的点是什么？

每次区间更新 $[l_u,r_u]$ 里面区间取 $\max$ 为 $dep_u$ ，即更新写法为 $maxi[rt] = \max(maxi[rt],dep[u])$ 。

如果是直接这样写的更新，那么这个点退出 $dfs$ 的时候就很难回到之前的状态了，所以我们就要用一个 $vector$ 保存一下之前的值，这样我们在退出的时候只需要把当前区间内最后的一个深度 $pop$ 掉就行。

又因为 $dfs$ 的特殊性，我们能保证 $vector$ 里面的深度值是递增的，如果这个区间 $vector.size()$ 不为空的话，我们就让 $maxi[rt] = vector.back()$ ，这样我就可以保证在 $u$ 退出 $dfs$ 的时候一定可以回到之前的最大值。接下来再用左右区间的最大值更新一下是选子区间还是当前的深度。

最后注意我们区间是 $[1,2n]$ ，线段树要开 $N<<3$ 。

时间复杂度为 $O(n\log n)$ 。

const int N = 3e5 + 7;

struct Node {
#define mid (l + r >> 1)
#define ls rt << 1
#define rs rt << 1 | 1
#define lson ls,l,mid
#define rson rs,mid+1,r

    int maxi[N << 3];
    vector<int> a[N << 3];
    void push_up(int rt, int l, int r) {
        maxi[rt] = 0;
        if (a[rt].size())    maxi[rt] = a[rt].back();
        if (l != r)
            maxi[rt] = max({ maxi[rt],maxi[ls],maxi[rs] });
    }
    void build(int rt, int l, int r) {
        if (l == r) {
            maxi[rt] = 0;
            a[rt].clear();
            return;
        }
        build(lson);
        build(rson);
    }
    void update(int rt, int l, int r, int L, int R, int v) {
        if (L <= l && r <= R) {
            if (v != -1)    a[rt].push_back(v);
            else a[rt].pop_back();
            push_up(rt, l, r);
            return;
        }
        if (R <= mid)    update(lson, L, R, v);
        else if (L > mid)    update(rson, L, R, v);
        else {
            update(lson, L, mid, v);
            update(rson, mid + 1, R, v);
        }
        push_up(rt, l, r);
    }
    int query(int rt, int l, int r, int L, int R) {
        if (L <= l && r <= R)    return maxi[rt];
        int res = 0;
        if (a[rt].size())    res = a[rt].back();
        if (R <= mid)    res = max(res, query(lson, L, R));
        else if (L > mid)    res = max(res, query(rson, L, R));
        else {
            res = max(res, query(lson, L, mid));
            res = max(res, query(rson, mid + 1, R));
        }
        return res;
    }
#undef mid
#undef ls
#undef rs
#undef lson
#undef rson
}A;

int n;
vector<int> G1[N], G2[N];

int tot, dfnl[N], dfnr[N];

void dfsTree2(int u, int fa) {
    dfnl[u] = ++tot;
    for (auto& v : G2[u]) {
        if (v == fa)    continue;
        dfsTree2(v, u);
    }
    dfnr[u] = ++tot;
}

int dep[N], res;

void dfsTree1(int u, int fa, int pre_dep) {
    dep[u] = dep[fa] + 1;

    pre_dep = max(pre_dep, A.query(1, 1, tot, dfnl[u], dfnr[u]));
    res = max(res, dep[u] - pre_dep);

    A.update(1, 1, tot, dfnl[u], dfnr[u], dep[u]);
    for (auto& v : G1[u]) {
        if (v == fa)    continue;
        dfsTree1(v, u, pre_dep);
    }
    A.update(1, 1, tot, dfnl[u], dfnr[u], -1);
}

int solve() {
    n = read();

    tot = 0;
    for (int i = 1; i <= n; ++i) {
        G1[i].clear();
        G2[i].clear();
    }

    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        G1[u].push_back(v);
        G1[v].push_back(u);
    }
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        G2[u].push_back(v);
        G2[v].push_back(u);
    }

    dfsTree2(1, 0);
    A.build(1, 1, tot);
    res = 1;
    dfsTree1(1, 0, 0);
    print(res);

    return 1;
}

H、xay loves count

题目大意

给出你长度为 $n(1\le n\le 10^6)$ 的序列 $a_i(1\le a_i\le 10^6)$ ，询问满足 $a_i\times a_j=a_k$ 这样的三元组 $(i,j,k)$ 有多少组。

Solution

开一个桶记录次数，然后枚举 $a_i$ 并且枚举倍数 $j$ 即可，时间复杂度是一个调和级数 $O(n\log n)$ 。

const int N = 1e6 + 1;
int cnt[N];

int solve() {
    int n = read();
    for (int i = 1; i <= n; ++i) {
        int x = read();
        ++cnt[x];
    }

    long long res = 0;
    for (int i = 1; i < N; ++i) {
        for (int j = 1; i * j < N; ++j) {
            res += 1ll * cnt[i] * cnt[j] * cnt[i * j];
        }
    }
    print(res);

    return 1;
}

I、xay loves or

题目大意

给出 $x,s$ 都在 $int$ 范围内，求有多少个 $y(y>0)$ 使得 $x\ \mathbf{or}\ y = s$ 。

Solution

按位拆分， $bit_x$ 代表 $x$ 二进制表示中的某一位。

如果 $bit_x=0,bit_s=0$ ，这一位只有 $0$ 一种选择。

如果 $bit_x=0,bit_s=1$ ，这一位只有 $1$ 一种选择。

如果 $bit_x=1,bit_s=0$ ，说明无解。

如果 $bit_x=1,bit_s=1$ ，这一位有 $0,1$ 两种选择。

最后输出组合的方案数即可，注意特判掉全是 $0$ 的那一个 $y$ 。

int solve() {
    while (cin >> n >> m) {
        ll ans = 1;
        bool flag = true;
        for (int i = 0; i < 63; ++i) {
            int opx = (n >> i) & 1, ops = (m >> i) & 1;
            if (opx == 1 && ops == 0) {
                flag = false; break;
            }
            else if (opx == 1 && ops == 1) {
                ans *= 2;
            }
        }
        if(n == m){
            --ans;
        }
        if (!flag) cout << 0 << endl;
        else cout << ans << endl;
    }

    return 1;
}

J、xay loves Floyd

题目大意

有人把 $floyd$ 写成下面这样，请问这张有向图还有多少个 $dis[u][v]$ 是正确的？

点数 $n(n\le 2000)$ ，边数 $m(m\le 5000)$ ，边权 $w(1\le w\le 10^4)$

for i from 1 to n
  for j from 1 to n
    for k from 1 to n
      dis[i][j] <- min(dis[i][j], dis[i][k] + dis[k][j])

Solution

考点： $floyd$ 实现过程

我们可以在 $O(nm\log m)$ 的时间内调用 $n$ 次 $dijkstra$ 算法求解到正确 $dis[u][v]$ 。

然后我们就要知道什么样的更新会让 $dis[u][v]$ 按照错误的做法也是正确的。

当存在一条边 $(u,v,w)$ ，有 $dis[u][v] = w$ 的时候。
当存在三点 $(i,j,k)$ ，有 $dis[i][k]$ 正确， $dis[k][j]$ 正确，并且 $k$ 这个点在 $i\to j$ 的最短路路径上。

我们用数组 $f1[i][j]$ 表示 $dis[i][j]$ 是正确的，我们用数组 $f2[i][j]$ 表示 $dis[j][i]$ 是正确的。

我们用 $g[i][j]$ 存下从 $i\to j$ 所有最短路上的点构成的集合。

只要我们枚举每个 $j$ ，再去枚举 $k$ ，让 $f1[i][k],f2[k][j]$ 都为真，并且 $k\in g[i][j]$ ，但是很显然这里看得出来复杂度是 $O(n^3)$ 的，我们需要考虑用 $bitset$ 加速。

那么具体实现的时候，我们求出正确的 $dis[u][v]$ 之后，先遍历每一条边，把情况 $1$ 判断掉并且更新 $f1,f2$ 数组。

接下来我们跟着他给的错误做法，外层枚举 $i$ ，然后把 $dis[i]$ 数组按照升序排序后，按照最近的节点开始往后面更新，如果 $dis[i][v] = dis[i][u] + w$ 那么说明 $g[i][u]$ 里面的全部的点要加入到 $g[i][v]$ 中，这里发现我们不需要二维的 $g[i][j]$ 每次用完清空即可，然后加入集合的操作也可以用 $bitset$ 运算。

至此最后枚举一下 $j$ ，如果 $f1[i]\&f2[j]\&g[j]$ 任何一位为 $1$ 说明存在一个点让 $dis[i][j]$ 是正确的，我们更新一下 $f1,f2$ 数组。

最终把 $f1$ 中全部的 $1$ 加起来，还有是无穷大的点一起求合就是答案了。

const int N = 2e3 + 7;
ll n, m;
vector<pai> G[N];
bitset<N> f1[N], f2[N], g[N];
int dis[N][N];

priority_queue<pai, vector<pai>, greater<pai>> pq;
bool vis[N];

void dijkstra(int s, int* d) {
    fill(d + 1, d + 1 + n, INF);
    fill(vis + 1, vis + 1 + n, 0);
    d[s] = 0;
    pq.push({ 0,s });
    while (pq.size()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u])    continue;
        vis[u] = 1;
        for (auto& [v, w] : G[u]) {
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pq.push({ d[v],v });
            }
        }
    }
}

int tmp[N], ID;
bool cmp(int x, int y) {
    return dis[ID][x] < dis[ID][y];
}

int solve() {
    n = read(), m = read();
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read(), w = read();
        G[u].push_back({ v,w });
    }
    for (int i = 1; i <= n; ++i) {
        dijkstra(i, dis[i]);
        f1[i].set(i);
        f2[i].set(i);
    }

    for (int u = 1; u <= n; ++u) {
        for (auto& [v, w] : G[u]) {
            if (dis[u][v] == w) {
                f1[u].set(v);
                f2[v].set(u);
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            tmp[j] = j;
            g[j].reset();
            g[j].set(j);
        }

        ID = i;
        sort(tmp + 1, tmp + 1 + n, cmp);
        for (int j = 1; j <= n; ++j) {
            int u = tmp[j];
            for (auto& [v, w] : G[u]) {
                if (dis[i][v] == dis[i][u] + w) {
                    g[v] |= g[u];
                }
            }
        }

        for (int j = 1; j <= n; ++j) {
            if ((f1[i] & f2[j] & g[j]).any()) {
                f1[i].set(j);
                f2[j].set(i);
            }
        }
    }

    int res = 0;
    for (int i = 1; i <= n; ++i)    res += f1[i].count();
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            res += dis[i][j] == INF;
        }
    }

    print(res);

    return 1;
}

2021牛客暑期多校训练营7

B、xay loves monotonicity

题目大意

Solution

F、xay loves trees

题目大意

Solution

H、xay loves count

题目大意

Solution

I、xay loves or

题目大意

Solution

J、xay loves Floyd

题目大意

Solution