CS101 2021Fall PA3,4 problem solution

PA3

The title description of PA3 is really the most unspeakable of the four Pa. at the beginning, both Title 1 and Title 2 are conditionally missing. In particular, the description of Title 2 is very unclear, there is no example explanation, and there is no accurate and rigorous definition of what scheme is essentially different, If you don't guess the method according to the tag, but analyze the problem itself, you really can't do it. The special input method of question 3 is not explained very clearly.

3001

Give me one n n n nodes m m Undirected graph with m edges G = ( V , E ) G=(V,E) G=(V,E), please select V V A subset of V U U U. If the nodes at both ends of an edge are U U U, then the stability of this edge is 1 1 1； If there is exactly one node at both ends of an edge U U U, then the stability of this edge is − 1 -1 −1； The stability of other edges is 0 0 0 In addition, U U The stability of each node in U is − 1 -1 − 1, not in U U The node stability in U is 0 0 0 Now determine a subset U U The selection scheme of U maximizes the sum of the stability of the whole graph, as long as the maximum stability is output. be careful, U = ∅ U=\varnothing U = ∅ is also a scheme, and its stability is 0 0 0.

It can be proved that if you want to select several nodes in each connected block, it will not be worse to select all nodes of the whole connected block. Therefore, the answer is the sum of the answers of each connected block, where, in a connected block G ′ = ( V ′ , E ′ ) G^\prime=(V^\prime,E^\prime) G ′ = (V ′, E ′), select all nodes V ′ V^\prime The stability obtained by V 'is ∣ E ′ ∣ − ∣ V ′ ∣ |E^\prime|-|V^\prime| ∣ E ′∣ − ∣ V ′∣, so only the number of points and edges of each connected block are required, and then max ⁡ { ∣ E ′ ∣ − ∣ V ′ ∣ , 0 } \max\{|E^\prime|-|V^\prime|,0\} max {∣ E ′∣ − ∣ V ′∣, 0} can be included in the answer.

Thinking of this, there are many ways. The number of points can be obtained by a simple dfs or bfs, and the number of edges satisfies a conclusion
2 ∣ E ′ ∣ = ∑ v ∈ V ′ deg ⁡ v , 2|E^\prime|=\sum_{v\in V^\prime}\deg v, 2∣E′∣=v∈V′∑​degv,
So you can count the degree of each point in dfs or bfs (the degree of each point can be calculated when entering). Of course, you can also mark which connected block each point belongs to during dfs or bfs, and then traverse all the edges to calculate how many edges each connected block has. In addition, this problem can also be done with disjoint set. We record the sum of points and degrees in each connected block on the tree root of the joint set, and then traverse the joint set to count the answers.

I would like to mention a point about merging sets: the class talked about a strategy of merging according to height. In fact, there is also a so-called "heuristic merging", which can also ensure that the tree height is zero without path compression O ( log ⁡ n ) O(\log n) O(logn). This strategy is to record the size of each tree on its root s i z e ( x ) size(x) size(x), that is, the number of nodes included; When merging two trees x x x and y y When y is the root of the tree, the s i z e size The smaller one doesn't come s i z e size The bigger one.

int fa[maxn], size[maxn];
int findfa(int x) {
  return x == fa[x] ? x : (fa[x] = findfa(fa[x]));
}
inline void union_set(int x, int y) {
  x = findfa(x);
  y = findfa(y);
  if (x == y)
    return;
  if (size[x] < size[y]) {
    fa[x] = y;
    size[y] += size[x];
  } else {
    fa[y] = x;
    size[x] += size[y];
  }
}

The correctness of this is to consider any node x x Distance from x to the root of the tree where it is located d e p t h ( x ) depth(x) depth(x), this distance will increase 1 1 If and only if this tree is merged into another larger tree, it means that the tree in which it is located s i z e size At least double the size. And there are only n n n, so this process occurs at most log ⁡ 2 n \log_2n Log 2 n times, so the tree height is O ( log ⁡ n ) O(\log n) O(logn). Of course, with path compression, it will fly fast.

3002

Give an undirected connected graph, each point has a point weight, define that the edge weight of each edge is equal to the point weight sum of the nodes at both ends, and find the maximum spanning tree and (non strict) sub large spanning tree. n ⩽ 1000 , m ⩽ 100000 n\leqslant 1000,m\leqslant 100000 n ⩽ 1000,m ⩽ 100000, point weight ∈ ( 0 , 50000 ) \in(0,50000) ∈ (050000) is an integer.

The meaning of this question is guessed according to the tag and the knowledge learned, because the title description itself doesn't make it clear what kind of scheme is essentially different. Later, piazza had a direct showdown with TA, saying that "different strategies refer to different edge sets that can span the whole graph".

At first, I didn't say that the point weight was an integer. As a result, a large group of people used float as a floating point number. Here is a reminder: in most cases, the accuracy of float is not enough. In case of floating point numbers, double is preferred. And you don't have to worry about whether higher accuracy leads to slower computing speed. If you have any questions, please read "Advice: Deciding which Type to Use" in Section 1, Chapter 2, the fifth edition of C++ Primer.

First find a maximum spanning tree. Just use Kruskal or Prim algorithm. Of course, Kruskal is generally preferred because Prim you have to write heap optimization. Kruskal's time complexity is mainly in sorting, and the time complexity after sorting is O ( m α ( n ) ) O(m\alpha(n)) O(m α (n)). After finding the largest spanning tree, we usually have the following two methods to require the next largest spanning tree:

Algorithm 1: consider deleting an edge on the tree

We can enumerate each edge on the maximum spanning tree, consider deleting this edge from the graph, and then find the maximum spanning tree again. Because the edge of the tree is only n − 1 n-1 n − 1, and after deleting an edge, you don't need to reorder the edges, just skip this edge, so the time complexity is O ( n m α ( n ) ) O(nm\alpha(n)) O(nm α (n)). This topic n ⩽ 1000 , m ⩽ 100000 n\leqslant 1000,m\leqslant 100000 n ⩽ 1000,m ⩽ 100000. This time complexity can be passed. Note that deleting an edge may cause the graph to be disconnected, and your maximum spanning tree will not be found n − 1 n-1 n − 1 edge, which should be skipped.

#include <algorithm>
#include <cctype>
#include <climits>
#include <cstdio>
#include <functional>
#include <iterator>

template <typename T>
inline void read(T &x) {
  int f = 0, c = getchar();
  x = 0;
  while (!isdigit(c)) {
    f |= c == '-';
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - 48;
    c = getchar();
  }
  if (f)
    x = -x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &...args) {
  read(x);
  read(args...);
}

namespace gkxx {

template <typename ForwardIterator, typename Less>
void __merge(
    ForwardIterator begin, ForwardIterator mid, ForwardIterator end,
    typename std::iterator_traits<ForwardIterator>::difference_type dist,
    Less less) {
  ForwardIterator i = begin, j = mid;
  using value_type = typename std::iterator_traits<ForwardIterator>::value_type;
  value_type *tmp = new value_type[dist](), *k = tmp;
  while (i != mid && j != end) {
    if (less(*i, *j))
      *k++ = *i++;
    else
      *k++ = *j++;
  }
  while (i != mid)
    *k++ = *i++;
  while (j != end)
    *k++ = *j++;
  k = tmp;
  while (begin != end)
    *begin++ = *k++;
  delete[] tmp;
}

template <typename ForwardIterator, typename Less>
void merge_sort(ForwardIterator begin, ForwardIterator end, Less less) {
  auto dist = std::distance(begin, end);
  if (dist <= 1)
    return;
  ForwardIterator mid = std::next(begin, dist / 2);
  merge_sort(begin, mid, less);
  merge_sort(mid, end, less);
  __merge(begin, mid, end, dist, less);
}

template <typename ForwardIterator>
inline void merge_sort(ForwardIterator begin, ForwardIterator end) {
  merge_sort(begin, end, std::less<void>());
}

} // namespace gkxx

constexpr int maxn = 1e3 + 7, maxm = 1e5 + 7;

struct Edge {
  int from, to, len;
  Edge() : from(0), to(0), len(0) {}
};
int chosen[maxn], tot;
Edge edges[maxm];
int fa[maxn], size[maxn], val[maxn];
int n, m;

inline void set_init() {
  for (int i = 1; i <= n; ++i) {
    fa[i] = i;
    size[i] = 1;
  }
}
int findf(int x) {
  return fa[x] == x ? x : (fa[x] = findf(fa[x]));
}
inline void union_set(int x, int y) {
  int fx = findf(x), fy = findf(y);
  if (fx == fy)
    return;
  if (size[fx] < size[fy]) {
    size[fy] += size[fx];
    fa[fx] = fy;
  } else {
    size[fx] += size[fy];
    fa[fy] = fx;
  }
}

int kruskal(int del = -1) {
  set_init();
  int ans = 0, cnt = 0;
  for (int i = 1; i <= m; ++i)
    if (i != del) {
      int u = edges[i].from, v = edges[i].to, w = edges[i].len;
      int fu = findf(u), fv = findf(v);
      if (fu != fv) {
        ans += w;
        if (del == -1)
          chosen[++tot] = i;
        union_set(fu, fv);
        if (++cnt == n - 1)
          break;
      }
    }
  return cnt == n - 1 ? ans : -1;
}

int main() {
  read(n, m);
  for (int i = 1; i <= n; ++i)
    read(val[i]);
  for (int i = 1; i <= m; ++i) {
    read(edges[i].from, edges[i].to);
    edges[i].len = val[edges[i].from] + val[edges[i].to];
  }
  gkxx::merge_sort(
      edges + 1, edges + m + 1,
      [](const Edge &a, const Edge &b) -> bool { return a.len > b.len; });
  int best = kruskal();
  int second = 0;
  for (int i = 1; i <= tot; ++i) {
    second = std::max(second, kruskal(chosen[i]));
    if (second == best)
      break;
  }
  printf("%.1lf\n", (best + second) / 2.0);
  return 0;
}

Algorithm 2: enumerate the edges that are not on the tree, and consider replacing the edges on the tree

Enumerate each edge that is not on the maximum spanning tree ( u , v ) (u,v) (u,v), if we add this edge to the maximum spanning tree, it will obviously form a ring. We have to be on the maximum spanning tree u u u to v v Find an edge on the path of v and delete it. Obviously, we should find the edge with the least edge weight. We can spend O ( n ) O(n) O(n) do dfs or bfs on the tree to find u u u to v v What is the minimum edge weight on the path of v. There are a total of edges not on the maximum spanning tree m − ( n − 1 ) m-(n-1) m − (n − 1), so the total time complexity is O ( n m ) O(nm) O(nm), can be passed.

Can this algorithm be optimized? be aware n ⩽ 1000 n\leqslant 1000 n ⩽ 1000, we can remember f ( x , y ) f(x, y) f(x,y) represents the node on the tree x x x and y y The minimum value of the edge weight on the path between y is done at the beginning n n n times dfs or bfs, flower O ( n 2 ) O(n^2) O(n2) time preprocesses the entire two-dimensional array f f f. In this way, the time complexity of a single query is O ( 1 ) O(1) O(1), the complexity of the whole algorithm is O ( n 2 + m ) = O ( n 2 ) O(n^2+m)=O(n^2) O(n2+m)=O(n2).

But in the competition, the data range of a problem like this is not so kind, and it is usually given n ⩽ 100000 n\leqslant 100000 n ⩽ 100000 instead of 1000 1000 1000. In fact, there are many ways to quickly preprocess and query the minimum edge weight of a path in the tree, which can be achieved by using multiplication, link cut tree or tree chain partition + ST table O ( n log ⁡ n ) O(n\log n) O(nlogn) pretreatment O ( log ⁡ n ) O(\log n) O(logn) single query, or tree chain segmentation + line segment tree O ( n ) O(n) O(n) pretreatment O ( log ⁡ 2 n ) O(\log^2n) O(log2n) single query. There are many methods. Interested students can see it This question.

#include <algorithm>
#include <climits>
#include <cstdio>
#include <functional>
#include <iterator>

namespace gkxx {

template <typename ForwardIterator, typename Less>
void __inplace_merge(
    ForwardIterator begin, ForwardIterator mid, ForwardIterator end,
    typename std::iterator_traits<ForwardIterator>::difference_type dist,
    Less less) {
  ForwardIterator i = begin, j = mid;
  using value_type = typename std::iterator_traits<ForwardIterator>::value_type;
  value_type *tmp = new value_type[dist](), *k = tmp;
  while (i != mid && j != end) {
    if (less(*i, *j))
      *k++ = *i++;
    else
      *k++ = *j++;
  }
  while (i != mid)
    *k++ = *i++;
  while (j != end)
    *k++ = *j++;
  k = tmp;
  while (begin != end)
    *begin++ = *k++;
  delete[] tmp;
}

template <typename ForwardIterator, typename Less>
void merge_sort(ForwardIterator begin, ForwardIterator end, Less less) {
  auto dist = std::distance(begin, end);
  if (dist <= 1)
    return;
  ForwardIterator mid = std::next(begin, dist / 2);
  merge_sort(begin, mid, less);
  merge_sort(mid, end, less);
  __inplace_merge(begin, mid, end, dist, less);
}

template <typename ForwardIterator>
inline void merge_sort(ForwardIterator begin, ForwardIterator end) {
  merge_sort(begin, end, std::less<void>());
}

} // namespace gkxx

constexpr int maxn = 1007, maxm = 1e5 + 7;

struct Edge {
  int from, to, weight;
};

Edge edges[maxm];
bool use[maxm];
int n, m;
int firmness[maxn];

int fa[maxn], size[maxn];

int findfa(int x) {
  return fa[x] == x ? x : (fa[x] = findfa(fa[x]));
}
inline void union_set(int x, int y) {
  x = fa[x];
  y = fa[y];
  if (x == y)
    return;
  if (size[x] < size[y]) {
    fa[x] = y;
    size[y] += size[x];
  } else {
    fa[y] = x;
    size[x] += size[y];
  }
}

struct Node {
  int to, wei;
  int next;
};
Node T[maxn * 2];
int total;
int head[maxn];

inline void add_edge(int x, int y, int w) {
  T[++total].to = y;
  T[total].wei = w;
  T[total].next = head[x];
  head[x] = total;
}

int kruskal() {
  gkxx::merge_sort(edges + 1, edges + m + 1,
                   [](const Edge &lhs, const Edge &rhs) -> bool {
                     return lhs.weight > rhs.weight;
                   });
  for (int i = 1; i <= n; ++i)
    fa[i] = i;
  int best = 0;
  for (int i = 1; i <= m; ++i) {
    int x = edges[i].from, y = edges[i].to, w = edges[i].weight;
    if (findfa(x) != findfa(y)) {
      union_set(x, y);
      best += w;
      add_edge(x, y, w);
      add_edge(y, x, w);
      use[i] = true;
    }
  }
  return best;
}

int f[maxn][maxn];

void dfs(int x, int fa, int s) {
  for (int i = head[x]; i; i = T[i].next) {
    int v = T[i].to, w = T[i].wei;
    if (v != fa) {
      f[s][v] = std::min(f[s][x], w);
      dfs(v, x, s);
    }
  }
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i)
    scanf("%d", firmness + i);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &edges[i].from, &edges[i].to);
    edges[i].weight = firmness[edges[i].from] + firmness[edges[i].to];
  }
  int best = kruskal();
  for (int i = 1; i <= n; ++i) {
    f[i][i] = INT_MAX;
    dfs(i, 0, i);
  }
  int second = 0;
  for (int i = 1; i <= m; ++i)
    if (!use[i]) {
      int cur = best + edges[i].weight - f[edges[i].from][edges[i].to];
      if (cur > second)
        second = cur;
    }
  printf("%.1lf\n", (best + second) / 2.0);
  return 0;
}

Briefly mention the ideas of several other practices. As mentioned earlier, the ST table can solve the interval maximum query (or similar problems, such as previous intervals) on a sequence gcd ⁡ \gcd gcd query) problem, can do O ( 1 ) O(1) O(1). Now, facing the problem of path maximum query on the tree, we have an algorithm called "light chain segmentation", which can divide the tree into several chains and transform a path query into O ( log ⁡ n ) O(\log n) O(logn) sub chain query, and the chain can be regarded as an interval, then it can be processed with ST table. If the st table is changed into a segment tree, the time complexity of preprocessing can be changed from O ( n log ⁡ n ) O(n\log n) O(nlogn) is reduced to O ( n ) O(n) O(n), but the time complexity of a single query becomes O ( log ⁡ 2 n ) O(\log^2n) O(log2n), because the query on the segment tree itself is O ( log ⁡ n ) O(\log n) O(logn).

However, the division of heavy chain is a little overqualified here, and it is also troublesome to write. Here is a more noteworthy idea called "multiplication", which is similar to ST table. We set f a ( x , i ) fa(x,i) fa(x,i) indicates from x x x jump up 2 i 2^i 2i the node to which an edge can jump, which is similar to a dynamic programming, we can transfer as follows:
f a ( x , i ) = f a ( f a ( x , i − 1 ) , i − 1 ) , fa(x,i)=fa(fa(x,i-1),i-1), fa(x,i)=fa(fa(x,i−1),i−1),
That is, start with x x x jump up 2 i − 1 2^{i-1} 2i − 1 side, and then continue to jump 2 i − 1 2^{i-1} 2i − 1 side. be careful, i i The value of i is only log ⁡ 2 n \log_2n log2 n species, because the tree height cannot exceed n n n. In this way, we can use dfs once O ( n log ⁡ n ) O(n\log n) O(nlogn) preprocesses all f a fa fa value. On this basis, make m n ( x , i ) mn(x,i) mn(x,i) indicates from x x x starts to go up 2 i 2^i What is the minimum value of edge weight in 2i edges? Similarly, there is the following transfer
m n ( x , i ) = min ⁡ { m n ( x , i − 1 ) , m n ( f a ( x , i − 1 ) , i − 1 ) } . mn(x,i)=\min\{mn(x,i-1),mn(fa(x,i-1),i-1)\}. mn(x,i)=min{mn(x,i−1),mn(fa(x,i−1),i−1)}.
It can be calculated f a fa fa is calculated at the same time. Now suppose we want to query from u u u to v v Minimum path edge weight of v, assuming x x The depth of x is large. Let's start with x x x starts jumping to and y y y is at the same depth, but not step by step. We know d e p t h ( x ) − d e p t h ( y ) depth(x)-depth(y) The number depth(x) − depth(y) has a unique binary representation. If the number is represented in binary, it is the second i i Bit i is 1 1 1 (second from low to high) 0 , 1 , ⋯ 0,1,\cdots 0,1,...), we jump up 2 i 2^i Step 2i. In this way, you can jump at most log ⁡ 2 n \log_2n log2 # n steps can jump to and y y y is equal in depth, because the binary digits of this number are at most log ⁡ 2 n \log_2n log2​n. Jump to x x x and y y y wait for depth, and then continue to jump up from the two positions, which can be enumerated from large to small i i i. As long as f a ( x , i ) ≠ f a ( y , i ) fa(x,i)\neq fa(y,i) fa(x,i)  = fa(y,i) means jump up 2 i 2^i 2i can jump up until two points meet without meeting each other. This point is called the nearest common ancestor (LCA). In the above process, the answer is counted while jumping, which reduces the time complexity O ( log ⁡ n ) O(\log n) O(logn).

#include <algorithm>
#include <climits>
#include <cstdio>
#include <functional>
#include <iterator>

namespace gkxx {

template <typename ForwardIterator, typename Less>
void __inplace_merge(
    ForwardIterator begin, ForwardIterator mid, ForwardIterator end,
    typename std::iterator_traits<ForwardIterator>::difference_type dist,
    Less less) {
  ForwardIterator i = begin, j = mid;
  using value_type = typename std::iterator_traits<ForwardIterator>::value_type;
  value_type *tmp = new value_type[dist](), *k = tmp;
  while (i != mid && j != end) {
    if (less(*i, *j))
      *k++ = *i++;
    else
      *k++ = *j++;
  }
  while (i != mid)
    *k++ = *i++;
  while (j != end)
    *k++ = *j++;
  k = tmp;
  while (begin != end)
    *begin++ = *k++;
  delete[] tmp;
}

template <typename ForwardIterator, typename Less>
void merge_sort(ForwardIterator begin, ForwardIterator end, Less less) {
  auto dist = std::distance(begin, end);
  if (dist <= 1)
    return;
  ForwardIterator mid = std::next(begin, dist / 2);
  merge_sort(begin, mid, less);
  merge_sort(mid, end, less);
  __inplace_merge(begin, mid, end, dist, less);
}

template <typename ForwardIterator>
inline void merge_sort(ForwardIterator begin, ForwardIterator end) {
  merge_sort(begin, end, std::less<void>());
}

} // namespace gkxx

constexpr int maxn = 1007, maxm = 1e5 + 7;

struct Edge {
  int from, to, weight;
};

Edge edges[maxm];
bool use[maxm];
int n, m;
int firmness[maxn];

int par[maxn], size[maxn];

int findfa(int x) {
  return par[x] == x ? x : (par[x] = findfa(par[x]));
}
inline void union_set(int x, int y) {
  x = par[x];
  y = par[y];
  if (x == y)
    return;
  if (size[x] < size[y]) {
    par[x] = y;
    size[y] += size[x];
  } else {
    par[y] = x;
    size[x] += size[y];
  }
}

struct Node {
  int to, wei;
  int next;
};
Node T[maxn * 2];
int total;
int head[maxn];

inline void add_edge(int x, int y, int w) {
  T[++total].to = y;
  T[total].wei = w;
  T[total].next = head[x];
  head[x] = total;
}

int kruskal() {
  gkxx::merge_sort(edges + 1, edges + m + 1,
                   [](const Edge &lhs, const Edge &rhs) -> bool {
                     return lhs.weight > rhs.weight;
                   });
  for (int i = 1; i <= n; ++i)
    par[i] = i;
  int best = 0;
  for (int i = 1; i <= m; ++i) {
    int x = edges[i].from, y = edges[i].to, w = edges[i].weight;
    if (findfa(x) != findfa(y)) {
      union_set(x, y);
      best += w;
      add_edge(x, y, w);
      add_edge(y, x, w);
      use[i] = true;
    }
  }
  return best;
}

int fa[maxn][22], mn[maxn][22], dep[maxn];

void dfs(int x) {
  dep[x] = dep[fa[x][0]] + 1;
  for (int i = 1; i <= 20; ++i) {
    fa[x][i] = fa[fa[x][i - 1]][i - 1];
    mn[x][i] = std::min(mn[x][i - 1], mn[fa[x][i - 1]][i - 1]);
  }
  for (int i = head[x]; i; i = T[i].next) {
    int v = T[i].to, w = T[i].wei;
    if (v != fa[x][0]) {
      fa[v][0] = x;
      mn[v][0] = w;
      dfs(v);
    }
  }
}

int query(int x, int y) {
  int ans = INT_MAX;
  if (dep[x] < dep[y])
    std::swap(x, y);
  // Jump to the same depth first
  for (int i = 20; i >= 0; --i)
    if (dep[fa[x][i]] >= dep[y]) {
      if (mn[x][i] < ans)
        ans = mn[x][i];
      x = fa[x][i];
    }
  if (x == y)
    return ans;
  // Jump up again
  for (int i = 20; i >= 0; --i)
    if (fa[x][i] != fa[y][i]) {
      if (mn[x][i] < ans)
        ans = mn[x][i];
      if (mn[y][i] < ans)
        ans = mn[y][i];
      x = fa[x][i];
      y = fa[y][i];
    }
  return std::min({ans, mn[x][0], mn[y][0]});
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i)
    scanf("%d", firmness + i);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &edges[i].from, &edges[i].to);
    edges[i].weight = firmness[edges[i].from] + firmness[edges[i].to];
  }
  int best = kruskal();
  dfs(1);
  int second = 0;
  for (int i = 1; i <= m; ++i)
    if (!use[i]) {
      int cur = best + edges[i].weight - query(edges[i].from, edges[i].to);
      if (cur > second)
        second = cur;
    }
  printf("%.1lf\n", (best + second) / 2.0);
  return 0;
}

What? You asked me link cut tree? It's better for you to ask Hu Jintian, because our link cut tree is learned from his blog orzzz

3003

Maintaining a collection supports:

• Insert a number
• Delete a number
• Query the ranking of a number
• Query page k k Small value of k

First explain the input method of this question: in order to test the efficiency of everyone's data structure implementation, this question cards the data scale to the extreme 1 0 6 10^6 106, and slightly increased the time limit. In this case, the input time may not be negligible. In order to prevent input from consuming a lot of time, this question is not to input the test data, but to give you the data generator and its calling method. What is input is the parameters of the data generator. Finally, in order to avoid wasting a lot of time on output, the output is the result of combining the answers xor of each query.

This is a template question. There are two main methods: balanced tree school and unbalanced tree school. Because there are too many practices, this solution focuses on broadening everyone's vision, and the code implementation is symbolically given to two. If you want to further learn, please move on The problem of Luogu Problem solving area.

Balanced tree

AVL and Rb tree have been taught in the class. I don't know whether there are warriors who wrote RB tree. I personally feel that RB tree is basically the most difficult to write among several balance trees. Of course, its efficiency is also quite high. The ordered associative containers of STL, such as STD:: set and STD:: map, are implemented by RB tree. AVL is not difficult to write. The trouble you can think of is that it needs to be rotated many times when deleting. But in fact, the most used balance tree in the competition is neither AVL nor RB tree, but the following three: splay, tree and scapegoat.

Splay is based on rotation. Its idea is: after accessing a node (insert, query, etc.), it will be transferred to the root immediately, so it also has a "cache" effect. It can transfer any node to the root, which makes it very flexible and can support many powerful operations. But it does not guarantee that the height of the tree is always the same O ( log ⁡ n ) O(\log n) O(logn), whose time complexity analysis is relatively complex, is the so-called "equal sharing" O ( log ⁡ n ) O(\log n) O(logn)".

Tree = tree + heap. Its idea is to give each node an additional so-called "priority" (a randomly generated number) to make the priorities meet the heap nature, that is, the priority of the father is always greater than that of the child. When a node is inserted to destroy the nature of the heap, it is adjusted by rotation. This is an implementation based on rotation, but a giant named fan Haoqiang proposed a so-called "irrotational Treap", which is based on splitting and merging. It can be for any given number x x x. In O ( log ⁡ n ) O(\log n) Split the tree into two trees in the time of O(logn), and one tree is less than or equal to x x x. The other one is all bigger than x x x； Of course, it can also be split into a tree just ahead k k k small nodes, and the other tree contains the remaining nodes; It can also be in O ( log ⁡ n ) O(\log n) O(logn), merge two treaps into one, as long as all nodes of one tree are less than or equal to that of the other. In this way, other operations are very simple, such as inserting a number x x x. Just press first x x x splits into two trees and at the same time x x x is regarded as a tree with only one node, and the three trees can be merged.

Scapegoat, a scapegoat tree, is very violent: it has a way to measure the "balance" of a certain tree. If it is found that a certain tree is not balanced, it will directly flatten the sub tree to form a perfect balance tree.

In the implementation, some techniques are common. For example, how to deal with the situation that the same number is inserted multiple times? We can record the occurrence times on each node, and the repeated insertion will directly increase the corresponding occurrence times without creating a new node. When deleting a node, the number of occurrences decreases. If it decreases to zero, it decreases to zero. What does it matter? No, the number of occurrences is 0 0 0, in fact, there is no need to delete it at all, because we know that deleting a node on AVL is more troublesome and needs to be rotated many times. If you leave it there, the order of magnitude of the number of nodes in the whole tree remains the same, and there will be little difference in efficiency. Calculate ranking or k k Be careful when k is small. You have to calculate the sum of "occurrences" of a certain tree, not the number of nodes.

If you have written a function to check the ranking, how to check it k k What about the small value of k? One way to be lazy is to dichotomy directly: I guess k k The small value of k is a certain number, and then check the ranking of this number to decide whether I guess big or small. The time complexity of this algorithm is O ( log ⁡ n log ⁡ A ) O(\log n\log A) O(lognlogA), where A A A is the maximum value of the range. Of course, the normal way is to go down from the root node on the balance tree and look at the sum of "occurrences" of the left subtree and k k The size relationship of k k k Is the small value of k on the left or right.

Put a code for non rotating Treap:

#include <iostream>
#include <tuple>

constexpr int maxn = 1e6 + 7;

struct Treap {
  int ch[maxn][2], sz[maxn], val[maxn], pri[maxn];
  int total, root;
  int newNode(int v = 0) {
    int x = ++total;
    val[x] = v;
    sz[x] = 1;
    pri[x] = rand();
    ch[x][0] = ch[x][1] = 0;
    return x;
  }
  void update(int x) {
    sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
  }
  void split(int x, int v, int &l, int &r) {
    if (!x) {
      l = r = 0;
    } else {
      if (val[x] <= v) {
        l = x;
        split(ch[x][1], v, ch[x][1], r);
      } else {
        r = x;
        split(ch[x][0], v, l, ch[x][0]);
      }
      update(x);
    }
  }
  int merge(int x, int y) {
    if (x == 0 || y == 0)
      return x + y;
    if (pri[x] < pri[y]) {
      ch[y][0] = merge(x, ch[y][0]);
      update(y);
      return y;
    } else {
      ch[x][1] = merge(ch[x][1], y);
      update(x);
      return x;
    }
  }
  void insert(int v) {
    int x, y;
    split(root, v, x, y);
    root = merge(merge(x, newNode(v)), y);
  }
  void remove(int v) {
    int x, y, z;
    split(root, v - 1, x, z);
    split(z, v, y, z);
    y = merge(ch[y][0], ch[y][1]);
    root = merge(merge(x, y), z);
  }
  int rank(int v) {
    int x, y;
    split(root, v - 1, x, y);
    int res = sz[x];
    root = merge(x, y);
    return res;
  }
  int kth(int k) {
    ++k;
    int x = root;
    while (sz[ch[x][0]] + 1 != k) {
      if (k <= sz[ch[x][0]])
        x = ch[x][0];
      else
        k -= sz[ch[x][0]] + 1, x = ch[x][1];
    }
    return val[x];
  }
  int size() {
    return sz[root];
  }
};

int A, B, C, lfsr;
double P[4][4];
int lfsr_generator() {
  auto ret = lfsr;
  return (lfsr ^= lfsr << 13, lfsr ^= lfsr >> 17, lfsr ^= lfsr << 5, ret);
}
std::tuple<int, int> command() {
  auto imm = lfsr_generator();
  static int state = 0;
  auto p = double(lfsr_generator() & 0x7fffffff) / INT32_MAX;
  for (int i = 0; i < 4; i++)
    if ((p -= P[state % 4][i]) < 0) {
      state += 4 - state % 4 + i;
      break;
    }
  return std::tuple<int, int>(state % 4,
                              (imm * A + state * B + C) & 0x7fffffff);
}

Treap t;

int main() {
  int m;
  std::ios::sync_with_stdio(false);
  std::cin >> m >> lfsr >> A >> B >> C;
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
      std::cin >> P[i][j];
  int tans = 0;
  for (int i = 1; i <= m; i++) {
    int op, imm;
    std::tie(op, imm) = command();
    if (op == 0)
      t.insert(imm);
    if (op == 1)
      t.remove(t.kth(imm % t.size()));
    if (op == 2)
      tans ^= t.rank(imm);
    if (op == 3)
      tans ^= t.kth(imm % t.size());
  }
  std::cout << tans << "\n";
  return 0;
}

Before introducing the unbalanced tree school, let's talk about online and offline. There are usually two approaches to this problem. One is to read all queries and operations first, which is equivalent to knowing in advance what to do next. At this time, you can do some preprocessing, and then officially start processing queries and operations. This algorithm is called "offline algorithm". The other is to answer a result immediately after reading a query, and do this operation immediately after reading an operation, which is called "online algorithm". Some questions will find ways to force online in order to increase the difficulty. For example, every query or operation entered will become a password, and the key parameter required for decryption is the answer of the last query.

But this problem is allowed to be offline, that is, we can know which numbers will be inserted in advance. What's the balance tree! Directly save and sort all the numbers that may be inserted, remove the duplicates, and then build a perfect binary search tree. At first, the "occurrence times" of all nodes are zero. You don't have to do anything. The tree height is always O ( log ⁡ m ) O(\log m) O(logm).

Nonequilibrium tree

There are three kinds of unbalanced trees: segment tree, tree array and 01 Trie. The Trie of 01 Trie is the Trie written by many people in pa1. The integer can be regarded as a character set in binary { 0 , 1 } \{0,1\} {0,1} string, then it can be maintained by Trie tree. However, it is essentially no different from the line segment tree, but the perspective is different. We won't talk more about it.

Both segment trees and tree arrays are based on the idea that all inserted numbers are [ 0 , N ] [0,N] Integer in [0,N]. order f ( x ) f(x) f(x) indicates x x How many times x appears in the set, x ∈ [ 0 , N ] ∩ Z x\in[0,N]\cap\Z x∈[0,N]∩Z. So insert x x x is increasing f ( x ) f(x) f(x), delete x x x is decreasing f ( x ) f(x) f(x), how many number ratios are queried x x Small x is summation ∑ i = 0 x − 1 f ( i ) \sum_{i=0}^{x-1}f(i) Σ i=0x − 1 − f(i), as for query k k The small value of k... I'll talk about it later. If it's a big deal, it can be solved by two points. Like this f f The problems of single point modification and interval summation on f sequence can be solved very directly by segment tree and tree array, but there is a problem here: N N N can be very large. Both line segment tree and tree array need to be implemented directly O ( N ) O(N) Space of O(N), if N N N yes 1 0 9 10^9 109 or INT_MAX doesn't work.

However, although N N N may be very large, but in fact, there must not be more useful than n m m m, that is, the distribution of these numbers in this range is sparse; In fact, we only pay attention to the relative size of these numbers, not how much it is. We can adopt an off-line method, first store all the numbers involved into an array tmp, sort and remove the duplicate elements. At this time, each number has a unique subscript in the tmp array 1 , 2 , ⋯   , n 1,2,\cdots,n 1,2,⋯,n. In this way, we have established from each original number to [ 1 , n ] ∩ Z [1,n]\cap\Z One to one mapping of [1,n] ∩ Z, and n ⩽ m ⩽ 1 0 6 n\leqslant m\leqslant 10^6 n ⩽ m ⩽ 106 is a small range. Suppose you want to insert a number now x x x. We find its subscript in the tmp array x ′ x^\prime x ', and then the actual increment is f ( x ′ ) f(x^\prime) f(x ') instead of f ( x ) f(x) f(x). This algorithm is called discretization. Note that the search subscript must be binary search. Don't traverse in sequence, otherwise it will be invalid O ( n ) O(n) O(n), your tree will be written in vain.

What I didn't say just now k k In fact, the problem of small value of k can be bisected directly on the line segment tree O ( log ⁡ n ) O(\log n) O(logn). I won't say more details.

The specific principle and implementation of line segment tree and tree array can be checked online by yourself, so I won't talk about it. Here is the code of a segment tree.

#include <algorithm>
#include <climits>
#include <iostream>
#include <tuple>

namespace gkxx {

template <typename ForwardIterator>
void __inplace_merge(
    ForwardIterator begin, ForwardIterator mid, ForwardIterator end,
    typename std::iterator_traits<ForwardIterator>::difference_type dist) {
  ForwardIterator i = begin, j = mid;
  using value_type = typename std::iterator_traits<ForwardIterator>::value_type;
  value_type *tmp = new value_type[dist](), *k = tmp;
  while (i != mid && j != end) {
    if (std::less<value_type>()(*i, *j))
      *k++ = *i++;
    else
      *k++ = *j++;
  }
  while (i != mid)
    *k++ = *i++;
  while (j != end)
    *k++ = *j++;
  k = tmp;
  while (begin != end)
    *begin++ = *k++;
  delete[] tmp;
}

template <typename ForwardIterator>
void merge_sort(ForwardIterator begin, ForwardIterator end) {
  auto dist = std::distance(begin, end);
  if (dist <= 1)
    return;
  ForwardIterator mid = std::next(begin, dist / 2);
  merge_sort(begin, mid);
  merge_sort(mid, end);
  __inplace_merge(begin, mid, end, dist);
}

template <typename ForwardIterator>
ForwardIterator unique(ForwardIterator begin, ForwardIterator end) {
  if (begin == end)
    return end;
  ForwardIterator result = begin;
  while (++begin != end) {
    if (!(*result == *begin) && ++result != begin) {
      *result = std::move_if_noexcept(*begin);
    }
  }
  return ++result;
}

template <typename RandomAccessIterator>
RandomAccessIterator lower_bound(
    RandomAccessIterator begin, RandomAccessIterator end,
    typename std::iterator_traits<RandomAccessIterator>::value_type const
        &value) {
  auto dist = std::distance(begin, end);
  while (dist > 1) {
    auto mid = begin + dist / 2;
    if (value < *mid)
      end = mid;
    else
      begin = mid;
    dist = std::distance(begin, end);
  }
  return begin;
}

} // namespace gkxx

constexpr int maxn = 1e6 + 7;

struct Command {
  int op, imm;
  explicit Command(int o = 0, int i = 0) : op(o), imm(i) {}
};
Command cmd[maxn];
int tmp[maxn], tot;
int sum[maxn << 1];
int all, M;

inline void build() {
  M = 1;
  while (M < all + 2)
    M <<= 1;
}
inline void add(int x, int val) {
  for (sum[x += M] += val, x >>= 1; x; x >>= 1)
    sum[x] += val;
}
inline int less_than(int x) {
  int ans = 0;
  for (int s = M, t = x + M; s ^ t ^ 1; s >>= 1, t >>= 1) {
    if (~s & 1)
      ans += sum[s ^ 1];
    if (t & 1)
      ans += sum[t ^ 1];
  }
  return ans;
}
inline int query_kth(int k) {
  int curr = 1;
  while (curr < M) {
    if (k <= sum[curr << 1])
      curr <<= 1;
    else {
      k -= sum[curr << 1];
      (curr <<= 1) |= 1;
    }
  }
  return curr - M;
}

inline void insert(int v) {
  v = gkxx::lower_bound(tmp + 1, tmp + all + 1, v) - tmp;
  add(v, 1);
}
inline void remove(int v) {
  v = gkxx::lower_bound(tmp + 1, tmp + all + 1, v) - tmp;
  add(v, -1);
}
inline int kth(int k) {
  return tmp[query_kth(k + 1)];
}
inline int rank(int v) {
  v = gkxx::lower_bound(tmp + 1, tmp + all + 1, v) - tmp;
  return less_than(v);
}
inline int size() {
  return sum[1];
}

int A, B, C, lfsr;
double P[4][4];
int lfsr_generator() {
  auto ret = lfsr;
  return (lfsr ^= lfsr << 13, lfsr ^= lfsr >> 17, lfsr ^= lfsr << 5, ret);
}
std::tuple<int, int> command() {
  auto imm = lfsr_generator();
  static int state = 0;
  auto p = double(lfsr_generator() & 0x7fffffff) / INT32_MAX;
  for (int i = 0; i < 4; i++)
    if ((p -= P[state % 4][i]) < 0) {
      state += 4 - state % 4 + i;
      break;
    }
  return std::tuple<int, int>(state % 4,
                              (imm * A + state * B + C) & 0x7fffffff);
}

int main() {
  int m;
  std::cin >> m >> lfsr >> A >> B >> C;
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
      std::cin >> P[i][j];
  int tans = 0;
  for (int i = 1; i <= m; i++) {
    int op, imm;
    std::tie(op, imm) = command();
    cmd[i].op = op;
    cmd[i].imm = imm;
    if (op == 0 || op == 2)
      tmp[++tot] = imm;
  }

  gkxx::merge_sort(tmp + 1, tmp + tot + 1);
  all = gkxx::unique(tmp + 1, tmp + tot + 1) - (tmp + 1);
  build();

  for (int i = 1; i <= m; ++i) {
    int op = cmd[i].op, imm = cmd[i].imm;
    if (op == 0)
      insert(imm);
    if (op == 1)
      remove(kth(imm % size()));
    if (op == 2)
      tans ^= rank(imm);
    if (op == 3)
      tans ^= kth(imm % size());
  }
  std::cout << tans << std::endl;
  return 0;
}

If you learn the line segment tree, you may still be confused when looking at this code, because this is a zkw line segment tree, which was invented by a giant named Zhang kunwei. Yes, it is the one who was sprayed with "pushin man" on Douban before. His line segment tree constant is small, runs fast and writes very short. Interested students can search his famous courseware the power of statistics. (in fact, you don't have to watch it if you don't play)

PA4

4001

There is a frog at a depth of n n n meters bottom, it needs to jump to a depth of 0 0 The ground of 0. If it's at a depth of i i Take off at i meters, and you can jump to a depth of j ∈ [ i − a i , i ] ∩ Z j\in[i-a_i,i]\cap\Z j ∈ [i − ai, i] ∩ Z meters, but then it will fall to a depth of j + b j j+b_j j+bj M. Ask at least how many steps you can jump to the ground. n ⩽ 3 × 1 0 5 n\leqslant 3\times 10^5 n⩽3 × 105. Guarantee 0 ⩽ a i ⩽ i , 0 ⩽ b i ⩽ n − i 0\leqslant a_i\leqslant i,0\leqslant b_i\leqslant n-i 0⩽ai​⩽i,0⩽bi​⩽n−i.

Algorithm 1: optimal drawing of line segment tree + shortest path

First of all, one of the most brainless ideas is to regard this process as a map and run the shortest path. Specifically, for each depth i i i build two points u i u_i ui # and v i v_i vi, for all j ∈ [ i − a i , i ] ∩ Z j\in[i-a_i,i]\cap\Z j ∈ [i − ai, i] ∩ Z, from u i u_i ui direction v j v_j vj ， connect the edges, and the edge weight is 1 1 1, indicates from i i i can jump to j j j. At the same time for each i i i. From v i v_i vi. direction u i + b i u_{i+b_i} ui+bi ， edge connected, edge weight is 0 0 0, indicating i i i this position will immediately slide to i + b i i+b_i i+bi ， this position. Note that it is necessary to build two points for each depth, because we must separate the upward jump and downward slide. We are not allowed to continue jumping after jumping without sliding, nor are we allowed to slide continuously. Then we find out on this graph u n u_n un to v 0 v_0 The shortest circuit of v0} is OK.

But this is problematic, because the edges indicating "jump" are connected to an interval from each point. If all edges are connected violently, the number of edges will reach O ( n 2 ) O(n^2) O(n2) is unacceptable in both time and space. As the saying goes, "if the IQ is not enough, the data structure will come together". At this time, we can invite the segment tree again: we build a segment tree, and the interval represented by the root node is [ 0 , n ] [0,n] [0,n], and then connect the edge from top to bottom in the tree, and the edge weight is 0 0 0, and the leaf is actually v 0 , ⋯   , v n v_0,\cdots,v_n v0​,⋯,vn​. For each i i i. Want from u i u_i ui direction interval [ i − a i , i ] [i-a_i,i] [i − ai, i] connect edges, and this interval is divided into segments on the segment tree O ( log ⁡ n ) O(\log n) The disjoint union of O(logn) intervals corresponds to the Union on the segment tree O ( log ⁡ n ) O(\log n) O(logn) nodes, from u i u_i ui) connect edges to these nodes on the line segment tree, and the edge weight is 1 1 1. So these edges connected to the interval are formed by O ( n ) O(n) O(n) is optimized to O ( log ⁡ n ) O(\log n) O(logn). Because the number of nodes in the segment tree is O ( n ) O(n) O(n), the edges connected on the line segment tree are naturally O ( n ) O(n) O(n). So the total number of sides is O ( n log ⁡ n ) O(n\log n) O(nlogn), so is the number of nodes O ( n ) O(n) O(n), just run the shortest path on this diagram. In fact, there is no need to write Dijkstra shortest path, because edge weights are 0 0 0 or 1 1 1. You can change the bfs magic into the so-called "0-1 bfs", or write an SPFA directly. In fact, it's almost the same.

My own gkxx::Vector and gkxx::Queue are used in the code. They are all made according to the standard library specification. There are more than 1000 lines pasted

#include "../../tools/Vector.hpp"
#include "../../tools/Queue.hpp"
#include <cctype>
#include <cstdio>

constexpr int maxn = 3e5 + 7;
constexpr int inf = 1e9;

gkxx::Vector<int> G[maxn * 3];

struct Node {
  int lc, rc;
};
Node sgt[maxn * 3];
int tot, root;
int leaf[maxn];
int dist[maxn * 3];
int n;

inline void add_edge(int x, int y) {
  G[x].emplace_back(y);
}

void build(int &o, int l, int r) {
  o = ++tot;
  if (l == r) {
    leaf[l] = o;
    return;
  }
  int mid = (l + r) >> 1;
  build(sgt[o].lc, l, mid);
  build(sgt[o].rc, mid + 1, r);
  add_edge(o, sgt[o].lc);
  add_edge(o, sgt[o].rc);
}

void add_edge(int o, int l, int r, int from, int tol, int tor) {
  if (tol <= l && r <= tor) {
    add_edge(from, o);
    return;
  }
  int mid = (l + r) >> 1;
  if (tol <= mid)
    add_edge(sgt[o].lc, l, mid, from, tol, tor);
  if (tor > mid)
    add_edge(sgt[o].rc, mid + 1, r, from, tol, tor);
}

gkxx::Queue<int> q;

int main() {
  scanf("%d", &n);
  tot = n;
  build(root, 0, n);
  for (int i = 1; i <= n; ++i) {
    int a;
    scanf("%d", &a);
    add_edge(root, 0, n, i, i - a, i);
  }
  for (int i = 1; i <= n; ++i) {
    int b;
    scanf("%d", &b);
    add_edge(leaf[i], i + b);
  }
  for (int i = 0; i <= tot; ++i)
    dist[i] = inf;
  dist[n] = 0;
  q.push(n);
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    int w = x <= n ? 1 : 0;
    for (auto v : G[x]) {
      if (dist[v] > dist[x] + w) {
        dist[v] = dist[x] + w;
        q.push(v);
      }
    }
  }
  printf("%d\n", dist[leaf[0]] < inf ? dist[leaf[0]] : -1);
  return 0;
}

Algorithm 2: DP

set up f ( i ) f(i) f(i) indicates jumping to a depth of i i How many steps does it take for the position of i (not yet sliding down). Suppose the previous step is to jump to a depth of j j j's position, slipped again j + b j j+b_j j+bj ， then from j + b j j+b_j j+bj jump to i i i. Means i ∈ [ j + b j − a j + b j , j + b j ] i\in\left[j+b_j-a_{j+b_j},j+b_j\right] i∈[j+bj​−aj+bj​​,j+bj​]. So we have an obvious transfer equation
f ( i ) = min ⁡ { f ( j ) + 1 : j + b j − a j + b j ⩽ i ⩽ j + b j } . f(i)=\min\left\{f(j)+1:j+b_j-a_{j+b_j}\leqslant i\leqslant j+b_j\right\}. f(i)=min{f(j)+1:j+bj​−aj+bj​​⩽i⩽j+bj​}.
But it is impossible to do so directly, because the conditions are met j j j scattered in various positions, which may be greater than i i i. It may also be less than i i i. But you're begging f ( i ) f(i) These must be guaranteed when f(i) f ( j ) f(j) f(j) has been calculated. In what order should you calculate these f ( i ) f(i) f(i)？ This is impossible. Of course, you can think of it as a dp with a transfer ring. For this DP, a strategy is to use a graph theory algorithm to solve it, such as bfs or shortest path, so you are brought to algorithm 1.

But we will find: useful j j j must be greater than i i i. That is, jump to bi i i i slide down from the high position and jump to the high position i i i won't be better. Why? Because you started at the bottom n n n starts jumping if you're from Bi i i A position i high j j j slipped to j + b j j+b_j j+bj, and then from j + b j j+b_j Jump to j+bj i i i. Then there must have been a step before, you from i i i low position k k k jumped to bi i i i high position, and in this step you can choose to jump directly to i i i. So we get j > i j>i j> I, or i ⩽ j − 1 i\leqslant j-1 i ⩽ j − 1, then i ⩽ min ⁡ { j − 1 , j + b j } = j − 1 i\leqslant\min\{j-1,j+b_j\}=j-1 i⩽min{j−1,j+bj​}=j−1. So the transfer equation becomes
f ( i ) = min ⁡ { f ( j ) + 1 : j + b j − a j + b j ⩽ i ⩽ j − 1 } . f(i)=\min\left\{f(j)+1:j+b_j-a_{j+b_j}\leqslant i\leqslant j-1\right\}. f(i)=min{f(j)+1:j+bj​−aj+bj​​⩽i⩽j−1}.
We enumerate from large to small i i i to calculate these f ( i ) f(i) f(i), the transfer has no ring. Time complexity of transfer O ( n ) O(n) O(n), total complexity O ( n 2 ) O(n^2) O(n2).

f[n] = 0;
for (int i = n - 1; i >= 0; --i) {
  f[i] = inf;
  for (int j = n; j > i; --j)
    if (j + b[j] - a[j + b[j]] <= i && f[j] + 1 < f[i])
      f[i] = f[j] + 1;
}

It's a pity, O ( n 2 ) O(n^2) O(n2) can't pass. But in fact, you are only one step away from success, because you have noticed an important nature: for any position i i i say, jump to the ratio i i i slide down from the high position and jump to the high position i i i is meaningless.

Consider any two locations i 1 i_1 i1} and i 2 i_2 i2, hypothesis i 1 > i 2 i_1>i_2 i1 > I2, i.e i 1 i_1 i1# lower, then there must be f ( i 1 ) ⩽ f ( i 2 ) f(i_1)\leqslant f(i_2) f(i1) ⩽ f(i2), that is, the higher you jump, the more steps you take. Because in order to jump to a higher position i 2 i_2 i2, you have to compare at some point i 1 i_1 i1# low position k k k jump to ratio i 1 i_1 i1# high, and in this step, you can choose to jump directly to i 1 i_1 i1#. So there is no need to enumerate when we transfer j j j. Just find satisfaction directly j + b j − a j + b j ⩽ i j+b_j-a_{j+b_j}\leqslant i j+bj − aj+bj ⩽ i and j > i j>i j> Maximum of I j j Just j.

But directly from i i i find the largest eligible j j j is more difficult. We can change the direction and enumerate each one from large to small j j j. Will f ( j ) f(j) f(j) as known, enumerate those j j j can be transferred to i i i. Order f ( i ) = f ( j ) + 1 f(i)=f(j)+1 f(i)=f(j)+1. Note that it is easy to know from the previous properties that in the case of a solution, the calculated state is always continuous from the bottom to the top, that is, there is always one m m m satisfied f ( n ) , f ( n − 1 ) , ⋯   , f ( m ) f(n),f(n-1),\cdots,f(m) f(n),f(n − 1),... And f(m) have been calculated. So let's enumerate i i i, there is no need to consider those greater than or equal to m m m i i i. Specifically, for each j j j, satisfaction i ∈ [ j + b j − a j + b j , j + b j ] i\in[j+b_j-a_{j+b_j},j+b_j] All of i ∈ [j+bj − aj+bj, j+bj] i i i can be transferred to, and we just need to consider satisfaction i ∈ [ j + b j − a j + b j , min ⁡ { j + b j , m − 1 } ] i\in[j+b_j-a_{j+b_j},\min\{j+b_j,m-1\}] i ∈ [j+bj − aj+bj, min{j+bj, m − 1}] i i i. And remember to update after each calculation m m m. The code is as follows:

#include <algorithm>
#include <cstdio>

constexpr int maxn = 3e5 + 10;
constexpr int inf = 2e9;

int a[maxn], b[maxn], n;
int f[maxn];

int main() {
  freopen("data.in", "r", stdin);
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i)
    scanf("%d", a + i);
  for (int i = 1; i <= n; ++i)
    scanf("%d", b + i);
  for (int i = 0; i < n; ++i)
    f[i] = inf;
  int m = n;
  for (int j = n; j > 0; --j) {
    for (int i = j + b[j] - a[j + b[j]]; i <= std::min(j + b[j], m - 1); ++i)
      f[i] = f[j] + 1;
    if (j + b[j] - a[j + b[j]] < m)
      m = j + b[j] - a[j + b[j]];
  }
  printf("%d\n", f[0] < inf ? f[0] : -1);
  return 0;
}

What is the time complexity of this algorithm? There seems to be a double loop, but in fact, we ensure that each state is calculated only once, so the complexity is O ( n ) O(n) O(n).

4002

To give an undirected connected graph, now from 1 1 Starting from point 1, you can walk freely between the points you have passed, but every time you encounter a new node, you will record the label of this node in your notebook. Finally, you will get a sequence in your book and find the one with the smallest dictionary order among all possible sequences. n ⩽ 500 n\leqslant 500 n⩽500.

A greedy problem for the mentally retarded. You can choose the lowest number among all the nodes you can reach each time. The time complexity of directly enumerating to find the minimum number is O ( n 3 ) O(n^3) O(n3). But this question is for n ⩽ 500 n\leqslant 500 n ⩽ 500 to be honest, I'm not very good at Sister Li, because we actually have O ( ( n + m ) log ⁡ n ) O((n+m)\log n) O((n+m)logn): just change the bfs queue to the minimum heap.

4003

TSP

Directly from 1 1 Starting from point 1, we always take the shortest side we can take every time, which is greedy and complex O ( n 2 ) O(n^2) O(n2), obviously this is a wrong greed, and its solution can get 54 points.

If you don't 1 1 Start from point 1, but enumerate the starting points and run the algorithm n n n times, take the optimal solution, you can get 69-72 points.

Let's not talk about the algorithms with higher scores. There are simulated annealing, ant colony, genetics and so on. Some people fooled around and took 87. Study online by yourself.

I fooled around, took 81 and played other games. One night I dreamed that two monsters scored 90 points. I woke up and saw if I found it.