输入：01B0
过程："" → "0" → "01" → "0" → "00"
输出：00

输入：0BB1
过程："" → "0" → "" → "" → "1"
输出：1

import java.util.ArrayList;
import java.util.Scanner;

public class A_soln {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        ArrayList<Character> arrayList = new ArrayList<>();
        for (char i : s) {
            switch (i) {
                case '0':
                    arrayList.add('0');
                    break;
                case '1':
                    arrayList.add('1');
                    break;
                default:
                    if (!arrayList.isEmpty()) arrayList.removeLast();
            }
        }
        for (char i : arrayList) {
            System.out.print(i);
        }
    }
}

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string s;
    cin >> s;

    vector<char> stk;  // 用 vector 模拟栈

    for (char c : s) {
        if (c == '0' || c == '1') {
            // 按 0 或 1 → 压栈（追加到末尾）
            stk.push_back(c);
        } else {  // c == 'B'，退格
            // 栈非空时才弹栈，防止越界
            if (!stk.empty()) {
                stk.pop_back();  // 删除最后一个字符 = pop
            }
        }
    }

    // 输出最终栈中所有字符（从栈底到栈顶）
    for (char c : stk) {
        cout << c;
    }
    cout << endl;

    return 0;
}

vector<char> stk;  // 用 vector 模拟栈

for (char c : s) {
    if (c == '0' || c == '1') {
        stk.push_back(c);    // push
    } else {
        if (!stk.empty()) {
            stk.pop_back();  // pop（需判空）
        }
    }
}

for (char c : stk) {
    cout << c;
}

输入：3
     acornistnt / peanutbomb / constraint
输出：1
解释："acornistnt" 和 "constraint" 互为 anagram

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class B_soln {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        HashMap<String, Integer> map = new HashMap<>();
        long ans = 0;

        for (int i = 0; i < n; i++) {
            char[] s = sc.next().toCharArray();
            int[] arr = new int[10];
            for (int j = 0; j < 10; j++) {
                arr[j] = s[j];
            }
            arr = Arrays.stream(arr).sorted().toArray();
            String stringArr = Arrays.toString(arr);

            if (map.containsKey(stringArr)) {
                map.put(stringArr, map.get(stringArr) + 1);
            } else {
                map.put(stringArr, 1);
            }
        }

        for (int i : map.values()) {
            ans += (long) i * (i - 1) / 2;
        }
        System.out.println(ans);
    }
}

#include <iostream>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin >> N;

    unordered_map<string, long long> freq;  // 标准形式 → 出现次数
    string s;

    for (int i = 0; i < N; i++) {
        cin >> s;

        // 将字符串排序，得到"标准形式"（anagram 的唯一代表）
        sort(s.begin(), s.end());

        // 频次 +1
        freq[s]++;
    }

    // 统计答案：每组 size=c 的 anagram 贡献 C(c, 2) 对
    long long ans = 0;
    for (auto& p : freq) {
        long long c = p.second;
        ans += c * (c - 1) / 2;
    }

    cout << ans << endl;
    return 0;
}

unordered_map<string, long long> freq;

sort(s.begin(), s.end());
freq[s]++;

for (auto& p : freq) {
    long long c = p.second;
    ans += c * (c - 1) / 2;
}

输入：
7
1 5      → 加蛇(长5)，坐标 0
1 7      → 加蛇(长7)，坐标 0+5=5
3 2      → 第2条蛇坐标 → 5
1 3      → 加蛇(长3)，坐标 5+7=12
1 4      → 加蛇(长4)，坐标 12+3=15
2        → 队首离开(长5)，剩余坐标均-5
3 3      → 第3条蛇坐标 → 10

输出：5 / 10

import java.util.ArrayList;
import java.util.Scanner;

public class C_soln {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();

        ArrayList<Long> arrayList = new ArrayList<>();
        arrayList.add(0L);
        int size = 1;

        for (int i = 0; i < q; i++) {
            switch (sc.nextInt()) {
                case 1:
                    if (size == 0) {
                        arrayList.add(sc.nextLong());
                        size++;
                    } else {
                        arrayList.addLast(arrayList.get(size - 1) + sc.nextLong());
                        size++;
                    }
                    break;
                case 2:
                    arrayList.removeFirst();
                    size--;
                    break;
                default:
                    System.out.println(arrayList.get(sc.nextInt() - 1) - arrayList.getFirst());
            }
        }
    }
}

#include <iostream>
#include <deque>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int Q;
    cin >> Q;

    deque<ll> dq;       // 双端队列，存前缀和（原始绝对坐标）
    dq.push_back(0);    // 哨兵：初始原点（相当于已离开蛇总长 = 0）

    while (Q--) {
        int type;
        cin >> type;

        if (type == 1) {
            ll len;
            cin >> len;
            // 新蛇的原始头部坐标 = 上一条原始坐标 + 上一条长度
            // 即：当前队列最后一个前缀和 + 新蛇长度
            dq.push_back(dq.back() + len);
        }
        else if (type == 2) {
            // 队首蛇离开 → 对应的前缀和被移除
            // 此后队列首元素 dq.front() 自动成为新的"偏移基准"
            dq.pop_front();
        }
        else {  // type == 3
            int k;
            cin >> k;
            // 第 k 条蛇的前缀和 - 当前队首前缀和（偏移量）
            // dq[k-1] 不用 +1 因为队首是哨兵（或已离开蛇的总长）
            cout << dq[k - 1] - dq.front() << '\n';
        }
    }
    return 0;
}

deque<ll> dq;
dq.push_back(0);    // 哨兵

// type 1: 队尾入队
dq.push_back(dq.back() + len);

初始：dq = [0]
加蛇(长5) → dq = [0, 0+5] = [0, 5]
加蛇(长7) → dq = [0, 5, 5+7] = [0, 5, 12]

// type 2: 队首出队
dq.pop_front();

出队前：dq = [0, 5, 12, 15]
                    ↑ 已离开蛇总长=0（哨兵）

pop_front() 后：dq = [5, 12, 15]
                      ↑ 已离开蛇总长=5（原来的 dq[1] 变成了新的队首）

// type 3: 查询第 k 条蛇的头部坐标
cout << dq[k - 1] - dq.front() << '\n';

输入：3 3
     2 13 8
输出：9
解释：2円不用券，13→3(2张)，8→4(1张)，总计 2+3+4=9

输入：1 100000
     1000000000
输出：0
解释：10⁹ 用 10⁵ 张券，不断÷2 最终归 0

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class D_soln {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());

        for (int i = 0; i < n; i++) {
            pq.add(sc.nextInt());
        }

        for (int i = 0; i < m; i++) {
            pq.add(pq.poll() / 2);
        }

        long ans = 0L;
        for (int i : pq.stream().toList()) {
            ans += i;
        }
        System.out.println(ans);
    }
}

#include <iostream>
#include <queue>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    // 大顶堆：堆顶始终是当前最贵的商品
    priority_queue<ll> pq;

    for (int i = 0; i < N; i++) {
        ll price;
        cin >> price;
        pq.push(price);
    }

    // 每次取最贵的商品打折
    while (M--) {
        ll top = pq.top();   // O(1)：查看当前最贵价格
        pq.pop();            // O(log N)：弹出
        pq.push(top / 2);    // O(log N)：打折后放回
    }

    // 求和所有剩余价格
    ll ans = 0;
    while (!pq.empty()) {
        ans += pq.top();
        pq.pop();
    }

    cout << ans << endl;
    return 0;
}

priority_queue<ll> pq;

while (M--) {
    ll top = pq.top();   // 查看堆顶（最大值）
    pq.pop();            // 弹出堆顶
    pq.push(top / 2);    // 半价后放回
}

ll ans = 0;
while (!pq.empty()) {
    ans += pq.top();
    pq.pop();
}

输入：5
     1 1 / 1 1 / 2 1 / 1 2 / 1 4
输出：4
解释：时刻1 印商品4，时刻2 印商品1，时刻3 印商品3，时刻4 印商品5

import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Collections;

public class E_soln {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        HashMap<Long, ArrayList<Long>> hashMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            long t = sc.nextLong();
            long d = sc.nextLong();
            long leaveTime = t + d;
            if (hashMap.containsKey(t)) {
                hashMap.get(t).add(leaveTime);
            } else {
                ArrayList<Long> list = new ArrayList<>();
                list.add(leaveTime);
                hashMap.put(t, list);
            }
        }

        ArrayList<Long> entryTimes = new ArrayList<>(hashMap.keySet());
        Collections.sort(entryTimes);

        PriorityQueue<Long> current = new PriorityQueue<>();
        int ans = 0;
        long currentTime = 0;
        int timeIndex = 0;

        while (timeIndex < entryTimes.size() || !current.isEmpty()) {
            if (current.isEmpty()) {
                currentTime = Math.max(currentTime, entryTimes.get(timeIndex));
            }
            while (timeIndex < entryTimes.size() && entryTimes.get(timeIndex) <= currentTime) {
                long entryT = entryTimes.get(timeIndex);
                for (long leaveTime : hashMap.get(entryT)) {
                    current.add(leaveTime);
                }
                timeIndex++;
            }
            if (current.isEmpty()) continue;

            long earliestLeave = current.poll();
            if (earliestLeave < currentTime) continue;

            ans++;
            currentTime++;
        }

        System.out.println(ans);
    }
}

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    // 将每个商品的 (进入时间, 离开时间) 存入 vector
    vector<pair<ll, ll>> products(N);
    for (int i = 0; i < N; i++) {
        ll t, d;
        cin >> t >> d;
        products[i] = {t, t + d};  // {进入时间, 离开时间}
    }

    // 按进入时间升序排序
    sort(products.begin(), products.end());

    // 小顶堆，维护"当前在范围内"商品的离开时间
    priority_queue<ll, vector<ll>, greater<ll>> pq;

    int idx = 0;           // 指向下一个还没进入范围的商品
    int ans = 0;
    ll curTime = 0;        // 打印机下一次可用的时刻

    // 扫描线主循环
    while (idx < N || !pq.empty()) {

        // ① 空闲跳转：堆空说明没有可印的商品，时间跳到下一个商品进入时刻
        if (pq.empty()) {
            curTime = max(curTime, products[idx].first);
        }

        // ② 入堆：把 curTime 之前（含）进入的商品全部入堆
        while (idx < N && products[idx].first <= curTime) {
            pq.push(products[idx].second);  // 按离开时间入小顶堆
            idx++;
        }

        // ③ 过期丢弃：堆顶商品已过期（离开时间 < 当前时刻）→ 丢弃
        while (!pq.empty() && pq.top() < curTime) {
            pq.pop();
        }

        // ④ 印刷：堆顶是离开最早且未过期的商品
        if (!pq.empty()) {
            pq.pop();
            ans++;
            curTime++;  // 印刷消耗 1 微秒
        }
    }

    cout << ans << endl;
    return 0;
}

vector<pair<ll, ll>> products(N);
for (int i = 0; i < N; i++) {
    ll t, d;
    cin >> t >> d;
    products[i] = {t, t + d};  // {进入时间, 离开时间}
}
sort(products.begin(), products.end());

priority_queue<ll, vector<ll>, greater<ll>> pq;

// ① 空闲跳转
if (pq.empty()) {
    curTime = max(curTime, products[idx].first);
}

// ② 入堆
while (idx < N && products[idx].first <= curTime) {
    pq.push(products[idx].second);
    idx++;
}

// ③ 过期丢弃
while (!pq.empty() && pq.top() < curTime) {
    pq.pop();
}

// ④ 印刷
if (!pq.empty()) {
    pq.pop();
    ans++;
    curTime++;
}

while (还有商品未进入 或 堆非空):
    ┌─ ① 堆空 → 跳到下一个商品进入时间
    ├─ ② 把 curTime 之前进入的商品入堆
    ├─ ③ 堆顶已过期 → 弹出丢弃
    └─ ④ 堆顶有效 → 印刷，ans++，curTime++

输入：4 2
     3 5 1 2
输出：3
解释：(3, 1, 2)，|3-1|=2≤2，|1-2|=1≤2

输入：5 10
     10 20 100 110 120
输出：3
解释：(100, 110, 120) 或 (10, 20, 100)

import java.util.Scanner;

public class F_soln {
    static final int MAX_VAL = 500000;
    static int[] segTree;

    static void update(int node, int start, int end, int pos, int val) {
        if (start == end) {
            segTree[node] = Math.max(segTree[node], val);
        } else {
            int mid = (start + end) / 2;
            if (pos <= mid) {
                update(2 * node, start, mid, pos, val);
            } else {
                update(2 * node + 1, mid + 1, end, pos, val);
            }
            segTree[node] = Math.max(segTree[2 * node], segTree[2 * node + 1]);
        }
    }

    static int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0;
        if (l <= start && end <= r) return segTree[node];
        int mid = (start + end) / 2;
        int leftMax = query(2 * node, start, mid, l, r);
        int rightMax = query(2 * node + 1, mid + 1, end, l, r);
        return Math.max(leftMax, rightMax);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int D = sc.nextInt();

        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }

        segTree = new int[MAX_VAL * 4];
        int globalMax = 0;

        for (int val : A) {
            int L = Math.max(1, val - D);
            int R = Math.min(MAX_VAL, val + D);
            int maxLen = query(1, 1, MAX_VAL, L, R);
            int currentLen = maxLen + 1;
            update(1, 1, MAX_VAL, val, currentLen);
            if (currentLen > globalMax) {
                globalMax = currentLen;
            }
        }

        System.out.println(globalMax);
    }
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_VAL = 500000;       // A_i 的最大可能值
vector<int> segTree(MAX_VAL * 4); // 4 倍空间保证不越界

// 线段树：单点更新 —— 将位置 pos 的值更新为 val（取 max）
void update(int node, int start, int end, int pos, int val) {
    if (start == end) {
        // 到达叶子节点 [pos, pos]
        segTree[node] = max(segTree[node], val);
        return;
    }
    int mid = (start + end) / 2;
    if (pos <= mid) {
        update(node * 2, start, mid, pos, val);       // 进左子树
    } else {
        update(node * 2 + 1, mid + 1, end, pos, val);  // 进右子树
    }
    // 回溯：父节点 = max(左孩子, 右孩子)
    segTree[node] = max(segTree[node * 2], segTree[node * 2 + 1]);
}

// 线段树：区间查询 —— 查询区间 [l, r] 的最大值
int query(int node, int start, int end, int l, int r) {
    // 情况 1：完全无交集 → 返回 0（不影响 max）
    if (r < start || end < l) return 0;
    // 情况 2：当前区间被查询区间完全包含 → 剪枝返回
    if (l <= start && end <= r) return segTree[node];
    // 情况 3：部分交集 → 递归左右子树
    int mid = (start + end) / 2;
    int leftMax  = query(node * 2, start, mid, l, r);
    int rightMax = query(node * 2 + 1, mid + 1, end, l, r);
    return max(leftMax, rightMax);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, D;
    cin >> N >> D;

    int ans = 0;

    for (int i = 0; i < N; i++) {
        int val;
        cin >> val;

        // 可转移来源的值域区间：[val-D, val+D]
        int L = max(1, val - D);
        int R = min(MAX_VAL, val + D);

        // 查询该区间内最大 dp 值
        int best = query(1, 1, MAX_VAL, L, R);

        // 当前元素的 dp 值 = 最优前驱 dp + 1
        int cur = best + 1;

        // 更新线段树（位置 val 存入 dp[val]）
        update(1, 1, MAX_VAL, val, cur);

        ans = max(ans, cur);
    }

    cout << ans << endl;
    return 0;
}

dp[i] = 1 + max{ dp[j] : j < i 且 |Aᵢ - Aⱼ| ≤ D }

叶子节点 [v] 存储：dp[v] = 以值为 v 的元素结尾的最优解
查询 query(val-D, val+D)：值在合法范围内的最大 dp
更新 update(val, dp[val])：把当前 dp 写入线段树

void update(int node, int start, int end, int pos, int val) {
    if (start == end) {
        segTree[node] = max(segTree[node], val);  // 取 max（而不是覆盖）
        return;
    }
    int mid = (start + end) / 2;
    if (pos <= mid)
        update(node * 2, start, mid, pos, val);
    else
        update(node * 2 + 1, mid + 1, end, pos, val);
    segTree[node] = max(segTree[node * 2], segTree[node * 2 + 1]);
}

int query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;     // 完全不交 → 返回 0
    if (l <= start && end <= r)              // 完全包含 → 剪枝
        return segTree[node];
    int mid = (start + end) / 2;
    return max(query(node * 2, start, mid, l, r),
               query(node * 2 + 1, mid + 1, end, l, r));
}

for (int i = 0; i < N; i++) {
    int val;
    cin >> val;

    int L = max(1, val - D);
    int R = min(MAX_VAL, val + D);
    int best = query(1, 1, MAX_VAL, L, R);  // O(log MAX_VAL)
    int cur = best + 1;
    update(1, 1, MAX_VAL, val, cur);         // O(log MAX_VAL)
    ans = max(ans, cur);
}