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

Goodbye Souvenir

题目描述

I won’t feel lonely, nor will I be sorrowful… not before everything is buried.
A string of $n$ beads is left as the message of leaving. The beads are numbered from $1$ to $n$ from left to right, each having a shape numbered by integers between $1$ and $n$ inclusive. Some beads may have the same shapes.
The memory of a shape $x$ in a certain subsegment of beads, is defined to be the difference between the last position and the first position that shape $x$ appears in the segment. The memory of a subsegment is the sum of memories over all shapes that occur in it.
From time to time, shapes of beads change as well as the memories. Sometimes, the past secreted in subsegments are being recalled, and you are to find the memory for each of them.

题意概述

给定一个长度为$n$的序列$a_i$,有$m$次操作。操作有两种:给定$p, x$,将第$p$个数修改成$x$;给定$l, r$,求$[l, r]$内每种数字的长度之和。某种数字长度的定义是该数字在区间内第一次出现的位置与最后一次出现的位置之差。
数据范围:$1 \le n, m \le 10^5, \; 1 \le a_i, x \le n$。

算法分析

设区间$[l, r]$中某种数字出现的位置为$p_1, p_2, \ldots, p_k$,显然这个数字对答案的贡献为$p_k-p_1=(p_2-p_1)+(p_3-p_2)+ \cdots +(p_k-p_{k-1})$。令$pre_i$表示在$i$之前离$i$最近的等于$a_i$的数的位置,那么贡献就是$(p_2-pre_2)+(p_3-pre_3)+ \cdots +(p_k-pre_k)$。我们把每个数$a_i$想像成二维空间中的一个点$(pre_i, i)$,它的权值是$i-pre_i$。那么问题就变成了求在矩形$(l, l)-(r, r)$中的点权之和。这可以用传说中的CDQ分治来解决。

代码

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

#define int long long

using namespace std;

void maxify(int &a, int b) { b > a && (a = b); }
void minify(int &a, int b) { b < a && (a = b); }

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 operator > (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 operator < (T x) {
    write(x); return *this;
  }
} io;

struct BinaryIndexedTree {
private:
  static const int N = 200000;
  int n, a[N];

public:
  void init(int t) {
    n = t, memset(a, 0, sizeof a);
  }
  void add(int p, int v) {
    for (; p <= n; p += p & -p) a[p] += v;
  }
  int get(int p) {
    int ret = 0;
    for (; p; p -= p & -p) ret += a[p];
    return ret;
  }
};

struct Set {
private:
  static const int N = 200000;
  int a[N];
  set <int> s[N];
  set <int> :: iterator it;

public:
  void modify(int p, int v) {
    if (a[p]) s[a[p]].erase(p);
    a[p] = v;
    s[a[p]].insert(p);
  }
  int prev(int p) {
    it = s[a[p]].find(p);
    return it == s[a[p]].begin() ? *it : *(-- it);
  }
  int next(int p) {
    it = ++ s[a[p]].find(p);
    return it == s[a[p]].end() ? *(-- it) : *it;
  }
};

#define MODIFY 1
#define QUERY 2

struct Solver {
private:
  static const int N = 200000;
  int n, m, numq, top, pos[N], pre[N], ans[N];
  BinaryIndexedTree tree;
  Set s;
  struct Query {
    int type, x, y, w, id;
    bool operator < (const Query &q) const {
      return x == q.x ? type < q.type : x < q.x;
    }
  } q[N << 2], tmp[N << 2];
  void add_query(int type, int x, int y, int w, int id) {
    q[++ numq] = (Query) { type, x, y, w, id };
  } 
  void input() {
    io > n > m;
    for (int i = 2; i <= n + 1; ++ i) {
      int t; io > t, s.modify(i, t);
      int prev = s.prev(i);
      add_query(MODIFY, prev, i, i - prev, 0);
    }
    for (int i = 1; i <= m; ++ i) {
      int o; io > o;
      if (o == 1) {
        int p, x; io > p > x; ++ p;
        int prev = s.prev(p), next = s.next(p);
        if (prev < p) add_query(MODIFY, prev, p, prev - p, 0);
        if (next > p) add_query(MODIFY, p, next, p - next, 0);
        if (prev < p && next > p) add_query(MODIFY, prev, next, next - prev, 0);
        s.modify(p, x);
        prev = s.prev(p), next = s.next(p);
        if (prev < p && next > p) add_query(MODIFY, prev, next, prev - next, 0);
        if (prev < p) add_query(MODIFY, prev, p, p - prev, 0);
        if (next > p) add_query(MODIFY, p, next, next - p, 0);
      } else {
        int l, r; io > l > r, ++ l, ++ r, ++ top;
        add_query(QUERY, r, r, 1, top);
        add_query(QUERY, r, l - 1, -1, top);
        add_query(QUERY, l - 1, r, -1, top);
        add_query(QUERY, l - 1, l - 1, 1, top);
      }
    }
  }
  void process(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    process(l, mid), process(mid + 1, r);
    int s = l, t = mid + 1, pnt = l;
    while (s <= mid && t <= r) {
      if (q[s] < q[t]) {
        if (q[s].type == MODIFY) tree.add(q[s].y, q[s].w);
        tmp[pnt ++] = q[s ++];
      } else {
        if (q[t].type == QUERY) ans[q[t].id] += q[t].w * tree.get(q[t].y);
        tmp[pnt ++] = q[t ++];
      }
    }
    while (t <= r) {
      if (q[t].type == QUERY) ans[q[t].id] += q[t].w * tree.get(q[t].y);
      tmp[pnt ++] = q[t ++];
    }
    for (int i = l; i < s; ++ i) if (q[i].type == MODIFY) tree.add(q[i].y, -q[i].w);
    while (s <= mid) tmp[pnt ++] = q[s ++];
    for (int i = l; i <= r; ++ i) q[i] = tmp[i];
  }

public:
  void solve() {
    input(), tree.init(n + 1), process(1, numq);
    for (int i = 1; i <= top; ++ i) io < ans[i] < '\n';
  }
} solver;

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

Sereja and Subsequences

题目描述

Sereja has a sequence that consists of $n$ positive integers, $a_1, a_2, \ldots, a_n$.
First Sereja took a piece of squared paper and wrote all distinct non-empty non-decreasing subsequences of sequence $a$. Then for each sequence written on the squared paper, Sereja wrote on a piece of lines paper all sequences that do not exceed it.
A sequence of positive integers $x=x_1, x_2, \ldots, x_r$ doesn’t exceed a sequence of positive integers $y=y_1, y_2, \ldots, y_r$, if the following inequation holds: $x_1 \le y_1, x_2 \le y_2, \ldots, x_r \le y_r$.
Now Sereja wonders, how many sequences are written on the lines piece of paper. Help Sereja, find the required quantity modulo $1000000007$ ($10^9+7$).

题意概述

定义一个序列$a_1, a_2, \ldots, a_k$的数量等于长度为$k$且第$i$个元素不大于$a_i$的序列的个数。给定一个长度为$n$的序列,求其所有不下降子序列的数量之和。
数据范围:$1 \le n \le 10^5, \; 1 \le a_i \le 10^6$。

算法分析

显然,对于一个序列$a_1, a_2, \ldots, a_k$,它的数量为$a_1a_2 \cdots a_k$。令$f_i$表示以$i$结尾的不下降子序列的数量之和。设当前枚举到第$i$个数,转移方程如下
$$f_{a_i}=(1+f_1+f_2+ \cdots +f_{a_i})a_i$$
可以用树状数组来维护前缀和。最后得到的$f_1+f_2+ \cdots +f_{10^6}$就是答案。

代码

<?php
  const MAX_NUM = 1000000;
  const MOD = 1000000007;

  $tree = array();
  for ($i = 0; $i <= MAX_NUM; ++ $i) array_push($tree, 0);

  function add($pos, $val) {
    global $tree;
    for (; $pos <= MAX_NUM; $pos += $pos & -$pos) {
      $tree[$pos] += $val;
      $tree[$pos] -= (int) ($tree[$pos] / MOD) * MOD;
    }
  }

  function get($pos) {
    global $tree;
    $ret = 0;
    for (; $pos; $pos -= $pos & -$pos) {
      $ret += $tree[$pos];
      $ret -= (int) ($ret / MOD) * MOD;
    }
    return $ret;
  }

  $n = fgets(STDIN);
  $a = explode(' ', trim(fgets(STDIN)));
  for ($i = 0; $i < $n; ++ $i) {
    $sum = get($a[$i]);
    add($a[$i], $sum * $a[$i] + $a[$i] - $sum + get($a[$i] - 1));
  }
  $ans = get(MAX_NUM);
  $ans -= (int) ($ans / MOD) * MOD;
  echo $ans . "\n";
?>

Cards Sorting

题目描述

Vasily has a deck of cards consisting of $n$ cards. There is an integer on each of the cards, this integer is between $1$ and $100000$, inclusive. It is possible that some cards have the same integers on them.
Vasily decided to sort the cards. To do this, he repeatedly takes the top card from the deck, and if the number on it equals the minimum number written on the cards in the deck, then he places the card away. Otherwise, he puts it under the deck and takes the next card from the top, and so on. The process ends as soon as there are no cards in the deck. You can assume that Vasily always knows the minimum number written on some card in the remaining deck, but doesn’t know where this card (or these cards) is.
You are to determine the total number of times Vasily takes the top card from the deck.

题意概述

有$n$张卡牌,第$i$张卡牌上的数字为$a_i$。每次从牌堆顶拿一张牌,如果它上面的数字是当前牌堆中最小的,则将它扔掉,否则将它放到牌堆底。问几次操作后牌堆为空。
数据范围:$1 \le n \le 10^5, \; 1 \le a_i \le 10^5$。

算法分析

先对卡牌上的数进行计数排序,接着从小到大处理:维护一个$now$指针,表示当前走到了第$now$个数;用树状数组维护当前剩余数字个数的前缀和,这样可以快速求出从第$i$个数走到第$j$个数所需要的次数。

代码

#include <iostream>
#include <vector>
using namespace std;
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;
long long n, t, now, ans, pre;
vector<long long> b[100001];
int main()
{
  cin >> n;
  tree.init(n);
  for (long long i = 1; i <= n; ++i) {
    cin >> t; tree.add(i, 1), b[t].push_back(i);
  }
  for (long long i = 1; i <= 100000; ++i) {
    if (!b[i].size()) continue; long long pnt = 0;
    while (pnt < b[i].size() && b[i][pnt] < now) ++pnt; --pnt;
    if (pnt < 0) pnt = b[i].size() - 1;
    if (b[i][pnt] > now) ans += tree.sum(b[i][pnt]) - tree.sum(now);
    else ans += tree.sum(n) - tree.sum(now) + tree.sum(b[i][pnt]);
    for (long long j = 0; j < b[i].size(); ++j) tree.add(b[i][j], -1);
    now = b[i][pnt];
  }
  cout << ans << endl;
  return 0;
}

DNA Evolution

题目描述

Everyone knows that DNA strands consist of nucleotides. There are four types of nucleotides: “A”, “T”, “G”, “C”. A DNA strand is a sequence of nucleotides. Scientists decided to track evolution of a rare species, which DNA strand was string $s$ initially.
Evolution of the species is described as a sequence of changes in the DNA. Every change is a change of some nucleotide, for example, the following change can happen in DNA strand “AAGC”: the second nucleotide can change to “T” so that the resulting DNA strand is “ATGC”.
Scientists know that some segments of the DNA strand can be affected by some unknown infections. They can represent an infection as a sequence of nucleotides. Scientists are interested if there are any changes caused by some infections. Thus they sometimes want to know the value of impact of some infection to some segment of the DNA. This value is computed as follows:

  • Let the infection be represented as a string $e$, and let scientists be interested in DNA strand segment starting from position $l$ to position $r$, inclusive.
  • Prefix of the string $eee$… (i.e. the string that consists of infinitely many repeats of string $e$) is written under the string $s$ from position $l$ to position $r$, inclusive.
  • The value of impact is the number of positions where letter of string $s$ coincided with the letter written under it.

Being a developer, Innokenty is interested in bioinformatics also, so the scientists asked him for help. Innokenty is busy preparing VK Cup, so he decided to delegate the problem to the competitors. Help the scientists!

题意概述

给定一个只包含ATGC四种字符的字符串$s$。有两种操作:①修改$s$某一位的字符;②求以字符串$e$为循环节的无限长循环串与$s$中$[l, r]$这个区间的字符串有几个对应位置的字符相等。操作有$q$次。
数据范围:$1 \le |s|, q \le 10^5, \; 1 \le |e| \le 10$。

算法分析

由于$e$的长度最多是$10$,因此可以考虑在模$|e|$意义下的字符数。令$f_{i, j, k}$表示在模$i$意义下,模$i$余$j$的字符$k$个数的前缀和。这可以用树状数组维护。修改和查询时只需在对应的树状数组上进行操作。

代码

#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
struct binary_indexed_tree {
  int n;
  vector<int> a;
  void init(int t) { n = t + 10, a.clear(), a.resize(n); }
  void add(int p, int t) { for (int i = p; i < n; i += i & -i) a[i] += t; }
  int sum(int p) {
    int ret = 0; if (p <= 0) return 0;
    for (int i = p; i; i -= i & -i) ret += a[i];
    return ret;
  }
} tree[11][10][4];
int get_type(char c) {
  if (c == 'A') return 0;
  else if (c == 'T') return 1;
  else if (c == 'G') return 2;
  else if (c == 'C') return 3;
  return -1;
}
int n, c, l, r, len, oper, ans;
string s, t;
int main()
{
  cin >> s; len = s.length();
  for (int i = 0; i <= 10; ++i)
    for (int j = 0; j < 10; ++j)
      for (int k = 0; k < 4; ++k)
        tree[i][j][k].init(len);
  for (int i = 0; i < len; ++i)
    for (int j = 1; j <= 10; ++j)
      tree[j][(i + 1) % j][get_type(s[i])].add(i + 1, 1);
  scanf("%d", &n);
  while (n--) {
    scanf("%d", &oper);
    if (oper == 1) {
      scanf("%d", &c); cin >> t;
      for (int i = 1; i <= 10; ++i) {
        tree[i][c % i][get_type(s[c - 1])].add(c, -1);
        tree[i][c % i][get_type(t[0])].add(c, 1);
      }
      s[c - 1] = t[0];
    } else {
      scanf("%d%d", &l, &r); cin >> t;
      len = t.length(), ans = 0;
      for (int i = 0; i < len; ++i) {
        ans += tree[len][(l + i) % len][get_type(t[i])].sum(r) - tree[len][(l + i) % len][get_type(t[i])].sum(l - 1);
      }
      printf("%d\n", ans);
    }
  }
  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;
}

Query on the Subtree

题目描述

Bobo has a tree, whose vertices are conveniently labeled by $1, 2, \ldots, n$. At the very begining, the $i$-th vertex is assigned with weight $w_i$.
There are $q$ operations. Each operations are of the following $2$ types:

  • change the weight of vertex $v$ into $x$ (denoted as “! $v$ $x$”),
  • ask the total weight of vertices whose distance are no more than $d$ away from vertex $v$ (denoted as “? $v$ $d$”).

Note that the distance between vertex $u$ and $v$ is the number of edges on the shortest path between them.

题意概述

给定一棵有$n$个节点的树,第$i$个节点的权值为$w_i$。有两种操作:①将节点$v$的权值变成$x$;②询问与节点$v$的距离不超过$d$的所有节点的权值和。共有$q$次操作。
数据范围:$1 \le n, q \le 10^5, \; 0 \le w_i \le 10^4, \; 0 \le x \le 10^4, \; 0 \le d \le n$。

算法分析

对于我们枚举的某一个重心$x$,从它子树的重心向它连一条“虚”边,这样就形成了一棵由重心相连构成的“重心树”。由重心的性质可得,这棵树最多只有$O(\log n)$层。
A Weight Tree
如图,黑色表示原树上的边,红色表示重心树上的“虚”边。
对于每个节点,我们用树状数组存下它在“重心树”上的子树节点到它的距离为$p$(在原树上的距离)的权值和。当我们询问到节点$v$的距离不超过$d$的节点的权值和时,答案就等于$v$的树状数组中$d$的前缀和,再加上“重心树”上$v$的祖先节点$u$的树状数组中$d-dist_{u, v}$的前缀和。可以发现,$u$在“重心树”上包含$v$的子树中的节点被重复计算了。
如图,在计算到节点$3$的距离不超过$3$的节点的权值和时,计算了节点$3$子树中的节点$1, 3, 6, 8$;在计算到节点$3$的祖先节点$2$的距离不超过$3-2=1$的节点的权值和时,节点$1$又被计算了一次。
根据容斥原理,只需对每个节点再用一个树状数组记录下它在“重心树”上的子树节点到它在“重心树”上的父节点的距离为$p$(在原树上的距离)的权值和,每次计算时减去这个树状数组中$d-dist_{u, v}$的前缀和,就得到了正确答案。
修改节点$v$的权值时,只需更新“重心树”上$v$所有祖先节点的树状数组即可。
树上两点间的距离可以通过倍增求LCA得到,不过有更简便的方法。由于每个节点只会被$O(\log n)$个重心搜到,因此可以存下每个节点到其所有祖先重心节点的距离。
在“重心树”上操作的时间复杂度为$O(\log n)$,树状数组的时间复杂度为$O(\log n)$,总时间复杂度为$O(q\log^2n)$。
“重心树”上每一层节点的树状数组空间复杂度为$O(n)$,有$O(\log n)$层,每个节点上要存$O(\log n)$个距离,总空间复杂度为$O(n\log n)$。

代码

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
struct edge {
    int v, nxt;
} e[200001];
struct binary_indexed_tree {
    int n;
    vector<int> a;
    void init(int size) { n = size + 10, a.clear(), a.resize(n); }
    void add(int p, int t) {
        if (p) for (int i = p; i < n; i += i & -i) a[i] += t;
    }
    int sum(int p) {
        if (p <= 0) return 0;
        int ret = 0;
        for (int i = min(p, n - 1); i; i -= i & -i) ret += a[i];
        return ret;
    }
} tree[200001];
int n, q, nume, tot, top, root, h[100001], w[100001];
int size[100001], f[100001], up[100001], id[100001][2];
bool vis[100001];
vector<int> dist[100001];
void add_edge(int u, int v) {
    e[++nume].v = v, e[nume].nxt = h[u], h[u] = nume;
    e[++nume].v = u, e[nume].nxt = h[v], h[v] = nume;
}
void get_root(int t, int fa) {
    size[t] = 1, f[t] = 0;
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v] && e[i].v != fa) {
            get_root(e[i].v, t);
            size[t] += size[e[i].v], f[t] = max(f[t], size[e[i].v]);
        }
    }
    f[t] = max(f[t], tot - size[t]);
    if (f[t] < f[root]) root = t;
}
void get_dist(int t, int fa, int depth, int flag) {
    if (flag) dist[t].push_back(depth);
    else {
        tree[id[root][0]].add(depth, w[t]);
        if (dist[t].size() > 1) tree[id[root][1]].add(dist[t][dist[t].size() - 2], w[t]);
    }
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v] && e[i].v != fa) get_dist(e[i].v, t, depth + 1, flag);
    }
}
void solve(int t) {
    vis[t] = true;
    for (int i = h[t]; i; i = e[i].nxt) if (!vis[e[i].v]) get_dist(e[i].v, t, 1, 0);
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v]) {
            root = 0, tot = size[e[i].v], get_root(e[i].v, t), up[root] = t;
            tree[id[root][0] = ++top].init(size[e[i].v]);
            tree[id[root][1] = ++top].init(size[e[i].v]);
            tree[id[root][1]].add(dist[root][dist[root].size() - 1], w[root]);
            get_dist(root, 0, 0, 1);
            solve(root);
        }
    }
}
void modify(int t, int d) {
    int p = t, top = dist[t].size() - 1;
    while (p) {
        if (top >= 0) tree[id[p][0]].add(dist[t][top], d);
        if (top > 0) tree[id[p][1]].add(dist[t][top - 1], d);
        p = up[p], --top;
    }
}
int ask(int t, int d) {
    int p = t, ret = 0, top = dist[t].size() - 1;
    while (p) {
        int len;
        if (top >= 0) len = d - dist[t][top];
        if (top >= 0 && len >= 0) ret += tree[id[p][0]].sum(len) + w[p];
        if (top > 0) len = d - dist[t][top - 1];
        if (top > 0 && len >= 0 && up[p]) ret -= tree[id[p][1]].sum(len);
        p = up[p], --top;
    }
    return ret;
}
int main()
{
    while (scanf("%d%d", &n, &q) != EOF) {
        nume = top = 0;
        memset(up, 0, sizeof(up));
        memset(h, 0, sizeof(h));
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &w[i]);
            dist[i].clear();
        }
        for (int i = 1; i < n; ++i) {
            int u, v;
            scanf("%d%d", &u, &v), add_edge(u, v);
        }
        root = 0, tot = f[0] = n, get_root(1, 0);
        tree[id[root][0] = ++top].init(size[1]);
        tree[id[root][1] = ++top].init(size[1]);
        get_dist(root, 0, 0, 1);
        solve(root);
        while (q--) {
            char oper = ' ';
            while (oper != '!' && oper != '?') scanf("%c", &oper);
            int v, d;
            scanf("%d%d", &v, &d);
            if (oper == '!') modify(v, d - w[v]), w[v] = d;
            else printf("%d\n", ask(v, d));
        }
    }
    return 0;
}