UNR#3 Day1

A. 鸽子固定器

把固定器按 \(s\) 排序。

如果选的个数 \(< m\)，选出来的一定是一个连续段，否则再多选夹在中间的固定器一定优。

如果选的个数 \(= m\)，按牢固度从小到大考虑每一个固定器，找以当前固定器为最小牢固度的长度为 \(m\) 的最优序列，分讨几种情况之后不难发现忽略牢固度更小的固定器后，这还是个连续段。

想清楚了暴力做就好，时间复杂度 \(\mathcal O(nm)\)。

注意别用 vector，它的 erase 的时间复杂度是 \(\mathcal O(n)\)。

推荐手写链表。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

constexpr int N = 2e5 + 10;

int n, m, ds, dv, pre[N], lat[N];

struct Node {int s, v, id;} a[N], b[N], c[N];
bool cmps(const Node &lhs, const Node &rhs) {return lhs.s < rhs.s;}
bool cmpv(const Node &lhs, const Node &rhs) {return lhs.v < rhs.v;}

inline void chkmax(ll &x, ll y) {x = max(x, y);}
inline ll S(ll x) {return ds == 1 ? x : x * x;}
inline ll V(ll x) {return dv == 1 ? x : x * x;}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m >> ds >> dv;
    for (int i = 1; i <= n; i++) cin >> a[i].s >> a[i].v;
    sort(a + 1, a + n + 1, cmps);
    ll ans = 0;
    for (int len = 1; len < m; len++) {
        int sv = 0;
        for (int i = 1; i <= len; i++) sv += a[i].v;
        for (int i = len + 1; chkmax(ans, V(sv) - S(a[i - 1].s - a[i - len].s)), i <= n; sv += a[i].v - a[i - len].v, i++);
    }
    for (int i = 1; i <= n; i++) a[i].id = i, b[i] = a[i], pre[i] = i - 1, lat[i] = i + 1;
    sort(b + 1, b + n + 1, cmpv);
    for (int j = 1; j <= n - m + 1; j++) {
        int p = b[j].id, tot = 0;
        for (int i = 2, cur = pre[p]; i <= m && cur; i++, cur = pre[cur]) c[++tot] = a[cur];
        reverse(c + 1, c + tot + 1);
        for (int i = 1, cur = p; i <= m && cur <= n; i++, cur = lat[cur]) c[++tot] = a[cur];
        int sv = 0;
        for (int i = 1; i <= m; i++) sv += c[i].v;
        for (int i = m + 1; chkmax(ans, V(sv) - S(c[i - 1].s - c[i - m].s)), i <= tot; sv += c[i].v - c[i - m].v, i++);
        pre[lat[p]] = pre[p], lat[pre[p]] = lat[p];
    }
    cout << ans;
    return 0;
}

B. To Do Tree

考虑没有 \(m\) 的限制时怎么做，显然直接拓扑排序即可。

现在有了 \(m\) 的限制，贪心地选子树大的，然后全对了。

证明不会。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

constexpr int N = 1e5 + 10;

int n, m, fa[N], sz[N];

vector<int> G[N];

struct cmp {const bool operator()(const int &lhs, const int &rhs) {return sz[lhs] < sz[rhs];}};
priority_queue<int, vector<int>, cmp> q;

void dfs(int u) {
    sz[u] = 1;
    for (int v : G[u]) dfs(v), sz[u] += sz[v];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m;
    for (int i = 2; i <= n; i++) cin >> fa[i], G[fa[i]].emplace_back(i);
    dfs(1);

    vector<vector<int>> ans;
    vector<int> op;

    q.emplace(1);
    while (!q.empty()) {
        op.clear();
        for (int i = 1; i <= m && !q.empty(); i++) {op.emplace_back(q.top()); q.pop();}
        ans.emplace_back(op);
        for (int u : op) for (int v : G[u]) q.emplace(v);
    }

    cout << ans.size();
    for (auto i : ans) {
        cout << '\n' << i.size();
        for (int j : i) cout << ' ' << j;
    }
    return 0;
}

C. 配对树

考虑这样一种情况，\(x, y\) 都在以 \(u\) 为根的子树上，但他们没有配对，实际上的配对情况是 \((x, x'), (y, y')\)，此时把配对改为 \((x, y), (x', y')\) 一定不劣。

所以一定存在一个最优匹配，使得所有路径不交。

考虑每条边对答案的贡献。

边 \((fa_u, u)\) 会被记入答案当且仅当以 \(u\) 为根的子树内 ddl 数量为奇数。

我们把 \(u\) 子树内的 ddl 视作 \(1\)，其余的视作 \(0\)，对于一个固定的 \(u\)，我们需要知道这个 \(01\) 序列里 \(1\) 的个数是奇数的子区间数。

对 \(01\) 序列做前缀和得到 \(s\)，所求即 \(s_r - s_{l - 1} \equiv 1 \pmod2, l - 1 \equiv r \pmod2\) 的 \((l, r)\) 的个数，分下标和值的奇偶四种情况讨论就好。

时间复杂度 \(\mathcal O(n^2 + nm)\)。

用线段树合并维护 \(s\)，时间复杂度 \(\mathcal O(n + m \log m)\)。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

constexpr int N = 1e5 + 10, TN = N * 40, MOD = 998244353;

int n, m, rt[N], ans;

int tot, head[N];
struct Edge {int to, nxt, val;} e[N << 1];
inline void add(int u, int v, int w) {e[++tot] = Edge{v, head[u], w}, head[u] = tot;}

namespace SGT {
    #define lson t[pos].ls
    #define rson t[pos].rs

    int tot;
    struct Seg {int c[2][2], ls, rs; bool s;} t[TN];

    inline void pu(int pos, int l, int r) {
        int mid = (l + r) >> 1;
        for (int i : {0, 1}) for (int j : {0, 1}) {
            t[pos].c[i][j] = 0;
            if (lson) t[pos].c[i][j] += t[lson].c[i][j];
            else if (!j) t[pos].c[i][j] += ((mid + 2 + i) >> 1) - ((l + 1 + i) >> 1); 
            if (rson) t[pos].c[i][j] += t[rson].c[i][j ^ t[lson].s];
            else if (j == t[lson].s) t[pos].c[i][j] += ((r + i) >> 1) - ((mid + i) >> 1);
        }
        t[pos].s = t[lson].s ^ t[rson].s;
    }

    void upd(int &pos, int l, int r, int x) {
        if (!pos) pos = ++tot;
        if (l == r) {t[pos].s = 1, t[pos].c[l & 1][1] = 1; return;}
        int mid = (l + r) >> 1;
        x <= mid ? upd(lson, l, mid, x) : upd(rson, mid + 1, r, x);
        pu(pos, l, r);
    }

    int merge(int x, int y, int l, int r) {
        if (!x || !y) return x ^ y;
        int mid = (l + r) >> 1;
        t[x].ls = merge(t[x].ls, t[y].ls, l, mid), t[x].rs = merge(t[x].rs, t[y].rs, mid + 1, r);
        pu(x, l, r); return x;
    }

    inline ll query(int pos) {return (1ll * t[pos].c[0][1] * t[pos].c[0][0] + 1ll * t[pos].c[1][0] * t[pos].c[1][1]) % MOD;}
}

void dfs(int u, int fa) {
    for (int i = head[u], v; v = e[i].to, i; i = e[i].nxt) if (v != fa) {
        dfs(v, u);
        ans = (ans + SGT::query(rt[v]) * e[i].val) % MOD;
        rt[u] = SGT::merge(rt[u], rt[v], 0, m);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m;
    for (int i = 1, u, v, w; i < n; i++) cin >> u >> v >> w, add(u, v, w), add(v, u, w);
    for (int i = 1, x; i <= m; i++) cin >> x, SGT::upd(rt[x], 0, m, i);
    dfs(1, -1);
    cout << ans;
    return 0;
}