Dynamic Rankings

题目描述

The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the $k$-th smallest number of the given $N$ numbers. They have developed a more powerful system such that for $N$ numbers $a_1, a_2, \ldots, a_N$, you can ask it like: what is the $k$-th smallest number of $a_i, a_{i+1}, \ldots, a_j$? (For some $i \le j$, $0 \lt k \le j+1-i$ that you have given to it). More powerful, you can even change the value of some $a_i$, and continue to query, all the same.
Your task is to write a program for this computer, which

  • Reads $N$ numbers from the input.
  • Processes $M$ instructions of the input. These instructions include querying the $k$-th smallest number of $a_i, a_{i+1}, \ldots, a_j$ and change some $a_i$ to $t$.

题意概述

有一个长度为$N$的数列。有$M$次操作,每次操作询问数列第$i$项到第$j$项之间的第$k$小值,或者将第$i$项修改为$t$。
数据范围:$1 \le N \le 50000, \; 1 \le M \le 10000$。
内存限制:$32$M。

算法分析

对于这种询问区间第$k$小值的题目,很容易想到主席树。但由于主席树是一种类似前缀和的结构,一次修改操作需要修改$O(N)$棵线段树。这显然不是我们所希望的。
既然主席树类似前缀和,那么就可以借用维护前缀和的工具——树状数组。把树状数组的每个节点看成一棵线段树,这样一次修改操作就只需要修改$O(\log N)$棵线段树,时间复杂度为$O(\log^2N)$。而询问操作需要先把该询问在树状数组上用到的节点提取出来(有$O(\log N)$个),然后利用类似主席树的方法二分,时间复杂度也是$O(\log^2N)$。
但是!这题的内存限制非常小,接受不了$O((N+M)\log^2N)$的空间复杂度。再考虑主席树,它的空间复杂度是$O(N\log N)$的。因此可以对原序列建立静态的主席树,对修改操作利用树状数组维护,这样空间复杂度降至$O(N\log N+M\log^2N)$,可以通过。

代码

/*
 * Beware of Bigfoot!
 */

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>

static int const N = 60005;
static int const NM = 2000000;
int n, m, nn, a[N], arr_rt[N], bit_rt[N], rec[N];
struct Query {
  int o, i, j, k;
} q[N];
struct SegmentTree {
  int ch[2], sum;
} nd[NM];

int create(int rt = 0) { return nd[++nn] = nd[rt], nn; }

int arr_insert(int rt, int p) {
  rt = create(rt), ++nd[rt].sum;
  int L = 0, R = N;
  for (int cur = rt; L < R;) {
    int MID = L + R >> 1, b = p > MID;
    nd[cur].ch[b] = create(nd[cur].ch[b]), ++nd[nd[cur].ch[b]].sum,
    cur = nd[cur].ch[b];
    b ? L = MID + 1 : R = MID;
  }
  return rt;
}

void bit_insert(int &rt, int p, int v) {
  if (rt == 0)
    rt = create();
  nd[rt].sum += v;
  int L = 0, R = N;
  for (int cur = rt; L < R;) {
    int MID = L + R >> 1, b = p > MID;
    if (nd[cur].ch[b] == 0)
      nd[cur].ch[b] = create();
    nd[nd[cur].ch[b]].sum += v;
    int tmp = nd[cur].ch[b];
    cur = tmp, b ? L = MID + 1 : R = MID;
  }
}

int bit_add(int p, int v, int c) {
  for (; p <= n; p += p & -p)
    bit_insert(bit_rt[p], v, c);
}

int main() {
  int T;
  scanf("%d", &T);
  for (; T--;) {
    std::map<int, int> mp;
    memset(arr_rt, nn = 0, sizeof arr_rt), memset(bit_rt, 0, sizeof bit_rt);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
      scanf("%d", &a[i]), mp[a[i]] = 0;
    for (int i = 1; i <= m; ++i) {
      char c;
      scanf(" %c", &c);
      if (c == 'Q')
        q[i].o = 0, scanf("%d%d%d", &q[i].i, &q[i].j, &q[i].k);
      else
        q[i].o = 1, scanf("%d%d", &q[i].i, &q[i].j), mp[q[i].j] = 0;
    }
    int cnt = 0;
    for (std::map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it)
      rec[cnt] = it->first, it->second = cnt++;
    for (int i = 1; i <= n; ++i)
      arr_rt[i] = arr_insert(arr_rt[i - 1], mp[a[i]]);
    for (int i = 1; i <= m; ++i) {
      if (q[i].o == 0) {
        std::vector<int> a, b;
        a.push_back(arr_rt[q[i].i - 1]), b.push_back(arr_rt[q[i].j]);
        for (int p = q[i].i - 1; p; p -= p & -p)
          a.push_back(bit_rt[p]);
        for (int p = q[i].j; p; p -= p & -p)
          b.push_back(bit_rt[p]);
        int L = 0, R = N;
        for (; L < R;) {
          int sum = 0;
          for (int i = 0; i < a.size(); ++i)
            sum -= nd[nd[a[i]].ch[0]].sum;
          for (int i = 0; i < b.size(); ++i)
            sum += nd[nd[b[i]].ch[0]].sum;
          int MID = L + R >> 1;
          if (sum < q[i].k) {
            L = MID + 1, q[i].k -= sum;
            for (int i = 0; i < a.size(); ++i)
              a[i] = nd[a[i]].ch[1];
            for (int i = 0; i < b.size(); ++i)
              b[i] = nd[b[i]].ch[1];
          } else {
            R = MID;
            for (int i = 0; i < a.size(); ++i)
              a[i] = nd[a[i]].ch[0];
            for (int i = 0; i < b.size(); ++i)
              b[i] = nd[b[i]].ch[0];
          }
        }
        printf("%d\n", rec[L]);
      } else
        bit_add(q[i].i, mp[a[q[i].i]], -1),
            bit_add(q[i].i, mp[a[q[i].i] = q[i].j], 1);
    }
  }
  return 0;
}

Little Pony and Lord Tirek

题目描述

Lord Tirek is a centaur and the main antagonist in the season four finale episodes in the series “My Little Pony: Friendship Is Magic”. In “Twilight’s Kingdom” (Part 1), Tirek escapes from Tartarus and drains magic from ponies to grow stronger.
The core skill of Tirek is called Absorb Mana. It takes all mana from a magic creature and gives them to the caster.
Now to simplify the problem, assume you have $n$ ponies (numbered from $1$ to $n$). Each pony has three attributes:

  • $s_i$: amount of mana that the pony has at time $0$;
  • $m_i$: maximum mana that the pony can have;
  • $r_i$: mana regeneration per unit time.

Lord Tirek will do $m$ instructions, each of them can be described with three integers: $t_i, l_i, r_i$. The instruction means that at time $t_i$, Tirek will use Absorb Mana on ponies with numbers from $l_i$ to $r_i$ (both borders inclusive). We’ll give you all the m instructions in order, count how much mana Tirek absorbs for each instruction.

题意概述

有$n$匹马,第$i$匹马初始时有$s_i$点魔法,魔法上限为$m_i$,每秒增加$r_i$点魔法。有$m$次操作,第$i$次操作在第$t_i$秒进行,将区间$[l_i, r_i]$中马的魔法清零。求每次操作清除了多少点魔法。
数据范围:$1 \le n, m \le 10^5, \; 0 \le s_i \le m_i \le 10^5, \; 0 \le r_i \le 10^5, \; 0 \le t_i \le 10^9$。

算法分析

显然,答案只与两次询问的时间差有关。
用set维护一些不相交的区间(它们的并是整个序列),每段区间内所有马的上次操作时间相同。每次操作就相当于切割一些区间然后合并一些区间。由于每次至多切割两个区间,因此总共操作的区间个数是$O(n)$的。
考虑区间询问。每匹马都可以表示为一个分段函数,我们用主席树来维护,第$i$棵线段树表示经过$i$秒后每匹马的函数。因为有些马有初始魔法,所以需要建两棵主席树,一棵表示第$i$匹马的初始魔法为$s_i$,另一棵表示所有马的初始魔法为$0$。
那么只要预处理出主席树,对于每次操作,在set中找到其对应的一些区间,在主席树上询问答案,并更新区间。

代码

/*
 * So, is the glass half empty, half full, or just twice as large as it needs to
 * be?
 */

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>

template <typename T> void read(T &n) {
  char c;
  for (; (c = getchar()) < '0' || c > '9';)
    ;
  for (n = c - '0'; (c = getchar()) >= '0' && c <= '9'; (n *= 10) += c - '0')
    ;
}

typedef long long ll;
typedef int const ic;

static ic N = 100005;
int numn, root[N << 1];
struct Pony {
  int s, m, r;
} p[N];
struct Event {
  int t, p, b;
} e[N];
struct Query {
  int t, l, r;
  bool operator<(Query const &a) const { return l < a.l; }
} q[N];
struct SegmentTree {
  int child[2];
  ll a, b;
} node[N << 6];
std::set<Query> st;

void update(ic &root) {
  if (!root)
    return;
  node[root].a = node[node[root].child[0]].a + node[node[root].child[1]].a;
  node[root].b = node[node[root].child[0]].b + node[node[root].child[1]].b;
}

void modify(int &root, ic &nl, ic &nr, ic &p, ic &a, ic &b, ic &flag) {
  if (p > nr || nl > p)
    return;
  if (flag)
    node[++numn] = node[root], root = numn;
  else if (!root)
    root = ++numn;
  if (nl == nr) {
    node[root].a = a, node[root].b = b;
    return;
  }
  ic mid = (nl + nr) >> 1;
  modify(node[root].child[0], nl, mid, p, a, b, flag);
  modify(node[root].child[1], mid + 1, nr, p, a, b, flag);
  update(root);
}

ll query(ic &root, ic &nl, ic &nr, ic &t, ic &l, ic &r) {
  if (!root || l > nr || nl > r)
    return 0;
  if (l <= nl && nr <= r)
    return node[root].a * t + node[root].b;
  ic mid = (nl + nr) >> 1;
  return query(node[root].child[0], nl, mid, t, l, r) +
         query(node[root].child[1], mid + 1, nr, t, l, r);
}

int main() {
  int n, m;
  read(n);
  for (int i = 0; i < n; ++i)
    read(p[i].s), read(p[i].m), read(p[i].r);
  read(m);
  for (int i = 0; i < m; ++i)
    read(q[i].t), read(q[i].l), read(q[i].r), --q[i].l, --q[i].r;
  for (int i = 0; i < n; ++i)
    modify(root[0], 0, n - 1, i, p[i].r, 0, 0),
        e[i] = (Event){p[i].r ? p[i].m / p[i].r + 1 : N, i, p[i].m};
  std::sort(e, e + n, [](Event const &a, Event const &b) { return a.t < b.t; });
  for (int i = 1, p = 0; i < N; ++i) {
    root[i] = root[i - 1];
    for (; p < n && e[p].t == i; ++p)
      modify(root[i], 0, n - 1, e[p].p, 0, e[p].b, 1);
  }
  for (int i = 0; i < n; ++i)
    modify(root[N], 0, n - 1, i, p[i].r, p[i].s, 0),
        e[i] = (Event){p[i].r ? (p[i].m - p[i].s) / p[i].r + 1 : N, i, p[i].m};
  std::sort(e, e + n, [](Event const &a, Event const &b) { return a.t < b.t; });
  for (int i = 1, p = 0; i < N; ++i) {
    root[N + i] = root[N + i - 1];
    for (; p < n && e[p].t == i; ++p)
      modify(root[N + i], 0, n - 1, e[p].p, 0, e[p].b, 1);
  }
  st.insert((Query){0, 0, n - 1});
  for (int i = 0; i < m; ++i) {
    auto rec = st.lower_bound((Query){q[i].t, q[i].l, q[i].r});
    if (rec == st.end())
      --rec;
    for (; rec != st.begin() && rec->r >= q[i].l; --rec)
      ;
    if (rec->r < q[i].l)
      ++rec;
    auto tmp = rec;
    Query l = (Query){rec->t, rec->l, q[i].l - 1};
    ll ans = 0;
    for (; rec != st.end() && rec->l <= q[i].r; ++rec)
      ans += rec->t ? query(root[std::min(q[i].t - rec->t, N - 1)], 0, n - 1,
                            q[i].t - rec->t, std::max(rec->l, q[i].l),
                            std::min(rec->r, q[i].r))
                    : query(root[std::min(q[i].t - rec->t, N - 1) + N], 0,
                            n - 1, q[i].t - rec->t, std::max(rec->l, q[i].l),
                            std::min(rec->r, q[i].r));
    printf("%lld\n", ans), --rec;
    Query r = (Query){rec->t, q[i].r + 1, rec->r};
    for (; tmp != st.end() && tmp->l <= q[i].r;)
      st.erase(tmp++);
    st.insert((Query){q[i].t, q[i].l, q[i].r});
    if (l.l <= l.r)
      st.insert(l);
    if (r.l <= r.r)
      st.insert(r);
  }
  return 0;
}

Destiny

题目描述

Once, Leha found in the left pocket an array consisting of $n$ integers, and in the right pocket $q$ queries of the form $l$ $r$ $k$. If there are queries, then they must be answered. Answer for the query is minimal $x$ such that $x$ occurs in the interval $l$ $r$ strictly more than ${r-l+1 \over k}$ times or $-1$ if there is no such number. Help Leha with such a difficult task.

题意概述

给定包含$n$个数的序列,有$q$次询问,每次询问给定$l, r, k$,求区间$[l, r]$中出现次数严格大于${r-l+1 \over k}$的最小数字。
数据范围:$1 \le n, q \le 3 \times 10^5, \; 1 \le a_i \le n, \; 2 \le k \le 5$。

算法分析

建主席树,第$i$个位置上的线段树是前$i$个数的权值线段树。这样就可以用前缀和思想快速求出区间$[l, r]$中某个数出现的次数。对于每个询问,用第$r$个位置上线段树的值减去第$(l-1)$个位置上线段树的值,直接在主席树上暴力查找。由于$k$比较小,查找复杂度不会太高。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline int read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return 0;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', len);
  }
  template <typename T>
  inline IOManager r(T &x) {
    read(x); return *this;
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char c) {
    putchar(c);
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
  template <typename T>
  inline IOManager w(T x) {
    write(x); return *this;
  }
} io;

struct SegmentTree {
private:
  static const int N = 9000000;
  int tot;
  struct Node {
    int val, child[2];
  } node[N];
  int add_point(int root, int l, int r, int p) {
    if (l == r) {
      node[++ tot] = (Node) { node[root].val, 0, 0 };
      ++ node[tot].val; return tot;
    }
    int mid = l + r >> 1, rec = ++ tot;
    node[rec] = (Node) { 0, 0, 0 };
    if (p <= mid) {
      node[rec].child[1] = node[root].child[1];
      node[rec].child[0] = add_point(node[root].child[0], l, mid, p);
    } else {
      node[rec].child[0] = node[root].child[0];
      node[rec].child[1] = add_point(node[root].child[1], mid + 1, r, p);
    }
    node[rec].val = node[node[rec].child[0]].val + node[node[rec].child[1]].val;
    return rec;
  }
  int query_point(int root1, int root2, int l, int r, int p) {
    if (node[root2].val - node[root1].val < p) return -1;
    if (l == r) return node[root2].val - node[root1].val >= p ? l : -1;
    int mid = l + r >> 1, res = -1;
    if (node[node[root2].child[0]].val - node[node[root1].child[0]].val >= p)
      res = query_point(node[root1].child[0], node[root2].child[0], l, mid, p);
    if (~ res) return res;
    res = query_point(node[root1].child[1], node[root2].child[1], mid + 1, r, p);
    return res;
  }

public:
  int n, cnt, root[N];
  void add(int p) {
    root[cnt + 1] = add_point(root[cnt], 1, n, p), ++ cnt;
  }
  int find(int l, int r, int p) {
    return query_point(root[l - 1], root[r], 1, n, p);
  }
  void print() {
    cout << cnt << endl;
    for (int i = 1; i <= cnt; ++ i) cout << root[i] << ' ';
    cout << endl << tot << endl;
    for (int i = 1; i <= tot; ++ i) cout << i << ' ' << node[i].val << ' ' << node[i].child[0] << ' ' << node[i].child[1] << endl;
  }
};

struct Solver {
private:
  int n, q;
  SegmentTree tree;
  void input() {
    io.r(n).r(q);
    tree.n = n;
    for (int i = 1; i <= n; ++ i) {
      int t; io.read(t), tree.add(t);
    }
  }
  void process() {
    int l, r, k; io.r(l).r(r).r(k);
    int p = (r - l + 1) / k + 1;
    io.w(tree.find(l, r, p)).w('\n');
  }

public:
  void solve() {
    input(); while (q --) process();
  }
} solver;

int main() {
  solver.solve();
  return 0;
}

Till I Collapse

题目描述

Rick and Morty want to find MR. PBH and they can’t do it alone. So they need of Mr. Meeseeks. They Have generated $n$ Mr. Meeseeks, standing in a line numbered from $1$ to $n$. Each of them has his own color. $i$-th Mr. Meeseeks’ color is $a_i$.
Rick and Morty are gathering their army and they want to divide Mr. Meeseeks into some squads. They don’t want their squads to be too colorful, so each squad should have Mr. Meeseeks of at most $k$ different colors. Also each squad should be a continuous subarray of Mr. Meeseeks in the line. Meaning that for each $1 \le i \le e \le j \le n$, if Mr. Meeseeks number $i$ and Mr. Meeseeks number $j$ are in the same squad then Mr. Meeseeks number $e$ should be in that same squad.
Also, each squad needs its own presidio, and building a presidio needs money, so they want the total number of squads to be minimized.
Rick and Morty haven’t finalized the exact value of $k$, so in order to choose it, for each $k$ between $1$ and $n$ (inclusive) need to know the minimum number of presidios needed.

题意概述

给定一个长度为$n$的数列,第$i$个数为$a_i$。要求将它们分成若干连续段。对于所有$k \in [1, n]$,问至少分成多少段,使得每一段中数字的种类数不超过$k$。
数据范围:$1 \le a_i \le n \le 10^5$。

算法分析1

有个显然的贪心策略:每一段越长越好。
容易发现答案一定单调不递增。对于$i \le j$,如果$ans_i=ans_j$,那么$ans_i=ans_{i+1}=ans_{i+2}= \cdots =ans_j$。因此我们可以贪心$O(n)$计算出左端点和右端点的$ans$,若它们相等,则将这个区间中的$ans$全都赋成左端点的$ans$;否则,取区间中点,并递归处理左右两个区间。

代码1

#include <cstdio>
#include <cstring>
using namespace std;
int n, last, a[100001], c[100001], ans[100001];
int get(int t) {
  memset(c, 0, sizeof(c));
  int p = 0, q = 1, ret = 0;
  while (q <= n) {
    int cnt = 1; c[a[q]] = 1;
    while (q < n) {
      if (cnt < t || c[a[q + 1]]) {
        cnt += !c[a[++q]], ++c[a[q]];
      } else break;
    }
    while (p < q) --c[a[++p]];
    ++q, ++ret;
  }
  return ret;
}
void solve(int l, int r) {
  if (l > r) return;
  ans[l] = get(l), ans[r] = get(r);
  if (ans[l] == ans[r]) {
    for (int i = l + 1; i < r; ++i) ans[i] = ans[l];
    return;
  }
  int mid = l + r >> 1;
  solve(l + 1, mid), solve(mid + 1, r - 1);
}
int main()
{
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  solve(1, n);
  for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
  printf("\n");
  return 0;
}

算法分析2

建可持久化线段树,第$i$个节点上的线段树维护区间$[j, i]$中数字的种类数。当遇到一个前面已经出现过的数字时,就在前面出现的位置上减一,在当前位置上加一。枚举$k$,并依据上述贪心策略,即可得到答案。

代码2

#include <cstdio>
using namespace std;
struct node_type {
  int val, child[2];
} node[4000001];
int n, tot, ans, a[100001], root[100001], pre[100001];
int insert_line(int root, int l, int r, int p, int val) {
  if (l == r) {
    node[++tot].val = node[root].val + val;
    node[tot].child[0] = node[tot].child[1] = 0;
    return tot;
  }
  int mid = l + r >> 1, ch;
  if (p <= mid) {
    ch = insert_line(node[root].child[0], l, mid, p, val);
    node[++tot].child[0] = ch, node[tot].child[1] = node[root].child[1];
  } else {
    ch = insert_line(node[root].child[1], mid + 1, r, p, val);
    node[++tot].child[0] = node[root].child[0], node[tot].child[1] = ch;
  }
  node[tot].val = node[node[tot].child[0]].val + node[node[tot].child[1]].val;
  return tot;
}
int query(int root, int l, int r, int p) {
  if (l == r) if (p >= node[root].val) return l; else return l + 1;
  int mid = l + r >> 1;
  if (p >= node[node[root].child[1]].val) return query(node[root].child[0], l, mid, p - node[node[root].child[1]].val);
  else return query(node[root].child[1], mid + 1, r, p);
}
int main()
{
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  pre[a[1]] = 1, root[1] = insert_line(0, 1, n, 1, 1);
  for (int i = 2; i <= n; ++i) {
    int rt = root[i - 1];
    if (pre[a[i]]) rt = insert_line(rt, 1, n, pre[a[i]], -1);
    pre[a[i]] = i, root[i] = insert_line(rt, 1, n, i, 1);
  }
  for (int i = 1; i <= n; ++i) {
    if (ans != 1) {
      ans = 0;
      int l = n, r;
      while (l) r = l, l = query(root[r], 1, n, i) - 1, ++ans;
    }
    printf("%d ", ans);
  }
  printf("\n");
  return 0;
}

Pishty and Tree

题目描述

A little boy Pishty lives in Khust – an ancient town in Uzhlyandia with their medieval castles and smart bears.
The gem of Khust is a very valuable castle because it protects the citizens of Uhzlyandia from the Durdom kingdom’s army. Pishty also like this castle because it hides old secrets in long halls and high towers…
The castle can be described as an undirected tree with $N$ vertices and $N-1$ edges. Each edge has a magic number $C$.
When a group of tourists visit the castle, they are interested in a path between vertices $U$ and $V$. They think that an edge is interesting if its magic number is less than or equal to $K$. The total attractivity of the path is the xor of all interesting edges on it.
The emperor of Uzhlyandia is interested in tourism development, and so he wants to find the total attractivity of the paths for each group. Because Pishty wants to become the emperor’s knight, he wants to know all of this information too. But he can’t do it on his own because there are a large number of groups. Please help Pishty to solve this unthinkable problem.
Given $M$ groups of tourists, find the total attractivity of the path for each group.

题意概述

给定一棵有$N$个节点的树,每条边都有一个权值$C$。有$M$组询问,每组询问给定$U, V$和$K$,求$U$到$V$路径上权值不超过$K$的边的权值的异或和。
数据范围:$1 \le N, M \le 10^5, \; 1 \le C, K \le 10^9$。

算法分析1

由于要求的是异或和,且$x \oplus y \oplus y=x$,因此可以分别求出$U, V$到根节点路径上权值不超过$K$的边的权值的异或和,将两个结果异或一下便得到了答案。
考虑采用树链剖分。定义重边为一个节点连向它最大子树的边,由重边构成的链称为重链;其他边均为轻边。令$size_x$表示以节点$x$为根的子树大小。对于一条轻边$(u, v)$,有$2size_v \lt size_u$。对于树中的任一节点,从根节点到它的路径上不超过$O(\log n)$条重链,不超过$O(\log n)$条轻边。在重链上用树状数组维护前缀和,即可在$O(\log^2n)$的时间内给出一组询问的答案。
因为有$K$这个限制,所以我们考虑离线做法:将边按$C$从小到大排序,将询问按$K$从小到大排序,在加入边的同时处理询问。

代码1

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
struct edge {
  long long u, v, c, nxt;
  bool operator < (const edge &a) const { return c < a.c; }
} e[200001], r[100001];
struct ask {
  long long u, v, k, id, ans;
  bool operator < (const ask &a) const { return k < a.k; }
} a[100001];
bool cmp(ask a, ask b) { return a.id < b.id; }
struct binary_indexed_tree {
  long long n;
  vector<long long> a;
  void init(long long t) { n = t + 10, a.clear(), a.resize(n); }
  void add(long long p, long long t) {
    for (long long i = p; i < n; i += i & -i) a[i] ^= t;
  }
  long long sum(long long p) {
    long long ret = 0;
    for (long long i = p; i; i -= i & -i) ret ^= a[i];
    return ret;
  }
} tree[100001];
long long T, n, m, nume, tot, pnt, h[100001], size[100001];
long long up[100001], down[100001], father[100001], dist[100001];
long long id[100001], len[100001], cnt[100001];
void add_edge(long long u, long long v, long long c) {
  e[++nume].u = u, e[nume].v = v, e[nume].c = c;
  e[nume].nxt = h[u], h[u] = nume;
  e[++nume].u = v, e[nume].v = u, e[nume].c = c;
  e[nume].nxt = h[v], h[v] = nume;
}
void dfs(long long t, long long fa, long long depth) {
  long long ma = 0;
  size[t] = 1, father[t] = fa, dist[t] = depth;
  for (long long i = h[t]; i; i = e[i].nxt) {
    if (e[i].v != fa) {
      dfs(e[i].v, t, e[i].c);
      ma = max(ma, size[e[i].v]);
      size[t] += size[e[i].v];
    }
  }
  for (long long i = h[t]; i; i = e[i].nxt) {
    if (e[i].v != fa && ma == size[e[i].v]) { down[t] = e[i].v; break; }
  }
}
void init(long long t, long long fa, long long rt) {
  if (!up[t]) id[up[t] = t] = ++tot, ++cnt[t], len[t] = 1;
  else ++cnt[up[t] = rt], len[t] = len[fa] + 1;
  for (long long i = h[t]; i; i = e[i].nxt) {
    if (e[i].v != fa) {
      if (!up[e[i].v]) init(e[i].v, t, e[i].v);
      else init(e[i].v, t, rt);
    }
  }
  if (t == up[t]) tree[id[t]].init(cnt[t]);
}
void insert_line(edge e) {
  if (up[e.u] == up[e.v] && len[e.u] < len[e.v]) {
    tree[id[up[e.u]]].add(len[e.u], e.c);
  }
}
long long query(long long u, long long k) {
  long long ret = 0;
  while (u != 1) {
    ret ^= tree[id[up[u]]].sum(len[u] - 1);
    u = up[u];
    if (u != 1) {
      if (dist[u] <= k) ret ^= dist[u];
      u = father[u];
    }
  }
  return ret;
}
int main()
{
  scanf("%lld", &T);
  while (T--) {
    scanf("%lld", &n);
    nume = tot = 0, pnt = 1;
    memset(h, 0, sizeof(h));
    memset(up, 0, sizeof(up));
    memset(down, 0, sizeof(down));
    memset(cnt, 0, sizeof(cnt));
    for (long long i = 1; i < n; ++i) {
      r[i].nxt = 0;
      scanf("%lld%lld%lld", &r[i].u, &r[i].v, &r[i].c);
    }
    sort(r + 1, r + n);
    for (long long i = 1; i < n; ++i) add_edge(r[i].u, r[i].v, r[i].c);
    dfs(1, 0, 0);
    for (long long i = 1; i <= n; ++i) if (down[i]) up[down[i]] = i;
    init(1, 0, 1);
    scanf("%lld", &m);
    for (long long i = 1; i <= m; ++i) {
      a[i].id = i, a[i].ans = 0;
      scanf("%lld%lld%lld", &a[i].u, &a[i].v, &a[i].k);
    }
    sort(a + 1, a + m + 1);
    for (long long i = 1; i <= m; ++i) {
      while (pnt <= nume && e[pnt].c <= a[i].k) insert_line(e[pnt++]);
      a[i].ans = query(a[i].u, a[i].k) ^ query(a[i].v, a[i].k);
    }
    sort(a + 1, a + m + 1, cmp);
    for (long long i = 1; i <= m; ++i) printf("%lld\n", a[i].ans);
  }
  return 0;
}

算法分析2

由于要求的是异或和,因此可以对整棵树建可持久化Trie树,每次询问直接查询$U, V$到根节点的路径上边权不超过$K$的边的权值的异或和,将两结果异或起来。

代码2

#include <cstdio>
#include <cstring>
using namespace std;
struct node_type {
  long long val, child[2];
} node[4000001];
struct edge {
  long long v, c, nxt;
} e[200001];
long long T, n, m, tot, nume, h[100001], root[100001];
void add_edge(long long u, long long v, long long c) {
  e[++nume].v = v, e[nume].c = c, e[nume].nxt = h[u], h[u] = nume;
  e[++nume].v = u, e[nume].c = c, e[nume].nxt = h[v], h[v] = nume;
}
long long insert_node(long long root, long long val, long long depth) {
  if (depth < 0) {
    node[++tot].val = node[root].val ^ val, node[tot].child[0] = node[tot].child[1] = 0;
    return tot;
  }
  long long t = (val >> depth) & 1;
  long long ch = insert_node(node[root].child[t], val, depth - 1);
  node[++tot].child[t] = ch, node[tot].child[!t] = node[root].child[!t];
  node[tot].val = node[node[tot].child[t]].val ^ node[node[tot].child[!t]].val;
  return tot;
}
void dfs(long long t, long long fa) {
  for (int i = h[t]; i; i = e[i].nxt) {
    if (e[i].v != fa) {
      root[e[i].v] = insert_node(root[t], e[i].c, 30);
      dfs(e[i].v, t);
    }
  }
}
long long get_dist(long long root, long long k, long long depth) {
  if (depth < 0) return node[root].val;
  long long t = (k >> depth) & 1;
  if (t) return node[node[root].child[0]].val ^ get_dist(node[root].child[1], k, depth - 1);
  else return get_dist(node[root].child[0], k, depth - 1);
}
int main()
{
  scanf("%lld", &T);
  while (T--) {
    scanf("%lld", &n);
    nume = tot = 0;
    memset(h, 0, sizeof(h));
    for (int i = 1; i < n; ++i) {
      long long u, v, c;
      scanf("%lld%lld%lld", &u, &v, &c);
      add_edge(u, v, c);
    }
    root[1] = insert_node(0, 0, 30);
    dfs(1, 0);
    scanf("%lld", &m);
    for (int i = 1; i <= m; ++i) {
      long long u, v, k;
      scanf("%lld%lld%lld", &u, &v, &k);
      printf("%lld\n", get_dist(root[u], k, 30) ^ get_dist(root[v], k, 30));
    }
  }
  return 0;
}