C. 星际航行

题目描述

给定一个 \(N\) 个点 \(M\) 条边的无向带权图。我们定义一条路径的长度为路径上边权最大值。有 \(Q\) 次查询，第 \(i\) 次查询从 \(u\) 到其他 \(N-1\) 个点的最短路径中路径长度第 \(k\) 大的长度。

思路

首先，此题显然只会在最小生成树上选择路径。所以我们可以先求出最小生成树。

又因为两个点之间的最长路径为其在 kruskal 重构树上的 LCA。所以我们可以建出重构树，那么从一个结点 \(u\) 出发的可能路径长度就是 \(u\) 的祖先的点权，小于或等于某个长度的路径数量就为对应结点的子树内叶子数量减一（因为要去掉自己到达自己）。使用倍增求解即可。

空间复杂度 \(O(N\log N+M)\)，时间复杂度 \(O(M\log M+(N+Q)\log N)\)。

代码

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

const int MAXM = 200001, MAXN = 100001;

struct Edge {
  int u, v, w;
}g[MAXM];

int n, m, q, _f[MAXN], a[MAXN], tot, f[19][MAXN], leaf[MAXN];
vector<int> e[MAXN];

int getfa(int u) {
  return (_f[u] == u ? u : _f[u] = getfa(_f[u]));
}

void dfs(int u) {
  leaf[u] = (e[u].empty());
  for(int i = 1; i <= 18; ++i) {
    f[i][u] = f[i - 1][f[i - 1][u]];
  }
  for(int v : e[u]) {
    f[0][v] = u;
    dfs(v);
    leaf[u] += leaf[v];
  }
}

int Get(int u, int k) {
  for(int i = 18; i >= 0; --i) {
    if(f[i][u] && leaf[f[i][u]] - 1 < k) {
      u = f[i][u];
    }
  }
  return a[f[0][u]];
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m >> q;
  tot = n;
  for(int i = 1; i <= m; ++i) {
    cin >> g[i].u >> g[i].v >> g[i].w;
  }
  sort(g + 1, g + m + 1, [](const Edge &a, const Edge &b) -> bool {
    return a.w < b.w;
  });
  iota(_f + 1, _f + 2 * n + 1, 1);
  for(int i = 1; i <= m; ++i) {
    int u = getfa(g[i].u), v = getfa(g[i].v), w = g[i].w;
    if(u != v) {
      a[++tot] = w;
      e[tot].emplace_back(u);
      e[tot].emplace_back(v);
      _f[u] = _f[v] = tot;
    }
  }
  dfs(tot);
  for(int i = 1, u, k; i <= q; ++i) {
    cin >> u >> k;
    cout << Get(u, n - k) << "\n";
  }
  return 0;
}

D. 异或函数

题目描述

我们令 \(f(x)=0\oplus1\oplus \dots\oplus x\)。给定一个序列 \(A_1,A_2,\dots,A_N\)，有 \(M\) 次操作：

• 对于 \(\forall l\le i\le r, A_i\leftarrow A_i+x\)。
• 求 \(\sum \limits_{i=l}^r f(A_i)\)。

思路

通过打表或推式子可以发现，\(f(x)=\begin{cases}2\mid x&x\\2\not \mid x&0\end{cases}+\begin{cases}2\mid \lfloor\frac{x-1}{2}\rfloor&1\\2\not \mid \lfloor\frac{x-1}{2}\rfloor&0\end{cases}\)。

使用线段树维护 \(\sum \begin{cases}2\mid x&x\\2\not \mid x&0\end{cases},\sum \begin{cases}2\mid x&0\\2\not \mid x&x\end{cases},\sum \begin{cases}2\mid x&1\\2\not \mid x&0\end{cases},\sum \begin{cases}2\mid x&0\\2\not \mid x&1\end{cases},\sum \begin{cases}2\mid \lfloor\frac{x-1}{2}\rfloor&1\\2\not \mid \lfloor\frac{x-1}{2}\rfloor&0\end{cases},\begin{cases}2\mid \lfloor\frac{x-1}{2}\rfloor&0\\2\not \mid \lfloor\frac{x-1}{2}\rfloor&1\end{cases}\) 即可。

空间复杂度 \(O(N)\)，时间复杂度 \(O(Q\log N)\)。

代码

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

const int MAXN = 100001;

int florr2(int x) {
  return (x < 0 ? (x - 1) / 2 : x / 2);
}

int f(int x) {
  return ((x & 1) ^ 1) * x + (((florr2(x - 1) + 2) & 1) ^ 1);
}

struct Segment_Tree {
  int l[MAXN << 2], r[MAXN << 2], cnt[MAXN << 2][2][2], cnt2[MAXN << 2][2], a[MAXN], nxt[2][2];
  ll sum[MAXN << 2], res[MAXN << 2][2], lazy[MAXN << 2];
  void pushup(int u) {
    res[u][0] = res[u << 1][0] + res[(u << 1) | 1][0], res[u][1] = res[u << 1][1] + res[(u << 1) | 1][1];
    cnt2[u][0] = cnt2[u << 1][0] + cnt2[(u << 1) | 1][0], cnt2[u][1] = cnt2[u << 1][1] + cnt2[(u << 1) | 1][1];
    cnt[u][0][0] = cnt[u << 1][0][0] + cnt[(u << 1) | 1][0][0], cnt[u][0][1] = cnt[u << 1][0][1] + cnt[(u << 1) | 1][0][1];
    cnt[u][1][0] = cnt[u << 1][1][0] + cnt[(u << 1) | 1][1][0], cnt[u][1][1] = cnt[u << 1][1][1] + cnt[(u << 1) | 1][1][1];
    sum[u] = sum[u << 1] + sum[(u << 1) | 1];
  }
  void build(int u, int s, int t) {
    l[u] = s, r[u] = t;
    if(s == t) {
      res[u][a[s] & 1] = a[s], cnt[u][(florr2(a[s] - 1) + 2) & 1][(a[s] + 1) & 1] = 1, sum[u] = f(a[s]), cnt2[u][a[s] & 1] = 1;
      return;
    }
    int mid = (s + t) >> 1;
    build(u << 1, s, mid), build((u << 1) | 1, mid + 1, t);
    pushup(u);
  }
  void tag(int u, ll x) {
    if(!x) {
      return;
    }
    if(x % 2) {
      swap(res[u][0], res[u][1]);
      swap(cnt2[u][0], cnt2[u][1]);
    }
    res[u][0] += 1ll * cnt2[u][0] * x;
    res[u][1] += 1ll * cnt2[u][1] * x;
    nxt[0][0] = nxt[0][1] = nxt[1][0] = nxt[1][1] = 0;
    for(bool o : {0, 1}) {
      for(bool o2 : {0, 1}) {
        nxt[(o + ((x / 2) & 1) + (((x & 1) + o2) / 2) & 1)][(o2 + (x & 1)) & 1] += cnt[u][o][o2];
      }
    }
    cnt[u][0][0] = nxt[0][0], cnt[u][0][1] = nxt[0][1], cnt[u][1][0] = nxt[1][0], cnt[u][1][1] = nxt[1][1];
    sum[u] = res[u][0] + cnt[u][0][0] + cnt[u][0][1];
    lazy[u] += x;
  }
  void pushdown(int u) {
    tag(u << 1, lazy[u]), tag((u << 1) | 1, lazy[u]), lazy[u] = 0;
  }
  void update(int u, int s, int t, ll x) {
    if(l[u] >= s && r[u] <= t) {
      tag(u, x);
      return;
    }
    pushdown(u);
    if(s <= r[u << 1]) {
      update(u << 1, s, t, x);
    }
    if(t >= l[(u << 1) | 1]) {
      update((u << 1) | 1, s, t, x);
    }
    pushup(u);
  }
  ll Getsum(int u, int s, int t) {
    if(l[u] >= s && r[u] <= t) {
      return sum[u];
    }
    pushdown(u);
    ll x = 0;
    if(s <= r[u << 1]) {
      x += Getsum(u << 1, s, t);
    }
    if(t >= l[(u << 1) | 1]) {
      x += Getsum((u << 1) | 1, s, t);
    }
    return x;
  }
}tr;

int n, m;

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for(int i = 1; i <= n; ++i) {
    cin >> tr.a[i];
  }
  tr.build(1, 1, n);
  for(int i = 1, op, l, r, x; i <= m; ++i) {
    cin >> op >> l >> r;
    if(op == 1) {
      cin >> x;
      tr.update(1, l, r, x);
    }else {
      cout << tr.Getsum(1, l, r) << "\n";
    }
  }
  return 0;
}