BCCs and 2CCs

Catalan Numbers

DP on Trees - Combining Subtrees

Querying for the minimum and number of occurrences of minimum in a range

Counting Minimums with Segment Tree

Finding nodes that must be visited along any path.

Critical

Dynamic programming on grid boundary states.

DP on Broken Profile

Additional dynamic programming techniques and optimizations like Knuth's optimization.

Additional DP Optimizations and Techniques

Visiting all edges of a graph exactly once.

Eulerian Tours

A formula for finding the number of faces in a planar graph.

Euler's Formula

Extended Euclidean Algorithm

More Complex Operations Using FFT

Introduction to Fast Fourier Transform

Flow with Lower Bounds

A simple solution to "Robotic Cow Herd" that generalizes.

Fracturing Search

Solving games that are usually two-player to find the winner.

Game Theory

Interactive and Communication Problems

Link Cut Tree

Lagrangian Relaxation

LineContainer

Matroid Intersection

Introduces maximum flow as well as flow with lower bounds.

Maximum Flow

Triangle Inequality, Johnson's Algorithm, and Min Cost Flow

Minimum Cost Flow

Minimum Cut

Erasing from non-amortized insert-only data structures.

Offline Deletion

What if data structures could time travel?

Persistent Data Structures

Prefix Sums of Number-Theoretic Functions (Part 1)

Prefix Sums of Number-Theoretic Functions (Part 2)

Subsets of nodes in directed graphs where each node in a subset can reach each other node in the subset.

Strongly Connected Components

Returning to Bellman-Ford and Floyd-Warshall.

Shortest Paths with Negative Edge Weights

Segment Tree Beats

Slope trick refers to a way to manipulate piecewise linear convex functions. Includes a simple solution to USACO Landscaping.

Slope Trick

Max Suffix Query with Insertions Only

Knuth-Morris-Pratt and Z Algorithms (and a few more related topics).

String Searching

Suffix Automata, Suffix Trees, and Palindromic Trees

String Suffix Structures

Quickly sorting suffixes of a string and its applications

Suffix Array

Treaps

Vectorization in C++

Efficiently querying for the kth minimum element in a subarray.

Wavelet Tree

XOR Basis

Using randomized algorithms to solve problems.

Randomness

Extending Range Queries to 2D (and beyond).

2D Range Queries

Binary Jumping

Examples of how bitsets give some unintended solutions on recent USACO problems.

(Optional) Bitsets

Decomposing a tree to facilitate path computations.

Centroid Decomposition

Final tips for Platinum and additional practice problems.

Additional Practice for USACO Platinum

Smallest convex polygon containing a set of points on a grid.

Convex Hull

A way to find the maximum or minimum value of several convex functions at given points.

Convex Hull Trick

Using Divide & Conquer as a DP Optimization.

Divide & Conquer - DP

Using Divide & Conquer to answer offline or online range queries on a static array.

Divide & Conquer - SRQ

Solving subset sum problems efficiently with DP.

Sum over Subsets DP

Geometry Primitives

Heavy-Light Decomposition

Repeatedly multiplying a square matrix by itself.

Matrix Exponentiation

Small-To-Large Merging

The inclusion-exclusion principle is a counting technique that generalizes the formula for computing the size of union of n finite sets.

Inclusion-Exclusion Principle

Lazy updates on segment trees and two binary indexed trees in conjunction.

Range Update Range Query

Solving 2D grid problems using 1D range queries.

Range Queries with Sweep Line

Walking on a Segment Tree, Non-Commutative Combiner Functions

More Applications of Segment Tree

Sparse Segment Trees

Splitting up data into smaller chunks to speed up processing.

Square Root Decomposition

Sweep Line

Compressing a tree to only the necessary nodes.

Virtual Tree

Decomposing Kruskal's algorithm to solve problems about minimum/maximum edge weights.

Kruskal Reconstruction Tree

DP on Trees - Solving For All Roots

Combinatorics

Final tips for Gold and additional practice problems.

Additional Practice for USACO Gold

Incorporating custom comparators into standard library containers.

(Optional) Sorted Sets with Custom Comparators

DP problems that require iterating over subsets.

Bitmask DP

Solving a DP problem on every contiguous subarray of the original array.

Range DP

DP on Trees - Introduction

The Disjoint Set Union (DSU) data structure, which allows you to add edges to a graph and test whether two vertices of the graph are connected.

Disjoint Set Union

Finding the number of integers in a range that have a property.

Digit DP

Using the information that one integer evenly divides another.

Divisibility

Quickly testing equality of substrings or sets with a small probability of failure.

Hashing

Maintaining collections of distinct elements with hashing.

(Optional) Hashmaps

Speeding up naive recursive solutions with memoization.

Introduction to DP

Finding the next element smaller or larger than a specified key in a sorted set, and using iterators with sorted sets.

More Operations on Sorted Sets

Problems that can be modeled as filling a limited-size container with items.

Knapsack DP

Finding and using the longest increasing subsequence of an array.

Longest Increasing Subsequence

Finding a subset of the edges of a connected, undirected, edge-weighted graph that connects all the vertices to each other of minimum total weight.

Minimum Spanning Trees

Problems involving dividing the search space into two.

Meet In The Middle

Modular Arithmetic

Segment Tree, Binary Indexed Tree, and Order Statistic Tree (in C++).

Point Update Range Sum

Counting the number of "special" paths on a grid, and how some string problems can be solved using grids.

Paths on Grids

Bellman-Ford, Floyd-Warshall, and Dijkstra.

Shortest Paths with Non-Negative Edge Weights

Maintaining data over consecutive subarrays.

Sliding Window

A data structure that only allows insertion and deletion at one end.

Stacks

Using ternary or binary search to find the mode of unimodal functions.

Optimizing Unimodal Functions

Ordering the vertices of a directed acyclic graph such that each vertex is visited before its children.

Topological Sort

Flattening a tree into an array to easily query and update subtrees.

Euler Tour Technique

Introduces how BFS can be used to find shortest paths in unweighted graphs.

Shortest Paths with Unweighted Edges

Binary searching on arbitrary monotonic functions.

Binary Search

Efficiently searching for a value in a sorted array.

Binary Search on a Sorted Array

Final tips for Silver and additional practice problems.

Additional Practice for USACO Silver

Finding connected components in a graph represented by a grid.

Flood Fill

Directed graphs in which every vertex has exactly one outgoing edge.

Introduction to Functional Graphs

Traversing a graph with depth first search and breadth first search.

Graph Traversal

Solving greedy problems by sorting the input.

Greedy Algorithms with Sorting

Six bitwise operators and the common ways they are used.

Intro to Bitwise Operators

Introducing a special type of graph: trees.

Introduction to Tree Algorithms

Salary Queries

"use strict";
const {Fragment: _Fragment, jsx: _jsx, jsxs: _jsxs} = arguments[0];
const frontmatter = undefined;
function _createMdxContent(props) {
  const _components = {
    a: "a",
    code: "code",
    h2: "h2",
    p: "p",
    pre: "pre",
    ...props.components
  }, {CPPSection, HeaderLink, JavaSection, LanguageSection} = _components;
  if (!CPPSection) _missingMdxReference("CPPSection", true);
  if (!HeaderLink) _missingMdxReference("HeaderLink", true);
  if (!JavaSection) _missingMdxReference("JavaSection", true);
  if (!LanguageSection) _missingMdxReference("LanguageSection", true);
  return _jsxs(_Fragment, {
    children: [_jsxs(_components.h2, {
      id: "solution-1",
      children: [_jsx(_components.a, {
        "aria-hidden": "true",
        tabIndex: "-1",
        className: "anchor before",
        href: "#solution-1",
        children: _jsx(HeaderLink, {})
      }), "Solution 1"]
    }), "\n", _jsx(_components.p, {
      children: "As mentioned in the module, you can apply coordinate compression before using a\nsegment tree or a BIT."
    }), "\n", _jsxs(_components.p, {
      children: ["Stick with arrays (or ", _jsx(_components.code, {
        children: "vector"
      }), "s) whenever possible; using a ", _jsx(_components.code, {
        children: "map"
      }), " instead may\nTLE."]
    }), "\n", _jsxs(LanguageSection, {
      children: [_jsx(CPPSection, {
        children: _jsx(_components.pre, {
          children: _jsx(_components.code, {
            className: "language-cpp",
            children: "#include <bits/stdc++.h>\n\nusing namespace std;\nusing ll = long long;\n\nconst int MX = 4e5 + 5;\n\nll bit[MX];\nvector<int> vals;\nint n, q;\n\nvoid upd(int i, int val) {\n\tfor (; i <= MX; i += i & (-i)) { bit[i] += val; }\n}\n\nvoid ad(int x, int b) {\n\tint ind = upper_bound(vals.begin(), vals.end(), x) - vals.begin();\n\tupd(ind, b);\n}\n\nll sum(int x) {\n\tll res = 0;\n\tfor (; x; x -= x & (-x)) { res += bit[x]; }\n\treturn res;\n}\n\nll query(int x) {\n\tint ind = upper_bound(vals.begin(), vals.end(), x) - vals.begin();\n\treturn sum(ind);\n}\n\nint main() {\n\tcin >> n >> q;\n\tvector<int> ar(n);\n\tfor (int i = 0; i < n; i++) { cin >> ar[i]; }\n\tvals = ar;\n\tvector<array<int, 3>> rec;\n\tfor (int i = 0; i < q; i++) {\n\t\tchar t;\n\t\tint a, b;\n\t\tcin >> t >> a >> b;\n\t\trec.push_back({t == '?', a, b});\n\t\tif (t == '!') vals.push_back(b);\n\t}\n\tsort(vals.begin(), vals.end());\n\tvals.erase(unique(vals.begin(), vals.end()), vals.end());\n\tfor (int i = 0; i < n; i++) { ad(ar[i], 1); }\n\tfor (auto u : rec) {\n\t\tu[1]--;\n\t\tif (u[0] == 0) {\n\t\t\tad(ar[u[1]], -1);\n\t\t\tar[u[1]] = u[2];\n\t\t\tad(ar[u[1]], 1);\n\t\t} else {\n\t\t\tcout << query(u[2]) - query(u[1]) << '\\n';\n\t\t}\n\t}\n}\n"
          })
        })
      }), _jsx(JavaSection, {
        children: _jsx(_components.pre, {
          children: _jsx(_components.code, {
            className: "language-java",
            children: "import java.io.*;\nimport java.util.*;\n\n// Utilizing the Fact that Total Unique Number of Salaries Including the Queries and\n// Input Array is no more than n (2e5) + 2 * q (2e5) which is 6*10^5.\n\n// So we don't have to worry about salary in range 1e9, we will compress it.\n\npublic class Salary_Queries {\n\tstatic Reader fr = new Reader();\n\tstatic PrintWriter out = new PrintWriter(System.out);\n\n\tstatic long[] list;\n\tstatic long[] Seq;\n\tstatic HashMap<Long, Integer> map;\n\n\tpublic static void main(String[] args) throws java.lang.Exception {\n\t\tint n = fr.nextInt();\n\t\tint q = fr.nextInt();\n\n\t\t// Fixed-size array avoids ArrayList's resizing overhead and Long autoboxing.\n\t\tlist = new long[n + (q << 1)];\n\t\tint ptr = 0;\n\t\tlong[] arr = new long[n];\n\t\tfor (int i = 0; i < n; i++) {\n\t\t\tarr[i] = fr.nextLong();\n\t\t\tlist[ptr++] = arr[i];\n\t\t}\n\n\t\tlong[][] query = new long[q][3];\n\t\tfor (int i = 0; i < q; i++) {\n\t\t\tchar ch = fr.nextChar();\n\t\t\tlong a = fr.nextLong();\n\t\t\tlong b = fr.nextLong();\n\n\t\t\tif (ch == '!') {\n\t\t\t\tquery[i][0] = 0;\n\t\t\t\tquery[i][1] = a - 1;\n\t\t\t\tquery[i][2] = b;\n\n\t\t\t\tlist[ptr++] = b;\n\t\t\t} else {\n\t\t\t\tquery[i][0] = 1;\n\t\t\t\tquery[i][1] = a;\n\t\t\t\tquery[i][2] = b;\n\t\t\t\tlist[ptr++] = a;\n\t\t\t\tlist[ptr++] = b;\n\t\t\t}\n\t\t}\n\n\t\t// Compression Step\n\t\t// Start\n\t\tArrays.sort(list, 0, ptr);\n\n\t\tint cnt = 0;\n\t\tlong prev = 0;\n\t\tmap = new HashMap<>();\n\t\tfor (int i = 0; i < ptr; i++) {\n\t\t\tif (prev != list[i]) map.put(list[i], cnt++);\n\t\t\tprev = list[i];\n\t\t}\n\t\t// End\n\n\t\tBIT bt = new BIT(cnt);\n\n\t\tfor (long ele : arr) { bt.update(map.get(ele), 1); }\n\n\t\tStringBuilder SB = new StringBuilder();\n\t\tfor (long[] qr : query) {\n\t\t\tif (qr[0] == 0) {\n\t\t\t\tbt.update(map.get(arr[(int)qr[1]]), -1);\n\t\t\t\tarr[(int)qr[1]] = qr[2];\n\t\t\t\tbt.update(map.get(arr[(int)qr[1]]), 1);\n\t\t\t} else {\n\t\t\t\tint ans = bt.get(map.get(qr[1]), map.get(qr[2]));\n\n\t\t\t\tSB.append(ans).append('\\n');\n\t\t\t}\n\t\t}\n\n\t\tout.println(SB.to_string());\n\t\tout.close();\n\t}\n\n\t// BeginCodeSnip{Reader}\n\tstatic class Reader {\n\t\tprivate final int BUFFER_SIZE = 1 << 16;\n\t\tprivate DataInputStream din;\n\t\tprivate byte[] buffer;\n\t\tprivate int bufferPointer, bytesRead;\n\n\t\tpublic Reader() {\n\t\t\tdin = new DataInputStream(System.in);\n\t\t\tbuffer = new byte[BUFFER_SIZE];\n\t\t\tbufferPointer = bytesRead = 0;\n\t\t}\n\n\t\t// Reads the next integer from input\n\t\tpublic int nextInt() throws IOException {\n\t\t\tint ret = 0;\n\t\t\tbyte c = read();\n\t\t\twhile (c <= ' ') { c = read(); }\n\t\t\tboolean neg = (c == '-');\n\t\t\tif (neg) c = read();\n\t\t\tdo { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9');\n\t\t\treturn neg ? -ret : ret;\n\t\t}\n\n\t\t// Reads the next long from input\n\t\tpublic long nextLong() throws IOException {\n\t\t\tlong ret = 0;\n\t\t\tbyte c = read();\n\t\t\twhile (c <= ' ') { c = read(); }\n\t\t\tboolean neg = (c == '-');\n\t\t\tif (neg) c = read();\n\t\t\tdo { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9');\n\t\t\treturn neg ? -ret : ret;\n\t\t}\n\n\t\tpublic char nextChar() throws IOException {\n\t\t\tbyte c = read();\n\t\t\twhile (c <= ' ') { c = read(); }\n\t\t\treturn (char)c;\n\t\t}\n\n\t\t// Reads the next byte from the buffer\n\t\tprivate byte read() throws IOException {\n\t\t\tif (bufferPointer == bytesRead) fillBuffer();\n\t\t\treturn buffer[bufferPointer++];\n\t\t}\n\n\t\t// Fills the buffer with new data\n\t\tprivate void fillBuffer() throws IOException {\n\t\t\tbytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);\n\t\t\tif (bytesRead == -1) buffer[0] = -1;\n\t\t}\n\t}\n\t// EndCodeSnip\n\n\tpublic static int max(int a, int b) { return Math.max(a, b); }\n\tpublic static int min(int a, int b) { return Math.min(a, b); }\n\tpublic static long max(long a, long b) { return Math.max(a, b); }\n\tpublic static long min(long a, long b) { return Math.min(a, b); }\n}\n\nclass BIT {\n\tint[] bit;\n\tint size;\n\n\tpublic BIT(int n) {\n\t\tthis.size = n;\n\t\tbit = new int[n + 1];\n\t}\n\tint sum(int r) {\n\t\tint res = 0;\n\t\tfor (; r >= 0; r = (r & (r + 1)) - 1) { res += bit[r]; }\n\n\t\treturn res;\n\t}\n\n\tvoid update(int x, int delta) {\n\t\tfor (; x < size; x |= x + 1) { bit[x] += delta; }\n\t}\n\n\tint get(int l, int r) { return sum(r) - sum(l - 1); }\n}\n"
          })
        })
      })]
    }), "\n", _jsxs(_components.p, {
      children: ["Here is a similar solution with a ", _jsx(_components.code, {
        children: "map"
      }), " that passes slightly under the time\nlimit."]
    }), "\n", _jsx(LanguageSection, {
      children: _jsx(CPPSection, {
        children: _jsx(_components.pre, {
          children: _jsx(_components.code, {
            className: "language-cpp",
            children: "#include <bits/stdc++.h>\nusing namespace std;\n\nusing ll = long long;\nusing ld = long double;\nusing db = double;\nusing str = string;  // yay python!\n\nusing pi = pair<int, int>;\nusing pl = pair<ll, ll>;\nusing pd = pair<db, db>;\n\nusing vi = vector<int>;\nusing vb = vector<bool>;\nusing vl = vector<ll>;\nusing vd = vector<db>;\nusing vs = vector<str>;\nusing vpi = vector<pi>;\nusing vpl = vector<pl>;\nusing vpd = vector<pd>;\n\n#define tcT template <class T\n#define tcTU tcT, class U\n// ^ lol this makes everything look weird but I'll try it\ntcT > using V = vector<T>;\ntcT, size_t SZ > using AR = array<T, SZ>;\ntcT > using PR = pair<T, T>;\n\n// pairs\n#define mp make_pair\n#define f first\n#define s second\n\n// vectors\n// oops size(x), rbegin(x), rend(x) need C++17\n#define sz(x) int((x).size())\n#define bg(x) begin(x)\n#define all(x) bg(x), end(x)\n#define rall(x) x.rbegin(), x.rend()\n#define sor(x) sort(all(x))\n#define rsz resize\n#define ins insert\n#define ft front()\n#define bk back()\n#define pb push_back\n#define eb emplace_back\n#define pf push_front\n\n#define lb lower_bound\n#define ub upper_bound\ntcT > int lwb(V<T> &a, const T &b) { return int(lb(all(a), b) - bg(a)); }\n\n// loops\n#define FOR(i, a, b) for (int i = (a); i < (b); ++i)\n#define F0R(i, a) FOR(i, 0, a)\n#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); --i)\n#define R0F(i, a) ROF(i, 0, a)\n#define trav(a, x) for (auto &a : x)\n\nconst int MOD = 1e9 + 7;  // 998244353;\nconst int MX = 2e5 + 5;\nconst ll INF = 1e18;  // not too close to LLONG_MAX\nconst ld PI = acos((ld)-1);\nconst int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};  // for every grid problem!!\nmt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());\ntemplate <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;\n\n// bitwise ops\n// also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html\nconstexpr int pct(int x) { return __builtin_popcount(x); }  // # of bits set\nconstexpr int bits(int x) {  // assert(x >= 0); // make C++11 compatible until\n\t                         // USACO updates ...\n\treturn x == 0 ? 0 : 31 - __builtin_clz(x);\n}  // floor(log2(x))\nconstexpr int p2(int x) { return 1 << x; }\nconstexpr int msk2(int x) { return p2(x) - 1; }\n\nll cdiv(ll a, ll b) {\n\treturn a / b + ((a ^ b) > 0 && a % b);\n}  // divide a by b rounded up\nll fdiv(ll a, ll b) {\n\treturn a / b - ((a ^ b) < 0 && a % b);\n}  // divide a by b rounded down\n\ntcT > bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }  // set a = min(a,b)\ntcT > bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }\n\ntcTU > T fstTrue(T lo, T hi, U f) {\n\thi++;\n\tassert(lo <= hi);  // assuming f is increasing\n\twhile (lo < hi) {  // find first index such that f is true\n\t\tT mid = lo + (hi - lo) / 2;\n\t\tf(mid) ? hi = mid : lo = mid + 1;\n\t}\n\treturn lo;\n}\ntcTU > T lstTrue(T lo, T hi, U f) {\n\tlo--;\n\tassert(lo <= hi);  // assuming f is decreasing\n\twhile (lo < hi) {  // find first index such that f is true\n\t\tT mid = lo + (hi - lo + 1) / 2;\n\t\tf(mid) ? lo = mid : hi = mid - 1;\n\t}\n\treturn lo;\n}\ntcT > void remDup(vector<T> &v) {  // sort and remove duplicates\n\tsort(all(v));\n\tv.erase(unique(all(v)), end(v));\n}\ntcTU > void erase(T &t, const U &u) {  // don't erase\n\tauto it = t.find(u);\n\tassert(it != end(t));\n\tt.erase(it);\n}  // element that doesn't exist from (multi)set\n\n// INPUT\n#define tcTUU tcT, class... U\ntcT > void re(complex<T> &c);\ntcTU > void re(pair<T, U> &p);\ntcT > void re(V<T> &v);\ntcT, size_t SZ > void re(AR<T, SZ> &a);\n\ntcT > void re(T &x) { cin >> x; }\nvoid re(db &d) {\n\tstr t;\n\tre(t);\n\td = stod(t);\n}\nvoid re(ld &d) {\n\tstr t;\n\tre(t);\n\td = stold(t);\n}\ntcTUU > void re(T &t, U &...u) {\n\tre(t);\n\tre(u...);\n}\n\ntcT > void re(complex<T> &c) {\n\tT a, b;\n\tre(a, b);\n\tc = {a, b};\n}\ntcTU > void re(pair<T, U> &p) { re(p.f, p.s); }\ntcT > void re(V<T> &x) { trav(a, x) re(a); }\ntcT, size_t SZ > void re(AR<T, SZ> &x) { trav(a, x) re(a); }\ntcT > void rv(int n, V<T> &x) {\n\tx.rsz(n);\n\tre(x);\n}\n\n// TO_STRING\n#define ts to_string\nstr ts(char c) { return str(1, c); }\nstr ts(const char *s) { return (str)s; }\nstr ts(str s) { return s; }\nstr ts(bool b) {\n#ifdef LOCAL\n\treturn b ? \"true\" : \"false\";\n#else\n\treturn ts((int)b);\n#endif\n}\ntcT > str ts(complex<T> c) {\n\tstringstream ss;\n\tss << c;\n\treturn ss.str();\n}\nstr ts(V<bool> v) {\n\tstr res = \"{\";\n\tF0R(i, sz(v)) res += char('0' + v[i]);\n\tres += \"}\";\n\treturn res;\n}\ntemplate <size_t SZ> str ts(bitset<SZ> b) {\n\tstr res = \"\";\n\tF0R(i, SZ) res += char('0' + b[i]);\n\treturn res;\n}\ntcTU > str ts(pair<T, U> p);\ntcT > str ts(T v) {  // containers with begin(), end()\n#ifdef LOCAL\n\tbool fst = 1;\n\tstr res = \"{\";\n\tfor (const auto &x : v) {\n\t\tif (!fst) res += \", \";\n\t\tfst = 0;\n\t\tres += ts(x);\n\t}\n\tres += \"}\";\n\treturn res;\n#else\n\tbool fst = 1;\n\tstr res = \"\";\n\tfor (const auto &x : v) {\n\t\tif (!fst) res += \" \";\n\t\tfst = 0;\n\t\tres += ts(x);\n\t}\n\treturn res;\n\n#endif\n}\ntcTU > str ts(pair<T, U> p) {\n#ifdef LOCAL\n\treturn \"(\" + ts(p.f) + \", \" + ts(p.s) + \")\";\n#else\n\treturn ts(p.f) + \" \" + ts(p.s);\n#endif\n}\n\n// OUTPUT\ntcT > void pr(T x) { cout << ts(x); }\ntcTUU > void pr(const T &t, const U &...u) {\n\tpr(t);\n\tpr(u...);\n}\nvoid ps() { pr(\"\\n\"); }  // print w/ spaces\ntcTUU > void ps(const T &t, const U &...u) {\n\tpr(t);\n\tif (sizeof...(u)) pr(\" \");\n\tps(u...);\n}\n\n// DEBUG\nvoid DBG() { cerr << \"]\" << endl; }\ntcTUU > void DBG(const T &t, const U &...u) {\n\tcerr << ts(t);\n\tif (sizeof...(u)) cerr << \", \";\n\tDBG(u...);\n}\n#ifdef LOCAL  // compile with -DLOCAL, chk -> fake assert\n#define dbg(...)                                                                       \\\n\tcerr << \"Line(\" << __LINE__ << \") -> [\" << #__VA_ARGS__ << \"]: [\", DBG(__VA_ARGS__)\n#define chk(...)                                                                       \\\n\tif (!(__VA_ARGS__))                                                                \\\n\t\tcerr << \"Line(\" << __LINE__ << \") -> function(\" << __FUNCTION__                \\\n\t\t     << \") -> CHK FAILED: (\" << #__VA_ARGS__ << \")\" << \"\\n\",                   \\\n\t\t    exit(0);\n#else\n#define dbg(...) 0\n#define chk(...) 0\n#endif\n\nvoid setPrec() { cout << fixed << setprecision(15); }\nvoid unsyncIO() { cin.tie(0)->sync_with_stdio(0); }\n// FILE I/O\nvoid setIn(str s) { freopen(s.c_str(), \"r\", stdin); }\nvoid setOut(str s) { freopen(s.c_str(), \"w\", stdout); }\nvoid setIO(str s = \"\") {\n\tunsyncIO();\n\tsetPrec();\n\t// cin.exceptions(cin.failbit);\n\t// throws exception when do smth illegal\n\t// ex. try to read letter into int\n\tif (sz(s)) setIn(s + \".in\"), setOut(s + \".out\");  // for USACO\n}\n\n/**\n * Description: range sum queries and point updates for $D$ dimensions\n * Source: https://codeforces.com/blog/entry/64914\n * Verification: SPOJ matsum\n * Usage: \\texttt{BIT<int,10,10>} gives 2D BIT\n * Time: O((\\log N)^D)\n */\n\ntemplate <class T, int... Ns> struct BIT {\n\tT val = 0;\n\tvoid upd(T v) { val += v; }\n\tT query() { return val; }\n};\ntemplate <class T, int N, int... Ns> struct BIT<T, N, Ns...> {\n\tBIT<T, Ns...> bit[N + 1];\n\ttemplate <typename... Args> void upd(int pos, Args... args) {\n\t\tassert(pos > 0);\n\t\tfor (; pos <= N; pos += pos & -pos) bit[pos].upd(args...);\n\t}\n\ttemplate <typename... Args> T sum(int r, Args... args) {\n\t\tT res = 0;\n\t\tfor (; r; r -= r & -r) res += bit[r].query(args...);\n\t\treturn res;\n\t}\n\ttemplate <typename... Args> T query(int l, int r, Args... args) {\n\t\treturn sum(r, args...) - sum(l - 1, args...);\n\t}\n\tint get_kth(T des) {\n\t\tassert(des > 0);\n\t\tint ind = 0;\n\t\tfor (int i = 1 << bits(N); i; i /= 2)\n\t\t\tif (ind + i <= N && bit[ind + i].val < des) des -= bit[ind += i].val;\n\t\tassert(ind < N);\n\t\treturn ind + 1;\n\t}\n};\ntemplate <class T, int N> int get_kth(const BIT<T, N> &bit, T des) {\n\tassert(des > 0);\n\tint ind = 0;\n\tfor (int i = 1 << bits(N); i; i /= 2)\n\t\tif (ind + i <= N && bit.bit[ind + i].val < des) des -= bit.bit[ind += i].val;\n\tassert(ind < N);\n\treturn ind + 1;\n}\n\nBIT<int, 1000005> B;\n\nmap<int, int> vals;\nint N, Q;\n\nvoid ad(int a, int b) {\n\tint ind = vals[a];\n\tB.upd(ind, b);\n}\n\nint query(int x) {\n\tauto it = vals.ub(x);\n\tint mx;\n\tif (it == end(vals)) mx = sz(vals);\n\telse mx = it->s - 1;\n\treturn B.sum(mx);\n}\n\nint main() {\n\tsetIO();\n\tre(N, Q);\n\tvi P(N);\n\tre(P);\n\ttrav(t, P) vals[t] = 0;\n\tV<AR<int, 3>> rec;\n\tF0R(i, Q) {\n\t\tchar t;\n\t\tint a, b;\n\t\tre(t, a, b);\n\t\trec.pb({t == '?', a, b});\n\t\tif (t == '!') vals[b] = 0;\n\t}\n\tint cnt = 0;\n\ttrav(t, vals) t.s = ++cnt;\n\ttrav(p, P) ad(p, 1);\n\ttrav(u, rec) {\n\t\tu[1]--;\n\t\tif (u[0] == 0) {\n\t\t\tad(P[u[1]], -1);\n\t\t\tP[u[1]] = u[2];\n\t\t\tad(P[u[1]], 1);\n\t\t} else ps(query(u[2]) - query(u[1]));\n\t}\n}\n"
          })
        })
      })
    }), "\n", _jsxs(_components.h2, {
      id: "solution-2",
      children: [_jsx(_components.a, {
        "aria-hidden": "true",
        tabIndex: "-1",
        className: "anchor before",
        href: "#solution-2",
        children: _jsx(HeaderLink, {})
      }), "Solution 2"]
    }), "\n", _jsx(_components.p, {
      children: "Just use indexed set!"
    }), "\n", _jsx(LanguageSection, {
      children: _jsx(CPPSection, {
        children: _jsx(_components.pre, {
          children: _jsx(_components.code, {
            className: "language-cpp",
            children: "#include <bits/stdc++.h>\n#include <ext/pb_ds/assoc_container.hpp>\n\nusing namespace std;\nusing namespace __gnu_pbds;\n\ntypedef long long ll;\ntypedef vector<int> vi;\ntypedef pair<int, int> pii;\ntemplate <class T>\nusing Tree =\n    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;\n\n#define FOR(i, a, b) for (int i = a; i < (b); i++)\n#define F0R(i, a) for (int i = 0; i < (a); i++)\n#define FORd(i, a, b) for (int i = (b) - 1; i >= a; i--)\n#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; i--)\n\n#define sz(x) (int)(x).size()\n#define mp make_pair\n#define pb push_back\n#define f first\n#define s second\n#define lb lower_bound\n#define ub upper_bound\n#define all(x) x.begin(), x.end()\n\nconst int MOD = 1000000007;\n\nint n, q, a[200001];\nTree<pii> o;\n\nint main() {\n\tios_base::sync_with_stdio(0);\n\tcin.tie(0);\n\tcin >> n >> q;\n\tFOR(i, 1, n + 1) {\n\t\tcin >> a[i];\n\t\to.insert({a[i], i});\n\t}\n\tF0R(i, q) {\n\t\tchar c;\n\t\tcin >> c;\n\t\tif (c == '!') {\n\t\t\tint x, y;\n\t\t\tcin >> x >> y;\n\t\t\to.erase({a[x], x});\n\t\t\ta[x] = y;\n\t\t\to.insert({a[x], x});\n\t\t} else {\n\t\t\tint x, y;\n\t\t\tcin >> x >> y;\n\t\t\tcout << o.order_of_key({y, MOD}) - o.order_of_key({x - 1, MOD}) << \"\\n\";\n\t\t}\n\t}\n}\n"
          })
        })
      })
    })]
  });
}
function MDXContent(props = {}) {
  const {wrapper: MDXLayout} = props.components || ({});
  return MDXLayout ? _jsx(MDXLayout, {
    ...props,
    children: _jsx(_createMdxContent, {
      ...props
    })
  }) : _createMdxContent(props);
}
return {
  frontmatter,
  default: MDXContent
};
function _missingMdxReference(id, component) {
  throw new Error("Expected " + (component ? "component" : "object") + " `" + id + "` to be defined: you likely forgot to import, pass, or provide it.");
}


Table of Contents

Table of Contents

Solution 1

Solution 2

Join the USACO Forum!