#include <iostream>
#include <deque> // 包含 deque 的头文件

using namespace std;

int main() {
    // 1. 创建一个 deque
    deque<int> dq;

    // 2. 在队尾插入元素
    dq.push_back(10); // dq: [10]
    dq.push_back(20); // dq: [10, 20]

    // 3. 在队头插入元素
    dq.push_front(5);  // dq: [5, 10, 20]
    dq.push_front(1);  // dq: [1, 5, 10, 20]

    // 4. 查看队头和队尾元素
    cout << "队头元素是: " << dq.front() << endl; // 输出 1
    cout << "队尾元素是: " << dq.back() << endl;  // 输出 20

    // 5. 获取队列大小
    cout << "队列大小是: " << dq.size() << endl; // 输出 4

    // 6. 从队头删除元素
    dq.pop_front(); // dq: [5, 10, 20]
    cout << "pop_front 后队头元素是: " << dq.front() << endl; // 输出 5

    // 7. 从队尾删除元素
    dq.pop_back();  // dq: [5, 10]
    cout << "pop_back 后队尾元素是: " << dq.back() << endl;  // 输出 10

    // 8. 判断队列是否为空
    while (!dq.empty()) {
        cout << "当前队头: " << dq.front() << ", 准备出队..." << endl;
        dq.pop_front();
    }

    if (dq.empty()) {
        cout << "队列现在为空。" << endl;
    }

    return 0;
}

// 伪代码：滑动窗口最大值
// 数组 A 的下标从 1 到 n
// 窗口大小为 k
// dq 是一个双端队列，存储的是数组 A 的下标

function slidingWindowMax(A, n, k):
    创建一个空的双端队列 dq
    创建一个空的结果数组 ans

    // 遍历数组 A 的每一个元素
    for i from 1 to n:
        // 规则一：维护单调性
        // 当队列不为空，且队尾下标对应的元素 <= 当前元素 A[i]
        while dq is not empty and A[dq.back()] <= A[i]:
            dq.pop_back() // 弹出队尾，因为它已经没有机会成为最大值了

        // 将当前元素的下标加入队尾
        dq.push_back(i)

        // 规则二：维护窗口范围
        // 如果队头元素的下标已经超出了窗口的左边界
        // 当前窗口的范围是 [i - k + 1, i]
        if dq.front() <= i - k:
            dq.pop_front() // 弹出队头

        // 当窗口形成后（即遍历过的元素个数 >= k），开始记录答案
        if i >= k:
            // 此时队头元素就是当前窗口的最大值
            ans.push_back(A[dq.front()])

    return ans

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

const int MAXN = 1000005;

int n, k;
int a[MAXN];
deque<int> min_dq, max_dq; // min_dq 存最小值的候选项，max_dq 存最大值的候选项

int main() {
    // 读入数据
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    // --- 求滑动窗口最小值 ---
    for (int i = 1; i <= n; ++i) {
        // 维护单调递增性：新来的元素 a[i] 从队尾把比它大的都赶走
        while (!min_dq.empty() && a[min_dq.back()] >= a[i]) {
            min_dq.pop_back();
        }
        min_dq.push_back(i); // 将当前元素下标入队

        // 维护窗口范围：检查队头是否已经滑出窗口
        if (min_dq.front() <= i - k) {
            min_dq.pop_front();
        }

        // 当窗口形成后（i >= k），输出结果
        if (i >= k) {
            cout << a[min_dq.front()] << " ";
        }
    }
    cout << endl;

    // --- 求滑动窗口最大值 ---
    for (int i = 1; i <= n; ++i) {
        // 维护单调递减性：新来的元素 a[i] 从队尾把比它小的都赶走
        while (!max_dq.empty() && a[max_dq.back()] <= a[i]) {
            max_dq.pop_back();
        }
        max_dq.push_back(i); // 将当前元素下标入队

        // 维护窗口范围：检查队头是否已经滑出窗口
        if (max_dq.front() <= i - k) {
            max_dq.pop_front();
        }
        
        // 当窗口形成后（i >= k），输出结果
        if (i >= k) {
            cout << a[max_dq.front()] << " ";
        }
    }
    cout << endl;

    return 0;
}

        节点1 (arr[1])
       /      \
  节点2(arr[2])  节点3(arr[3])
   /     \       /      \
arr[4] arr[5] arr[6] arr[7]

while (index > 1 and heap[index] > heap[index / 2])
    swap(heap[index], heap[index / 2])
    index = index / 2

while (2 * index <= size) // 只要存在子节点
    child_index = 2 * index // 左子节点
    // 如果右子节点存在，且比左子节点大，则目标是右子节点
    if (child_index + 1 <= size and heap[child_index + 1] > heap[child_index])
        child_index = child_index + 1
    
    // 如果当前节点比它的两个孩子都大，则调整结束
    if (heap[index] >= heap[child_index])
        break
    
    swap(heap[index], heap[child_index])
    index = child_index // 继续向下调整

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    // 默认是大根堆
    priority_queue<int> max_heap;

    max_heap.push(30);
    max_heap.push(100);
    max_heap.push(20);

    cout << "大根堆的堆顶元素是: " << max_heap.top() << endl; // 输出 100

    max_heap.pop(); // 弹出 100

    cout << "弹出后，堆顶元素是: " << max_heap.top() << endl; // 输出 30

    return 0;
}

// 定义一个存储 int 类型的小根堆
priority_queue<int, vector<int>, greater<int>> min_heap;

min_heap.push(30);
min_heap.push(100);
min_heap.push(20);

cout << "小根堆的堆顶元素是: " << min_heap.top() << endl; // 输出 20

#include <iostream>
#include <queue>
#include <vector>

// 使用 using namespace std 是为了让初学者更容易理解代码
// 在大型项目中，推荐使用 std:: 前缀
using namespace std;

int main() {
    // 关闭同步流，加速输入输出
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // 定义一个小根堆，因为题目要求我们处理最小值
    priority_queue<int, vector<int>, greater<int>> min_heap;

    for (int i = 1; i <= n; ++i) {
        int op;
        cin >> op;

        if (op == 1) {
            int x;
            cin >> x;
            min_heap.push(x);
        } else if (op == 2) {
            // top() 操作返回的是最小的元素
            cout << min_heap.top() << "\n";
        } else { // op == 3
            // pop() 操作会删除最小的元素
            min_heap.pop();
        }
    }

    return 0;
}

// 预计算 log2 的值，可以加速查询
log_table[1] = 0
for i from 2 to N:
    log_table[i] = log_table[i / 2] + 1

// 初始化 j=0 的情况
for i from 1 to N:
    st[i][0] = A[i]

// j 从 1 开始，表示区间长度从 2^1=2 开始
for j from 1 up to log_table[N]:
    // i 的范围要保证区间 [i, i + 2^j - 1] 不越界
    for i from 1 up to N - (1 << j) + 1:
        st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1])

// 假设 MAXN 是数组最大长度，LOGN 是 log2(MAXN) 的最大值
const int MAXN = 200005;
const int LOGN = 18; // log2(200005) 约等于 17.6

int a[MAXN];
int st[MAXN][LOGN];
int log_table[MAXN];

void build(int n) {
    // 预处理 log_table
    log_table[1] = 0;
    for (int i = 2; i <= n; i++) {
        log_table[i] = log_table[i / 2] + 1;
    }

    // 初始化 j=0
    for (int i = 1; i <= n; i++) {
        st[i][0] = a[i];
    }

    // 递推计算
    for (int j = 1; j <= log_table[n]; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            // st[i][j] = max(st[i][j-1], st[i + 2^(j-1)][j-1])
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query(int l, int r) {
    int len = r - l + 1;
    int k = log_table[len];
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

const int MAXN = 100005;
const int LOGN = 17; // log2(100005) 约等于 16.6

// st[i][j] 表示从 i 开始，长度为 2^j 的区间的最大值
int st[MAXN][LOGN + 1];
int log_table[MAXN];

// 预处理 log 表
void precompute_log(int n) {
    log_table[1] = 0;
    for (int i = 2; i <= n; i++) {
        log_table[i] = log_table[i / 2] + 1;
    }
}

// 构建 ST 表
void build(int n) {
    // j=0 的情况已经在主函数读入时处理
    for (int j = 1; j <= LOGN; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

// 查询 [l, r] 区间的最大值
int query(int l, int r) {
    int k = log_table[r - l + 1];
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

int main() {
    // 加速输入输出
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    precompute_log(n);

    // 读入原始数据，并初始化 st 表 j=0 的情况
    for (int i = 1; i <= n; i++) {
        cin >> st[i][0];
    }

    // O(N log N) 预处理
    build(n);

    // M 次 O(1) 查询
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        cout << query(l, r) << "\n";
    }

    return 0;
}

procedure Initialize(n)
    for i from 1 to n
        fa[i] ← i
    end for
end procedure

function Find(x)
    while fa[x] ≠ x
        x ← fa[x]
    end while
    return x
end function

procedure Union(x, y)
    root_x ← Find(x)
    root_y ← Find(y)
    if root_x ≠ root_y then
        fa[root_x] ← root_y
    end if
end procedure

function Find(x)
    if fa[x] == x then
        return x
    else
        fa[x] ← Find(fa[x])  // 在回溯时将沿途节点的父节点设为根节点
        return fa[x]
    end if
end function

procedure Initialize(n)
    for i from 1 to n
        fa[i] ← i
        siz[i] ← 1  // 初始化每个集合大小为 1
    end for
end procedure

procedure Union(x, y)
    root_x ← Find(x)
    root_y ← Find(y)
    if root_x ≠ root_y then
        // 将小树合并到大树
        if siz[root_x] < siz[root_y] then
            fa[root_x] ← root_y
            siz[root_y] ← siz[root_y] + siz[root_x]
        else
            fa[root_y] ← root_x
            siz[root_x] ← siz[root_x] + siz[root_y]
        end if
    end if
end procedure

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100005; // 假设元素数量不超过 100005

int fa[MAXN]; // 存储父节点
int siz[MAXN]; // 存储以该节点为根的集合的大小

// 初始化 1 到 n 的并查集
void init(int n) {
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
        siz[i] = 1;
    }
}

// 查找x的根节点（带路径压缩）
int find(int x) {
    if (fa[x] == x) {
        return x;
    }
    // 递归查找根节点，同时将路径上的节点直接指向根节点
    return fa[x] = find(fa[x]);
}

// 合并x和y所在的集合（按大小合并）
void unite(int x, int y) {
    int root_x = find(x);
    int root_y = find(y);

    if (root_x != root_y) {
        // 将小集合合并到大集合
        if (siz[root_x] < siz[root_y]) {
            fa[root_x] = root_y;
            siz[root_y] += siz[root_x];
        } else {
            fa[root_y] = root_x;
            siz[root_x] += siz[root_y];
        }
    }
}

// 判断x和y是否在同一个集合
bool is_same_set(int x, int y) {
    return find(x) == find(y);
}

int main() {
    // 这是一个使用示例，并非完整题目代码
    int n = 10; // 假设有 10 个元素
    init(n);

    unite(1, 2);
    unite(3, 4);
    unite(1, 3);

    if (is_same_set(2, 4)) {
        cout << "元素2和元素4在同一个集合中。" << endl;
    } else {
        cout << "元素2和元素4不在同一个集合中。" << endl;
    }

    if (is_same_set(1, 5)) {
        cout << "元素1和元素5在同一个集合中。" << endl;
    } else {
        cout << "元素1和元素5不在同一个集合中。" << endl;
    }

    return 0;
}

#include <iostream>

using namespace std;

const int MAXN = 10001; // 题目数据范围 N <= 10000

int fa[MAXN];
int siz[MAXN]; // 按大小合并的辅助数组，本题也可不用，但好习惯

void init(int n) {
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
        siz[i] = 1; // 即使不用按大小合并，初始化fa数组是必须的
    }
}

int find(int x) {
    if (fa[x] == x) {
        return x;
    }
    return fa[x] = find(fa[x]); // 路径压缩
}

void unite(int x, int y) {
    int root_x = find(x);
    int root_y = find(y);
    if (root_x != root_y) {
        // 直接合并，不使用按大小合并也足以通过本题
        fa[root_x] = root_y;
    }
}

int main() {
    // 为了提高读写效率
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    init(n);

    for (int i = 0; i < m; ++i) {
        int z, x, y;
        cin >> z >> x >> y;
        if (z == 1) {
            unite(x, y);
        } else { // z == 2
            if (find(x) == find(y)) {
                cout << "Y" << '\n';
            } else {
                cout << "N" << '\n';
            }
        }
    }

    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 1000005;

int h[MAXN]; // 数组模拟堆，从下标1开始
int heap_size = 0; // 堆中元素的数量

// 上浮操作，调整位置idx的元素
void sift_up(int idx) {
    // 当idx不是根节点(idx > 1) 且 当前节点比父节点小
    while (idx > 1 && h[idx] < h[idx / 2]) {
        swap(h[idx], h[idx / 2]);
        idx /= 2; // 继续向上看
    }
}

// 下沉操作，调整位置idx的元素
void sift_down(int idx) {
    while (2 * idx <= heap_size) { // 保证idx有左孩子
        int son = 2 * idx; // son先指向左孩子
        // 如果右孩子存在，且比左孩子更小，则son指向右孩子
        if (son + 1 <= heap_size && h[son + 1] < h[son]) {
            son++;
        }
        
        // 如果当前节点比它的两个孩子中较小的那个还要小，则满足堆序性，停止下沉
        if (h[idx] <= h[son]) {
            break;
        }
        
        // 否则，交换并继续下沉
        swap(h[idx], h[son]);
        idx = son;
    }
}

// 插入一个元素
void push(int val) {
    heap_size++;
    h[heap_size] = val;
    sift_up(heap_size);
}

// 删除堆顶元素
void pop() {
    if (heap_size == 0) return; // 堆为空
    h[1] = h[heap_size]; // 将最后一个元素移到堆顶
    heap_size--;
    sift_down(1); // 对新的堆顶执行下沉操作
}

// 获取堆顶元素
int top() {
    if (heap_size > 0) {
        return h[1];
    }
    return -1; // 表示堆为空
}

// 检查堆是否为空
bool empty() {
    return heap_size == 0;
}

int main() {
    // 使用示例
    push(30);
    push(10);
    push(20);
    push(5);

    while (!empty()) {
        cout << top() << " ";
        pop();
    }
    // 输出应为: 5 10 20 30
    cout << endl;

    return 0;
}

#include <queue> // 使用STL中的priority_queue
// priority_queue<int> max_heap; // 默认是大根堆
// priority_queue<int, vector<int>, greater<int>> min_heap; // 小根堆

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 1000005;

int h[MAXN];
int heap_size = 0;

void sift_up(int idx) {
    while (idx > 1 && h[idx] < h[idx / 2]) {
        swap(h[idx], h[idx / 2]);
        idx /= 2;
    }
}

void sift_down(int idx) {
    while (2 * idx <= heap_size) {
        int son = 2 * idx;
        if (son + 1 <= heap_size && h[son + 1] < h[son]) {
            son++;
        }
        if (h[idx] <= h[son]) {
            break;
        }
        swap(h[idx], h[son]);
        idx = son;
    }
}

void push(int val) {
    heap_size++;
    h[heap_size] = val;
    sift_up(heap_size);
}

void pop() {
    if (heap_size > 0) {
        h[1] = h[heap_size];
        heap_size--;
        sift_down(1);
    }
}

int top() {
    if (heap_size > 0) {
        return h[1];
    }
    return -1; // 题目保证操作合法，不会在空堆时查询
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            push(x);
        } else if (op == 2) {
            cout << top() << '\n';
        } else { // op == 3
            pop();
        }
    }

    return 0;
}

procedure Add(x, k)
    while x ≤ n
        C[x] ← C[x] + k
        x ← x + lowbit(x)
    end while
end procedure

function Query(x)
    sum ← 0
    while x > 0
        sum ← sum + C[x]
        x ← x - lowbit(x)
    end while
    return sum
end function

#include <iostream>

using namespace std;

const int MAXN = 500005;

int n; // 数组大小
long long c[MAXN]; // 树状数组，注意数据范围可能需要long long

// lowbit函数
int lowbit(int x) {
    return x & (-x);
}

// 单点增加：给A[x]增加k
void add(int x, int k) {
    while (x <= n) {
        c[x] += k;
        x += lowbit(x);
    }
}

// 前缀和查询：查询A[1]到A[x]的和
long long query(int x) {
    long long sum = 0;
    while (x > 0) {
        sum += c[x];
        x -= lowbit(x);
    }
    return sum;
}

int main() {
    // 使用示例
    n = 10;
    // 假设原数组 A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    // 初始化树状数组
    for (int i = 1; i <= n; ++i) {
        int val;
        // 假设这里能读到原数组的值
        // cin >> val;
        val = i;
        add(i, val);
    }

    // 查询前5个数的和 (1+2+3+4+5 = 15)
    cout << "Sum of first 5 elements: " << query(5) << endl;

    // 给第3个数加上5 (A[3]从3变为8)
    add(3, 5);
    
    // 再次查询前5个数的和 (1+2+8+4+5 = 20)
    cout << "Sum of first 5 elements after update: " << query(5) << endl;
    
    // 查询区间[3, 7]的和
    // A数组现在是 {1, 2, 8, 4, 5, 6, 7, 8, 9, 10}
    // Sum[3,7] = 8+4+5+6+7 = 30
    // query(7) - query(2)
    cout << "Sum of range [3, 7]: " << query(7) - query(2) << endl;
    
    return 0;
}

#include <iostream>

using namespace std;

const int MAXN = 500005;

int n, m;
long long c[MAXN];

int lowbit(int x) {
    return x & (-x);
}

void add(int x, int k) {
    while (x <= n) {
        c[x] += k;
        x += lowbit(x);
    }
}

long long query(int x) {
    long long sum = 0;
    while (x > 0) {
        sum += c[x];
        x -= lowbit(x);
    }
    return sum;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    // 初始化树状数组
    for (int i = 1; i <= n; ++i) {
        int val;
        cin >> val;
        add(i, val);
    }

    for (int i = 0; i < m; ++i) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            add(x, y); // y在这里是增量k
        } else { // op == 2
            cout << query(y) - query(x - 1) << '\n';
        }
    }

    return 0;
}

BUILD(p, L, R)
  // p 是当前节点编号，[L, R] 是它代表的区间
  IF L == R THEN
    tree[p] = A[L]
    RETURN
  END IF
  
  M = (L + R) / 2
  BUILD(2*p, L, M)        // 递归建左子树
  BUILD(2*p+1, M+1, R)    // 递归建右子树
  tree[p] = tree[2*p] + tree[2*p+1] // 用子节点信息更新当前节点

UPDATE(p, L, R, idx, val)
  // p: 当前节点编号, [L,R]: 当前区间
  // idx: 要修改的元素下标, val: 新的值
  IF L == R THEN
    tree[p] = val
    RETURN
  END IF
  
  M = (L + R) / 2
  IF idx <= M THEN
    UPDATE(2*p, L, M, idx, val) // idx 在左子区间
  ELSE
    UPDATE(2*p+1, M+1, R, idx, val) // idx 在右子区间
  END IF
  
  tree[p] = tree[2*p] + tree[2*p+1] // 回溯时更新父节点

QUERY(p, L, R, queryL, queryR)
  // p: 当前节点, [L,R]: 当前区间
  // [queryL, queryR]: 目标查询区间
  
  // 1. 完全包含
  IF queryL <= L AND R <= queryR THEN
    RETURN tree[p]
  END IF
  
  // 2. (隐式) 无交集的情况会在下面递归中处理，最终返回 0
  
  M = (L + R) / 2
  sum = 0
  
  // 3. 部分交集，需要递归
  IF queryL <= M THEN // 左子树与查询区间有交集
    sum = sum + QUERY(2*p, L, M, queryL, queryR)
  END IF
  
  IF queryR > M THEN // 右子树与查询区间有交集
    sum = sum + QUERY(2*p+1, M+1, R, queryL, queryR)
  END IF
  
  RETURN sum

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100005;

long long a[MAXN];      // 原始数组，下标从1开始
long long tree[MAXN * 4]; // 线段树数组
long long tag[MAXN * 4];  // 懒惰标记数组
int n; // 元素个数

// 用子节点信息更新父节点
void push_up(int p) {
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
}

// 下放懒惰标记
void push_down(int p, int l, int r) {
    if (tag[p] != 0) {
        int mid = (l + r) / 2;
        // 更新左子节点的值和标记
        tree[p * 2] += tag[p] * (mid - l + 1);
        tag[p * 2] += tag[p];
        // 更新右子节点的值和标记
        tree[p * 2 + 1] += tag[p] * (r - (mid + 1) + 1);
        tag[p * 2 + 1] += tag[p];
        // 清除当前节点的标记
        tag[p] = 0;
    }
}

// 建树
void build(int p, int l, int r) {
    if (l == r) {
        tree[p] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    push_up(p);
}

// 区间修改：将区间 [update_l, update_r] 内的数都加上 val
void update(int p, int l, int r, int update_l, int update_r, int val) {
    if (update_l <= l && r <= update_r) { // 完全覆盖
        tree[p] += (long long)(r - l + 1) * val;
        tag[p] += val;
        return;
    }
    
    push_down(p, l, r); // 准备访问子节点，先下放标记
    
    int mid = (l + r) / 2;
    if (update_l <= mid) {
        update(p * 2, l, mid, update_l, update_r, val);
    }
    if (update_r > mid) {
        update(p * 2 + 1, mid + 1, r, update_l, update_r, val);
    }
    
    push_up(p); // 用更新后的子节点信息更新自己
}

// 区间查询：查询区间 [query_l, query_r] 的和
long long query(int p, int l, int r, int query_l, int query_r) {
    if (query_l <= l && r <= query_r) { // 完全覆盖
        return tree[p];
    }
    
    push_down(p, l, r); // 准备访问子节点，先下放标记
    
    int mid = (l + r) / 2;
    long long sum = 0;
    if (query_l <= mid) {
        sum += query(p * 2, l, mid, query_l, query_r);
    }
    if (query_r > mid) {
        sum += query(p * 2 + 1, mid + 1, r, query_l, query_r);
    }
    return sum;
}

int main() {
    // 使用示例
    int m; // 操作次数
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    build(1, 1, n);

    for (int i = 0; i < m; ++i) {
        int type;
        cin >> type;
        if (type == 1) { // 区间修改
            int l, r, val;
            cin >> l >> r >> val;
            update(1, 1, n, l, r, val);
        } else { // 区间查询
            int l, r;
            cin >> l >> r;
            cout << query(1, 1, n, l, r) << endl;
        }
    }

    return 0;
}

      (root)
      /    \
     c      d
     |      |
     a      o
    / \     |
   t*  r*   g*
   |
   c
   |
   h*

INSERT(str)
  p = ROOT
  FOR ch IN str DO
    IF trie[p][ch] IS NULL THEN
      newNode = GET_NEW_NODE()
      trie[p][ch] = newNode
    END IF
    p = trie[p][ch]
  END FOR
  end_count[p] = end_count[p] + 1

SEARCH(str)
  p = ROOT
  FOR ch IN str DO
    IF trie[p][ch] IS NULL THEN
      RETURN false
    END IF
    p = trie[p][ch]
  END FOR
  RETURN (end_count[p] > 0)

#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int MAX_NODES = 100005; // 估算最大节点数（字符串总长）
const int CHARSET_SIZE = 26; // 字符集大小

int trie[MAX_NODES][CHARSET_SIZE];
int end_count[MAX_NODES];
int node_count; // 已使用的节点数量

// 初始化Trie树
void init() {
    // C++中全局数组默认初始化为0，这里可以省略memset
    // memset(trie, 0, sizeof(trie));
    // memset(end_count, 0, sizeof(end_count));
    node_count = 1; // 0号节点作为根节点
}

// 插入字符串
void insert(const string& s) {
    int p = 0; // 从根节点开始
    for (char ch : s) {
        int c = ch - 'a'; // 将字符映射到 0-25
        if (trie[p][c] == 0) {
            trie[p][c] = node_count++;
        }
        p = trie[p][c];
    }
    end_count[p]++;
}

// 查询字符串
bool search(const string& s) {
    int p = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (trie[p][c] == 0) {
            return false;
        }
        p = trie[p][c];
    }
    return end_count[p] > 0;
}

int main() {
    init();

    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        insert(s);
    }

    int m;
    cin >> m;
    for (int i = 0; i < m; ++i) {
        string s;
        cin >> s;
        if (search(s)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

    return 0;
}

          (2, 1)
         /      \
      (1, 3)    (6, 2)
               /      \
            (4, 4)    (7, 6)
             /  \
           (3, 5) (5, 9)

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

const int MAXN = 1000005;

struct Node {
    int val;
    int l_child, r_child;
};

Node tree[MAXN];
int val[MAXN];
int l_child[MAXN], r_child[MAXN];
int n;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> val[i];
    }

    stack<int> s;
    for (int i = 1; i <= n; ++i) {
        int last_pop = 0;
        // 当栈不空且栈顶元素值大于当前元素值
        while (!s.empty() && val[s.top()] > val[i]) {
            last_pop = s.top();
            s.pop();
        }

        if (!s.empty()) {
            // 栈顶是父节点，当前节点是其右孩子
            r_child[s.top()] = i;
        }

        // 最后一个弹出的节点是当前节点的左孩子
        l_child[i] = last_pop;
        
        s.push(i);
    }
    
    // 找到根节点（没有父节点的节点）
    // 在这个建树方法中，根是整个序列中最小值的下标
    // 或者可以通过一个 parent 数组来找，谁的 parent 是 0 谁就是根
    // P5854 模板题的输出要求比较特殊，需要计算哈希值
    long long ans1 = 0, ans2 = 0;
    for(int i = 1; i <= n; ++i) {
        ans1 ^= (long long)i * (l_child[i] + 1);
        ans2 ^= (long long)i * (r_child[i] + 1);
    }

    cout << ans1 << " " << ans2 << endl;

    return 0;
}

struct Node {
    int val;    // 节点的值
    int height; // 以当前节点为根的子树的高度
    Node *left, *right; // 左右孩子指针
};

function insert(node, value):
    if node is null:
        return create_new_node(value)

    if value < node.val:
        node.left = insert(node.left, value)
    else if value > node.val:
        node.right = insert(node.right, value)
    else: // 值已存在，不插入
        return node
    
    // 1. 更新高度
    update_height(node)

    // 2. 获取平衡因子，检查是否失衡
    balance = get_balance_factor(node)

    // 3. 如果失衡，进行旋转调整 (四种情况)
    // LL Case
    if balance < -1 and value < node.left.val:
        return right_rotate(node)
    
    // RR Case
    if balance > 1 and value > node.right.val:
        return left_rotate(node)

    // LR Case
    if balance < -1 and value > node.left.val:
        node.left = left_rotate(node.left)
        return right_rotate(node)

    // RL Case
    if balance > 1 and value < node.right.val:
        node.right = right_rotate(node.right)
        return left_rotate(node)

    // 4. 如果未失衡，直接返回当前节点
    return node

#include <iostream>
#include <cstdlib> // For rand()
#include <ctime>   // For srand()

using namespace std;

// 建议在程序开始时调用 srand(time(0)) 来初始化随机数种子

struct Node {
    int val;      // BST 的键值
    int priority; // 堆的优先级
    int size;     // 子树大小（用于查询排名等）
    Node *ch[2];  // ch[0] 是左孩子, ch[1] 是右孩子

    Node(int v) {
        val = v;
        priority = rand();
        size = 1;
        ch[0] = ch[1] = nullptr;
    }
};

// 更新节点 size 信息
void pushup(Node* p) {
    p->size = 1;
    if (p->ch[0]) p->size += p->ch[0]->size;
    if (p->ch[1]) p->size += p->ch[1]->size;
}

// 旋转操作 (d=0 右旋, d=1 左旋)
// d=0: 将 p 的左孩子(ch[0]) 旋上来
// d=1: 将 p 的右孩子(ch[1]) 旋上来
void rotate(Node* &p, int d) {
    Node* k = p->ch[d^1]; // d=0, k=p->ch[1]; d=1, k=p->ch[0]
    p->ch[d^1] = k->ch[d];
    k->ch[d] = p;
    pushup(p);
    pushup(k);
    p = k;
}

// 插入操作
void insert(Node* &p, int val) {
    if (!p) {
        p = new Node(val);
        return;
    }
    if (val == p->val) return; // 假设不插入重复值
    
    int d = (val > p->val); // d=0 插入左子树, d=1 插入右子树
    insert(p->ch[d], val);

    // 维护堆性质
    if (p->ch[d]->priority > p->priority) {
        rotate(p, d^1); // 如果右孩子(d=1)优先级大，需要左旋(d^1=0)
                        // 如果左孩子(d=0)优先级大，需要右旋(d^1=1)
                        // 这里有个小技巧，可以思考一下
    }
    pushup(p);
}

// 删除操作
void remove(Node* &p, int val) {
    if (!p) return;
    if (val < p->val) {
        remove(p->ch[0], val);
    } else if (val > p->val) {
        remove(p->ch[1], val);
    } else { // 找到了要删除的节点 p
        if (!p->ch[0] && !p->ch[1]) { // 叶子节点
            delete p;
            p = nullptr;
        } else if (!p->ch[0]) { // 只有右孩子
            Node* k = p;
            p = p->ch[1];
            delete k;
        } else if (!p->ch[1]) { // 只有左孩子
            Node* k = p;
            p = p->ch[0];
            delete k;
        } else { // 有两个孩子
            int d = (p->ch[0]->priority < p->ch[1]->priority); // 哪个孩子优先级大，就把它旋上来
            rotate(p, d);
            remove(p->ch[d], val); // 继续在旋转下去的子树中删除
        }
    }
    if (p) pushup(p);
}

#include <iostream>
#include <algorithm>

using namespace std;

struct Node {
    int val;
    int size;
    Node *ch[2]; // ch[0] left, ch[1] right
    Node *fa;    // parent pointer

    Node(int v, Node* f) {
        val = v;
        size = 1;
        ch[0] = ch[1] = nullptr;
        fa = f;
    }
};

Node* root;

void pushup(Node* p) {
    p->size = 1;
    if (p->ch[0]) p->size += p->ch[0]->size;
    if (p->ch[1]) p->size += p->ch[1]->size;
}

// d=0: 左孩子, d=1: 右孩子
// get(x) 判断 x 是其父节点的哪个孩子
int get(Node* p) {
    return p == p->fa->ch[1];
}

void rotate(Node* p) {
    Node *f = p->fa, *gf = f->fa;
    int d = get(p);
    
    // 连接 gf 和 p
    if (gf) gf->ch[get(f)] = p;
    p->fa = gf;

    // 连接 f 和 p 的子树
    f->ch[d] = p->ch[d^1];
    if (p->ch[d^1]) p->ch[d^1]->fa = f;
    
    // 连接 p 和 f
    p->ch[d^1] = f;
    f->fa = p;

    pushup(f);
    pushup(p);
}

void splay(Node* p, Node* goal = nullptr) {
    while (p->fa != goal) {
        Node *f = p->fa, *gf = f->fa;
        if (gf != goal) { // 如果有祖父节点，判断 zig-zig or zig-zag
            if (get(p) == get(f)) { // zig-zig
                rotate(f);
            } else { // zig-zag
                rotate(p);
            }
        }
        rotate(p);
    }
    if (goal == nullptr) { // 如果目标是根，更新 root 指针
        root = p;
    }
}

function Numeric_Hash(key, M):
  // key: 输入的数值
  // M:   模数，通常是一个质数
  return key mod M

#include <iostream>

using namespace std;

// M 通常选择一个质数，例如 100003
const int M = 100003; 

/**
 * @brief 计算数值的哈希值
 * @param key 输入的整数
 * @return key 对 M 取模后的哈希值
 */
int get_hash(int key) {
    // 为了防止 key 是负数，C++ 的负数取模结果可能也是负数
    // 通过 (key % M + M) % M 的方式确保结果为非负数
    return (key % M + M) % M;
}

int main() {
    int student_id = 20240321;
    int hash_value = get_hash(student_id);
    
    // 学号 20240321 对应的哈希值为：20240321 % 100003 = 20182
    cout << "学号 " << student_id << " 的哈希值是: " << hash_value << endl;
    
    return 0;
}

// --- 预处理 ---
function Precompute_Hash(S, n, P, M):
  h[0] = 0
  p[0] = 1
  for i from 1 to n:
    p[i] = (p[i-1] * P) mod M
    h[i] = (h[i-1] * P + S[i]) mod M

// --- 查询子串哈希 ---
function Get_Substring_Hash(l, r):
  // 计算 S[l..r] 的哈希值
  len = r - l + 1
  hash_val = (h[r] - h[l-1] * p[len] % M + M) % M
  return hash_val