牛客多校第七场题解

B - xay loves monotonicity

题意：
给你两个序列，其中第二个为序列。每次单点修改第一个序列；区间修改第二个序列，让区间所有数字；进行区间询问。

询问的规则是，从左端点开始，往右找第一个大于等于它的值的位置，然后接着找，直到不能找为止。然后把这些位置的数组对应的值取出来，如果相邻的值不相同，那么就会有一个贡献。输出贡献和。

思路：
洛谷上有原题，先丢个链接P4198

当时写完原题，我就觉得原题会写，这道题就一定会写，只是多了些东西恶心你。

然后我就被卡了

本人习惯做线段树pushUp，合并两个区间维护时回传结构体，然后就写得很麻烦。这里传个指针就很简单了。

先写原题，再写这题就很容易理解了。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 7;

int n, m, id[N];
int a[N], b[N];

struct Q {
    int opt, ql, qr;
}q[N];

#define ls (id << 1)
#define rs (id << 1 | 1)
#define mid (l + r >> 1)
struct Seg {
    int mx[N << 2], t[N << 2], bt[N << 2], lazy[N << 2];

    void down(int id) {
        if (!lazy[id]) return;
        lazy[ls] ^= 1, bt[ls] ^= 1;
        lazy[rs] ^= 1, bt[rs] ^= 1;
        lazy[id] ^= 1;
    }

    int query(int id, int l, int r, int& MAX, int& bit) {
        if (mx[id] < MAX) return 0;
        if (l == r) {
            int res = bt[id] ^ bit;
            if (MAX == -1) res = 0; // 说明我以当前节点为开头，所以肯定不能算贡献
            MAX = mx[id];
            bit = bt[id];
            return res;
        }
        down(id);
        if (mx[ls] >= MAX) {
            int res = query(ls, l, mid, MAX, bit);
            // 注意修改MAX和bit，因为当前这个区间整体是有贡献的，所以要用这个区间的值进行修改
            MAX = mx[id];
            bit = bt[id];
            return t[id] - t[ls] + res;
        } else {
            return query(rs, mid + 1, r, MAX, bit);
        }
    }

    void up(int id, int l, int r) {
        mx[id] = mx[ls], bt[id] = bt[ls]; // 先把左儿子的值传上来，再用左儿子的信息去找有儿子，维护区间整体信息
        t[id] = t[ls] + query(rs, mid + 1, r, mx[id], bt[id]);
    }

    void build(int id, int l, int r) {
        mx[id] = t[id] = bt[id] = 0;
        if (l == r) {
            mx[id] = a[l];
            bt[id] = b[l];
            return;
        }
        build(ls, l, mid);
        build(rs, mid + 1, r);
        up(id, l, r);
    }

    void modify(int id, int l, int r, int p, int v) {
        if (l == r) {
            mx[id] = v;
            return;
        }
        down(id);
        if (p <= mid) modify(ls, l, mid, p, v);
        else modify(rs, mid + 1, r, p, v);
        up(id, l, r);
    }

    void flip(int id, int l, int r, int ql, int qr) {
        if (l >= ql && r <= qr) {
            bt[id] ^= 1;
            lazy[id] ^= 1;
            return;
        }
        down(id);
        if (ql <= mid) flip(ls, l, mid, ql, qr);
        if (qr > mid) flip(rs, mid + 1, r, ql, qr);
        up(id, l, r);
    }

    int getAns(int id, int l, int r, int ql, int qr, int &MAX, int &bit) {
        if (mx[id] < MAX) return 0;
        if (l >= ql && r <= qr) {
            return query(id, l, r, MAX, bit);
        }
        down(id);
        int res = 0;
        // 优先询问左儿子，符合询问要求，所以可以直接写
        if (ql <= mid) res += getAns(ls, l, mid, ql, qr, MAX, bit);
        if (qr > mid) res += getAns(rs, mid + 1, r, ql, qr, MAX, bit);
        return res;
    }
}seg;

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
    }
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> q[i].opt >> q[i].ql >> q[i].qr;
    }
    seg.build(1, 1, n);
    for (int i = 1; i <= m; ++i) {
        if (q[i].opt == 1) seg.modify(1, 1, n, q[i].ql, q[i].qr);
        else if (q[i].opt == 2) seg.flip(1, 1, n, q[i].ql, q[i].qr);
        else {
            int mx = -1, bt = 0;
            cout << seg.getAns(1, 1, n, q[i].ql, q[i].qr, mx, bt) << '\n';
        }
    }
}

int main() {
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cout << fixed << setprecision(20);
#endif
    int t = 1;
    while (t--) solve();
    return 0;
}

F - xay loves trees

题意：
给你两棵树，在第一棵树上找一条最长链，要求链上所有点的在第二棵树上互相之间没有祖先关系。

思路：
点是点的祖先，当且仅当在以为根节点的子树中。由此可见，当我们选了一个节点后，它的子树中的所有节点都不能选了。

因为要保持是第一棵树上的一条链，所以我们选择在第一棵树上进行dfs，过程中把当前节点在第二棵树中形成的子树中的所有节点的权值加，当前长链是合法的当且仅当所有节点权值的最大值为。

由于要在第一棵树上连续，所以可以使用滑动窗口，当添加一个点会让当前状态非法时，就一直把前面的点删掉，以当前状态进行，回来之后再加回来，继续下一个递归。但是这样的做***被卡到，但是现在还没有加能卡掉这个做法的数据。

注意到我们只求最长的长度，且当前窗口长度是之前求出来的最长的合法长度，所以我们可以让这个窗口长度只增不降，即每次最多删除一个节点，这样就可以在的时间复杂度下找到最长的答案。

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

inline int rd() {
    int f = 0; int x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 3e5 + 7;
vector<int> v1[N], v2[N];
int n, stt[N], fnt[N], dfsId;
int ans, sz;
int que[N], head, rear;

#define ls (id << 1)
#define rs (id << 1 | 1)
#define mid (l + r >> 1)

struct Seg {
    int t[N << 2], lazy[N << 2];
    void up(int id) {
        t[id] = max(t[ls], t[rs]);
    }
    void down(int id) {
        if (!lazy[id]) return;
        int tmp = lazy[id];
        lazy[ls] += tmp;
        lazy[rs] += tmp;
        t[ls] += tmp;
        t[rs] += tmp;
        lazy[id] = 0;
    }
    void build(int id, int l, int r) {
        t[id] = 0, lazy[id] = 0;
        if (l == r) return;
        build(ls, l, mid);
        build(rs, mid + 1, r);
    }
    void modify(int id, int l, int r, int ql, int qr, int v) {
        if (l >= ql && r <= qr) {
            t[id] += v;
            lazy[id] += v;
            return;
        }
        down(id);
        if (ql <= mid) modify(ls, l, mid, ql, qr, v);
        if (qr > mid) modify(rs, mid + 1, r, ql, qr, v);
        up(id);
    }
    int query(int id, int l, int r, int ql, int qr) {
        // dbg(id, l, r);
        if (l >= ql && r <= qr) return t[id];
        down(id);
        int res = -inf;
        if (ql <= mid) res = max(res, query(ls, l, mid, ql, qr));
        if (qr > mid) res = max(res, query(rs, mid + 1, r, ql, qr));
        return res;
    }
}seg;

void dfsOd(int u, int fa) {
    stt[u] = ++dfsId;
    for (auto v : v2[u]) if (v != fa) dfsOd(v, u);
    fnt[u] = dfsId;
}

void dfs(int u, int fa) {
    seg.modify(1, 1, n, stt[u], fnt[u], 1);
    que[rear++] = u;
    int tmp = seg.query(1, 1, n, 1, n);
    if (tmp >= 2) {
        seg.modify(1, 1, n, stt[que[head]], fnt[que[head]], -1);
        head++;
    }
    ans = max(ans, rear - head);
    for (auto v : v1[u]) if (v != fa) dfs(v, u);
    seg.modify(1, 1, n, stt[u], fnt[u], -1);
    rear--;
    if (tmp >= 2) {
        head--;
        seg.modify(1, 1, n, stt[que[head]], fnt[que[head]], 1);
    }
}


void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        v1[i].clear();
        v2[i].clear();
    }
    for (int i = 2, u, v; i <= n; ++i) {
        cin >> u >> v;
        v1[u].push_back(v);
        v1[v].push_back(u);
    }
    for (int i = 2, u, v; i <= n; ++i) {
        cin >> u >> v;
        v2[u].push_back(v);
        v2[v].push_back(u);
    }
    dfsId = 0;
    dfsOd(1, 0);
    ans = 0;
    head = rear = 0;
    seg.build(1, 1, dfsId);
    dfs(1, 0);
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

H - xay loves count

题意：
给定序列，求三元组个数，满足。

思路：
记录每个数字出现的数量，枚举其中两个数，就可以算出第三个数，把它们的数量乘起来就是对答案的贡献。枚举时注意跳过不合法的数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define dbg(x...) do{ cerr << #x << " -> "; err(x);} while (0)
void err() { cerr << endl;}
template<class T, class... Ts> void err(const T& arg, const Ts&... args) { cerr << arg << " "; err(args...);}
const int N = 1e6 + 7;

int n;
int a[N];
ll num[N];
ll f[N];

void run() {
    scanf("%d", &n);
    for (int i =1 ;  i <= n; ++i) {
        scanf("%d", &a[i]);
        num[a[i]]++;
    }
    ll ans = 0;
    for (int i = 1; i < N; ++i) {
        for (int j = i; j < N; j += i) {
            ans += num[j] * num[j / i] * num[i];
        }
    }
    printf("%lld\n", ans);
}

int main() {
    int t = 1;
    while (t--) run();
    return 0;
}

I - xay loves or

思路：
签到。注意特判不能计入答案。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define endl "\n"
#define dbg(x...) do{ cerr << #x << " -> "; err(x);} while (0)
void err() { cerr << endl;}
template<class T, class... Ts> void err(const T& arg, const Ts&... args) { cerr << arg << " "; err(args...);}
const int maxn = 1e5 + 7;

void run() {
    int x, s;
    cin >> x >> s;
    if (((x ^ s) | s) > s) {
        cout << 0 << endl;
        return;
    }
    int y = x ^ s;
    y ^= s;
    cout << (1 << __builtin_popcount(y)) - ((x ^ s) == 0) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    while (t--) run();
    return 0;
}

J - xay loves Floyd

题意：
编程时把Floyd算法写错了，枚举中间点的for放在了第三维，问这样做了之后求出来的两点距离，还有多少个是正确的。定义。

思路：
放在第三维之后，相当于两点之间的最短路最多只能由一个点更新。考虑何种情况下这样子求得的最短路仍然是正确的。

1.两点直接相连的边就是最短路

2.两点，通过一个点相连的最短路是正确的最短路，且->，->的结果正确，且在->的最短路径上。

两点之间正确的最短路可以对每个点跑一遍，然后比较跑出来的图和原图相等的地方，这些就是属于第一种情况的，把他们标记一下，计入答案。

对于第二种情况，我们先枚举两边的点，，再枚举中间点，按照上述方法直接搞。这样的时间和空间复杂度都不太行，考虑优化。

首先解决路径上的点的问题。我们枚举，之后，要取出->最短路径上的点，每次重新取不合理，预处理又存不下。尝试能否固定其中一维，得到递推式。

因为跑过一遍，我们能清楚地知道当前到所有点的最短距离。那么我们可以来模拟一下的最后一步的转移过程。即枚举点的时候，按照点到点的距离，从小到大枚举，然后遍历从出发的边，设边权为，入点为，判断点到点的距离是否要用点到点的这条边更新，然后就可以把点到点的最短路径经过的点转移到点到点上面。再看一眼，最多开个大小的东西，这种转移又很像二进制的或操作，那么我们就可以开个长度为的维，表示点到点之间要经过哪些点，这个转移就比较容易了。

既然都用到了，看看能否用优化检查->，->的正确性。继续开两个二维，一个表示点到哪些点的最短路是能通过次转移获得正确答案的，一个表示哪些点到点的最短路是能通过次转移获得正确答案的。那么我们对这两个交一下，就能得到所有可行的中间点。

接下来我们要做的，就是检查这些可行的中间点，有没有在点到点的最短路径上的。我们只需要让之前得到的记录路径上的点的再和它交一下就行了。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e3 + 7;
int dis[N][N], disF[N][N];
int n, m;
vector< pair<int, int> > G[N];
bitset<N> toR[N], toL[N], pot[N];

void dij(int s){
    for (int i = 1; i <= n; ++i) dis[s][i] = inf;
    dis[s][s] = 0;
    priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > q;
    q.push({0, s});
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        for (auto t : G[u]) {
            int v = t.second, w = t.first;
            if (dis[s][v] > dis[s][u] + w) {
                dis[s][v] = dis[s][u] + w;
                q.push({dis[s][v], v});
            }
        }
    }
}

void solve() {
    memset(disF, 0x3f,sizeof(disF));
    scanf("%d %d", &n, &m);
    for (int i = 1, u, v, w; i <= m; ++i) {
        scanf("%d %d %d", &u, &v, &w);
        G[u].push_back({w, v});
        disF[u][v] = w;
    }
    for (int i = 1; i <= n; ++i) dij(i);
    for (int i = 1; i <= n; ++i) disF[i][i] = 0;
    for (int u = 1; u <= n; ++u) {
        for (int v = 1; v <= n; ++v) {
            if (dis[u][v] == disF[u][v]) {
                toR[v][u] = 1; // v作为终点或者中间点，哪些点能到v
                toL[u][v] = 1; // u作为起始点，能到哪些点
            }
        }
    }
    vector<int> que(n);
    iota(que.begin(), que.end(), 1);
    for (int u = 1; u <= n; ++u) {
        sort(que.begin(), que.end(), [&](int x, int y){
           return dis[u][x] < dis[u][y]; 
        });
        int pre = u;
        for (int i = 1; i <= n; ++i) pot[i].reset(), pot[i][i] = 1;
        for (auto v : que) {
            for (auto t : G[v]) {
                if (dis[u][v] + t.first == dis[u][t.second]) pot[t.second] |= pot[v]; // 使用当前边，最短路径经过点可以转移
            }
        }
        for (int v = 1; v <= n; ++v) {
            auto tmp = toR[v] & toL[u] & pot[v];
            if (tmp.count()) {
                toL[u][v] = 1, toR[v][u] = 1;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += toR[i].count();
    }
    printf("%d\n", ans);
}

int main() {
    int t = 1;
    while (t--) solve();
    return 0;
}

K - xay loves sequence

题意：
定义为让区间所有值都变成的最小操作次数，每次操作可以选择其中的一段区间，让区间内的每个 或者 。

思路：
先不考虑模，每次要修改一个区间，取差分数组，令，该差分数组满足，即在范围内，我选择任意一个正数（负数），一定会存在另一个负数（正数）。在没有模时，要使得区间都为，每次让区间同时加（减），相当于选两个位置，一个加上（减少），另一个减少（加上），所以答案是$$

在模意义下，，对一段区间增加或者减少是不需要算贡献的，即我可以在差分数组范围内选择两个位置，一个位置加上，另一个位置减少。考虑这样子的操作如何会让答案更优。

• 对于加来说，肯定要选择的地方，否则肯定不优。增加后变成了，
• 对于减来说，肯定要选择的地方，否则肯定不优。减少后变成了，

这两个东西肯定是同时选的，如果只选择一个的话，一个让答案增加了，另一个让答案增加了，无论怎么取值都到不了，肯定是不划算的。

现在的问题就转换成了求两者的之和最小是多少。我们可以对它们分别进行排序，求一个前缀和即可。这样子做的时间复杂度显然不能接受。观察到两者的之和是一个单峰函数，我们可以在级别下求出下凸峰值，但这样还是不够。

考虑二分后优化查询，我们要对一个区间求前大的和，这个东西就可以用主席树来求解了。两颗主席树用来维护正负差分值的绝对值，查询一个区间时，要注意头尾的差分值的绝对值并没有加进来，要额外传递一下和。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 7;
const int MAX = (1 << 30) - 1;

int n, q, ql, qr, k;
ll a[N], pre[N];

struct Seg {
    struct Node {
        int ls, rs, cnt;
        ll sum;
    }t[N * 50];

    int rt[N], tot;

    void modify(int &rt, int l, int r, int pos, int v) {
        int now = ++tot;
        t[now] = t[rt];
        t[now].sum += v;
        t[now].cnt += 1;
        if (l == r) {
            rt = now;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) modify(t[now].ls, l, mid, pos, v);
        else modify(t[now].rs, mid + 1, r, pos, v);
        rt = now;
    }

    ll query(int lr, int rr, int l, int r, int k, ll ed) {
        if (!k) return 0;
        if (l == r) { // 查询到单点，还剩下k个数字没放进来
            return (ll)l * k;
        }
        int mid = (l + r) >> 1;
        int nums = t[ t[rr].rs ].cnt - t[ t[lr].rs ].cnt + (ed > mid && ed <= r); // 计入传递进来的差分值的绝对值的影响
        // 这里有个trick，判断 nums <= k 而不是 nums < k，这样右边就不用再分区间了，能减少很多递归。这题大概能减个1s左右
        if (nums <= k) return query(t[lr].ls, t[rr].ls, l, mid, k - nums, ed) + t[ t[rr].rs ].sum - t[ t[lr].rs ].sum + (ed > mid && ed <= r)  * ed;
        else return query(t[lr].rs, t[rr].rs, mid + 1, r, k, ed);
    }

    int getsz(int l, int r) {
        return t[ rt[r] ].cnt - t[ rt[l] ].cnt + 1; // 注意还没传递进来的差分值的绝对值也要占一个位置
    }
}seg[2];

ll calc(int l, int r, int kk) {
    ll res = (pre[r] - pre[l] + a[l] + a[r]) / 2;
    return res + (ll)kk * k - seg[0].query(seg[0].rt[l], seg[0].rt[r], 0, MAX, kk, a[r]) - seg[1].query(seg[1].rt[l], seg[1].rt[r], 0, MAX, kk, a[l]);
}

void solve() {
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 2; i <= n; ++i) {
        ll v = abs(a[i] - a[i - 1]);
        pre[i] = pre[i - 1] + v;
        seg[1].rt[i] = seg[1].rt[i - 1];
        seg[0].rt[i] = seg[0].rt[i - 1];
        if (a[i] >= a[i - 1]) {
            seg[1].modify(seg[1].rt[i], 0, MAX, v, v);
        } else {
            seg[0].modify(seg[0].rt[i], 0, MAX, v, v);
        }
    }
    while (q--) {
        cin >> ql >> qr >> k;
        int l = 0, r = min(seg[0].getsz(ql, qr), seg[1].getsz(ql, qr)), mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (!mid || calc(ql, qr, mid) < calc(ql, qr, mid - 1)) l = mid + 1;
            else r = mid - 1;
        }
        cout << calc(ql, qr, l - 1) << '\n';
    }
}

int main() {
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cout << fixed << setprecision(20);
#endif
    int t = 1;
    while (t--) solve();
    return 0;
}