Has Not Appeared
0/6
Counting Minimums with Segment Tree
Authors: Benjamin Qi, Dustin Miao
Querying for the minimum and number of occurences of minimum in a range
Prerequisites
Focus Problem – try your best to solve this problem before continuing!
Resources | ||||
---|---|---|---|---|
cp-algo |
We would like a data structure that can efficiently handle two types of operations:
- Update index to value
- Report the minimum and the number of occurences of the minimum on a range
We can use a normal segment tree to handle range queries, but slightly modify each node and the merge operation. Let each node be a pair of values , where is the minimum value and is the number occurences of the minimum value.
If node has two children and , then
- if , then
- if , then
- if , then
Implementation
C++
const int MAXN = 2e5;struct Node {int val = INT32_MAX, cnt = 1;} tree[2 * MAXN];// combines two segment tree nodesNode merge(Node a, Node b) {if (a.val < b.val) {return a;
Solution - Area of Rectangles
Hint 1
Hint 2
Solution
Implementation
C++
#include <bits/stdc++.h>using namespace std;const int MAXX = 1e6;const int MAXN = 2 * MAXX + 1;struct Event {int t, x, y0, y1;// t = 1 for left bound, -1 for right boundbool operator<(const Event &e) { return x < e.x; }
Problems
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
CF | Easy | Show TagsDP | |||
mBIT | Normal | ||||
IOI | Hard | ||||
HR | Hard | Show TagsLazy SegTree | |||
CF | Very Hard |
Optional: Permutation Tree
Module Progress:
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!