B、xay loves monotonicity

题目大意

初始你有两个长度为的序列。

序列满足下面的要求：。接下来你有三种操作：

1. 把赋值成。
2. 把这一段区间全部按位取反，即互换。
3. 求在这个区间中必选构成的最长不下降子序列，假设为，那么我们取出构成一个串，这个串中有多少个交接处就是这个区间的答案，你需要回答这样的操作答案是多少？

操作最多有个。

Solution

考点：线段树区间合并

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

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

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

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

那么对应的我们就要在中维护这个变量，在中往下推标记。

我们设计一个函数他会帮我们求出在区间中上一次最大值是并且结尾是的答案贡献。

那么我们在线段树从下往上更新的时候，我们可以知道一定会先等于左子数的最大值，接下来拿着左子数的最大值去查询，就可以用右子树全部可能的点依次更新的最值和结尾的，并且的返回值就是区间里面它的不下降子序列长度。

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

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

然后求解答案的过程就去线段树区间上找到查询给的区间累加求合即可，时间复杂度。

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

题目大意

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

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

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

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

Solution

考点：时间戳+线段树

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

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

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

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

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

每次区间更新里面区间取为，即更新写法为。

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

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

最后注意我们区间是，线段树要开。

时间复杂度为。

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

题目大意

给出你长度为的序列，询问满足这样的三元组有多少组。

Solution

开一个桶记录次数，然后枚举并且枚举倍数即可，时间复杂度是一个调和级数。

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

题目大意

给出都在范围内，求有多少个使得。

Solution

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

如果，这一位只有一种选择。

如果，这一位只有一种选择。

如果，说明无解。

如果，这一位有两种选择。

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

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

题目大意

有人把写成下面这样，请问这张有向图还有多少个是正确的？

点数，边数，边权

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

考点：实现过程

我们可以在的时间内调用次算法求解到正确。

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

1. 当存在一条边，有的时候。
2. 当存在三点，有正确，正确，并且这个点在的最短路路径上。

我们用数组表示是正确的，我们用数组表示是正确的。

我们用存下从所有最短路上的点构成的集合。

只要我们枚举每个，再去枚举，让都为真，并且，但是很显然这里看得出来复杂度是的，我们需要考虑用加速。

那么具体实现的时候，我们求出正确的之后，先遍历每一条边，把情况判断掉并且更新数组。

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

至此最后枚举一下，如果任何一位为说明存在一个点让是正确的，我们更新一下数组。

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

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;
}