A. Maple and Multiplication

思路：

其实就是找最大公倍数

分三种情况：

a==b 0  ； gcd(a,b)==a||b   1   ；其他  2

#include<bits/stdc++.h>
#define ll long long 
#define endl "\n"
using namespace std;
int gcd(int x, int y) {
    while (x % y != 0) {
        int w = x % y;
        x = y;
        y = w;
    }
    return y;
}
void solve() {
    int a, b;
    cin >> a >> b;
    int w = gcd(a, b);
    if (a == b) {
        cout << 0 << endl;
    }
    else if(w==a||w==b) {
        cout << 1 << endl;
    }
    else {
        cout << 2 << endl;
    }
    return;
}
int main(){
	ios::sync_with_stdio(false);        // 禁用同步
    std::cin.tie(nullptr),std::cout.tie(nullptr);             // 解除cin与cout绑定
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B. Cake Collection

思路：贪心

他会累积，所以事最后一秒收最快的，倒二秒收次快的……

#include<bits/stdc++.h>
#define ll long long 
#define endl "\n"
using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end(), greater<int>());
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += m * a[i];
        m--;
        if (m == 0) {
            break;
        }
    }
    cout << ans << endl;
    return;
}
int main(){
	ios::sync_with_stdio(false);        // 禁用同步
    std::cin.tie(nullptr),std::cout.tie(nullptr);             // 解除cin与cout绑定
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C. Cake Assignment

思路：

从结果出发，反方向推（分一半给别人，就相当于另一个人减去自己，自己*2），可以发现只有自己比别人小，才可以进行此操作，否则另一个人进行此操作，直到两人相等；

#include<bits/stdc++.h>
#define ll long long 
#define endl "\n"
using namespace std;

void solve() {
    ll k, x;
    cin >> k >> x;
    vector<int> a;
    ll y = 1;
    for (int i = 0; i <= k; i++) {
        y *= 2;
    }
    y -= x;
    while (x != y){
        if (x < y) {
            y -= x;
            x *= 2;
            a.push_back(1);
        }
        else {
            x -= y;
            y *= 2;
            a.push_back(2);
        }
    }
    cout << a.size() << endl;
    for (int i = a.size()-1; i>=0; i--) {
        cout << a[i] << " ";
    }
    cout << endl;
    return;
}
int main(){
	ios::sync_with_stdio(false);        // 禁用同步
    std::cin.tie(nullptr),std::cout.tie(nullptr);             // 解除cin与cout绑定
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

 D. Antiamuny Wants to Learn Swap

思路：

例句n=3,4的所以情况，可以发现只要在区间内存在 三个（可以不相邻）递减的数，这个区间就是不完美的。

因此我们可以找到以a[i]为左边界，区间内存在 三个（可以不相邻）递减的数的最小为右边界，记为d[i]的值，然后看 r<d[i]的话就是完美的。（这个可以用单调栈来写）

#include<bits/stdc++.h>
#define ll long long  // 定义长整型别名，简化代码
#define endl "\n"     // 定义换行符宏，方便输出
using namespace std;

void solve() {
    int n, q;
    cin >> n >> q;  // 输入数组长度n和查询次数q
    
    // 定义数组：
    // a[i]：原始数组（1-based索引）
    // b[i]：记录i位置右侧第一个比a[i]小的元素位置（不存在则为n+2）
    // c[i]：记录i位置左侧第一个比a[i]大的元素位置（不存在则为0）
    // d[i]：预处理的辅助数组，用于快速回答查询
    vector<int>a(n+1), b(n+1), c(n+1), d(n+1 , n + 2);
    
    // 读取原始数组
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    stack<int> p;  // 单调栈，用于维护元素索引
    
    // 第一遍单调栈：求b数组（右侧第一个更小元素位置）
    for (int i = 1; i <= n; i++) {
        // 栈非空且当前元素小于栈顶元素时，栈顶元素的右侧更小元素就是i
        while (!p.empty() && a[i] < a[p.top()]) {
            b[p.top()] = i;  // 记录位置
            p.pop();         // 栈顶元素已处理，弹出
        }
        p.push(i);  // 当前元素入栈，继续维护单调性
    }
    // 处理栈中剩余元素（右侧没有更小的元素）
    while (!p.empty()) {
        b[p.top()] = n + 2;  // 用n+2标记不存在
        p.pop();
    }
    
    // 第二遍单调栈：求c数组（左侧第一个更大元素位置）
    for (int i = n; i > 0; i--) {  // 从右向左遍历
        // 栈非空且当前元素大于栈顶元素时，栈顶元素的左侧更大元素就是i
        while (!p.empty() && a[i] > a[p.top()]) {
            c[p.top()] = i;  // 记录位置
            p.pop();         // 栈顶元素已处理，弹出
        }
        p.push(i);  // 当前元素入栈，继续维护单调性
    }
    // 处理栈中剩余元素（左侧没有更大的元素）
    while (!p.empty()) {
        c[p.top()] = 0;  // 用0标记不存在
        p.pop();
    }
    
    // 预处理d数组：d[k]表示所有c[i]=k的元素中，b[i]的最小值
    for (int i = 1; i <= n; i++) {
        d[c[i]] = min(d[c[i]], b[i]);
    }
    
    // 对d数组进行后缀最小值处理，使d[i]表示i及右侧的最小值
    int min_d = d[n];  // 从n开始向左维护最小值
    for (int i = n; i > 0; i--) {
        min_d = min(min_d, d[i]);
        d[i] = min_d;  // 更新d[i]为当前最小值
    }
    
    // 处理查询
    int l, r;
    for (int i = 0; i < q; i++) {
        cin >> l >> r;
        // 判断[l, r]区间内是否满足条件：
        // d[l] > r表示在l位置及右侧，符合条件的元素右侧更小元素位置超出r范围
        if (d[l] > r) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return;
}

int main() {
    ios::sync_with_stdio(false);  // 禁用输入输出同步，加速cin/cout
    std::cin.tie(nullptr), std::cout.tie(nullptr);  // 解除cin与cout的绑定，进一步加速
    int t = 1;
    cin >> t;  // 输入测试用例数量
    while (t--) {
        solve();  // 处理每个测试用例
    }
    return 0;
}

这是给思路，AI写的代码，运行正确（不建议）

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int MAXN = 5e5 + 10;

int a[MAXN];
int rightmost_greater[MAXN];  // 每个位置j左边最大的i<j且a[i]>a[j]
int max_i[MAXN];              // 每个位置k对应的最大i，使得存在i<j<k且a[i]>a[j]>a[k]

// Fenwick树用于计算max_i，支持前缀最大值查询和点更新
struct FenwickTree {
    int size;
    vector<int> tree;

    FenwickTree(int n) : size(n), tree(n + 2, -INF) {}

    // 更新位置x的最大值为v
    void update(int x, int v) {
        for (; x <= size; x += x & -x) {
            tree[x] = max(tree[x], v);
        }
    }

    // 查询[1, x]区间的最大值
    int query(int x) {
        int res = -INF;
        for (; x > 0; x -= x & -x) {
            res = max(res, tree[x]);
        }
        return res;
    }
};

// 线段树用于查询max_i的区间最大值
struct SegmentTree {
    int n;
    vector<int> tree;

    SegmentTree(int size) {
        n = 1;
        while (n < size) n <<= 1;
        tree.assign(2 * n, -INF);
    }

    void build(const vector<int>& arr) {
        for (int i = 0; i < arr.size(); ++i) {
            tree[n + i] = arr[i];
        }
        for (int i = n - 1; i > 0; --i) {
            tree[i] = max(tree[2 * i], tree[2 * i + 1]);
        }
    }

    // 查询[l, r]区间的最大值（0-based）
    int query(int l, int r) {
        l += n;
        r += n;
        int res = -INF;
        while (l <= r) {
            if (l % 2 == 1) res = max(res, tree[l++]);
            if (r % 2 == 0) res = max(res, tree[r--]);
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
};

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

    int t;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }

        // 步骤1：计算rightmost_greater
        stack<int> st;
        for (int j = 1; j <= n; ++j) {
            while (!st.empty() && a[st.top()] <= a[j]) {
                st.pop();
            }
            rightmost_greater[j] = st.empty() ? -INF : st.top();
            st.push(j);
        }

        // 步骤2：计算max_i
        int rev_size = n;
        FenwickTree ft(rev_size);
        for (int k = 1; k <= n; ++k) {
            // 计算反转索引，将a[j] > a[k]的查询转为前缀查询
            int x = a[k];
            int rev_x = rev_size - x + 1;
            int q_max = ft.query(rev_x - 1);  // 查询a[j] > a[k]的最大值
            max_i[k] = q_max;

            // 更新Fenwick树，插入当前元素的rightmost_greater
            int current_rev = rev_size - a[k] + 1;
            if (rightmost_greater[k] != -INF) {
                ft.update(current_rev, rightmost_greater[k]);
            }
        }

        // 步骤3：构建线段树查询max_i的区间最大值
        vector<int> seg_data(n + 1);  // 1-based
        for (int i = 1; i <= n; ++i) {
            seg_data[i] = max_i[i];
        }
        SegmentTree stree(n + 1);  // 0-based存储，1-based数据
        stree.build(seg_data);

        // 处理查询
        while (q--) {
            int l, r;
            cin >> l >> r;
            if (r - l + 1 < 3) {
                cout << "YES\n";
                continue;
            }
            int k_start = l + 2;
            int k_end = r;
            if (k_start > k_end) {
                cout << "YES\n";
                continue;
            }
            // 线段树是0-based，查询[k_start, k_end]
            int max_val = stree.query(k_start, k_end);
            if (max_val >= l) {
                cout << "NO\n";
            }
            else {
                cout << "YES\n";
            }
        }
    }

    return 0;
}