题目分析

JYY 的计算器有 $N$ 条预设指令，每次输入一个初始值 $X$，依次执行所有指令，结果限制在 $[L,R]$ 范围内。需要处理 $Q$ 个不同的初始值，求每个初始值经过所有指令后的最终结果。

解题思路

核心思想

使用线段树结合函数复合的方法批量处理：

1. 将每个初始值 $X$ 经过指令序列的变换看作复合函数
2. 使用线段树维护所有初始值的当前状态
3. 通过延迟标记高效处理批量指令

关键技术

• 函数复合：每个指令对应线性变换 $f(x) = mul \cdot x + addx \cdot x_0 + add$
• 延迟传播：累积未下推的操作，减少更新次数
• 边界处理：自动将超出范围的值修正为 $L$ 或 $R$

算法步骤

1. 读入指令和初始值，对初始值排序
2. 构建线段树，维护每个叶子节点的当前值和初始值
3. 依次处理每条指令，更新线段树的延迟标记
4. 处理边界溢出，修正超出范围的值
5. 查询最终结果，输出每个初始值对应的结果

完整代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define enl putchar('\n')
#define spc putchar(' ')

namespace fastIO {
    void read(int &res) {
        int f = 1;
        res = 0;
        char c = getchar();
        while (c < '0' || c > '9') {
            if (c == '-') f = -1;
            c = getchar();
        }
        while (c >= '0' && c <= '9') {
            res = (res << 3) + (res << 1) + (c ^ 48);
            c = getchar();
        }
        res *= f;
    }
    
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar((x % 10) | 48);
    }
}

using namespace fastIO;

const int N = 100005;

int m, down, up, n;
int ans[N];
pair<int, int> upd[N];  // 存储指令：类型和参数
pair<int, int> a[N];    // 存储初始值和索引

// 线段树节点
struct node {
    int minn, min0, maxn, max0;  // 当前最小值、初始最小值、当前最大值、初始最大值
    int add, mul, addx;           // 延迟标记：常数加、乘、与初始值相关的加
} tr[N << 2];

// 合并左右子树信息
void pushup(int k) {
    tr[k].maxn = tr[k << 1 | 1].maxn;
    tr[k].minn = tr[k << 1].minn;
    tr[k].min0 = tr[k << 1].min0;
    tr[k].max0 = tr[k << 1 | 1].max0;
}

// 构建线段树
void build(int k, int l, int r) {
    tr[k].mul = 1;
    tr[k].add = tr[k].addx = 0;
    
    if (l == r) {
        tr[k].minn = tr[k].maxn = tr[k].min0 = tr[k].max0 = a[l].first;
        return;
    }
    
    int mid = (l + r) >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    pushup(k);
}

// 应用变换到节点
void pushnow(int k, int t1, int t2, int t3) {
    // 更新延迟标记
    tr[k].mul *= t1;
    tr[k].add = tr[k].add * t1 + t3;
    tr[k].addx = tr[k].addx * t1 + t2;
    
    // 更新当前值范围
    tr[k].maxn = tr[k].maxn * t1 + tr[k].max0 * t2 + t3;
    tr[k].minn = tr[k].minn * t1 + tr[k].min0 * t2 + t3;
}

// 根据指令类型更新
void update(int k, int op, int x) {
    if (op == 0)       // +a: f(x) = x + a
        pushnow(k, 1, 0, x);
    else if (op == 1)  // -a: f(x) = x - a  
        pushnow(k, 1, 0, -x);
    else if (op == 2)  // *a: f(x) = x * a
        pushnow(k, x, 0, 0);
    else if (op == 3)  // @a: f(x) = x + a*x0
        pushnow(k, 1, x, 0);
}

// 下推延迟标记
void pushdown(int k) {
    pushnow(k << 1, tr[k].mul, tr[k].addx, tr[k].add);
    pushnow(k << 1 | 1, tr[k].mul, tr[k].addx, tr[k].add);
    tr[k].mul = 1;
    tr[k].addx = tr[k].add = 0;
}

// 处理下界溢出：将小于down的值设为down
void todown(int k, int l, int r) {
    if (l == r) {
        pushnow(k, 0, 0, down);  // 直接设为下界
        return;
    }
    
    pushdown(k);
    int mid = (l + r) >> 1;
    
    // 根据右子树的最小值决定处理顺序
    if (tr[k << 1 | 1].minn < down) {
        todown(k << 1 | 1, mid + 1, r);
        pushnow(k << 1, 0, 0, down);  // 左子树全部设为下界
    } else {
        todown(k << 1, l, mid);
    }
    
    pushup(k);
}

// 处理上界溢出：将大于up的值设为up  
void toup(int k, int l, int r) {
    if (l == r) {
        pushnow(k, 0, 0, up);  // 直接设为上界
        return;
    }
    
    pushdown(k);
    int mid = (l + r) >> 1;
    
    // 根据左子树的最大值决定处理顺序
    if (tr[k << 1].maxn > up) {
        toup(k << 1, l, mid);
        pushnow(k << 1 | 1, 0, 0, up);  // 右子树全部设为上界
    } else {
        toup(k << 1 | 1, mid + 1, r);
    }
    
    pushup(k);
}

// 查询最终结果
void query(int k, int l, int r) {
    if (l == r) {
        ans[a[l].second] = tr[k].minn;  // 存储到对应索引
        return;
    }
    
    pushdown(k);
    int mid = (l + r) >> 1;
    query(k << 1, l, mid);
    query(k << 1 | 1, mid + 1, r);
}

signed main() {
    // 读入指令数量、上下界
    read(m); read(down); read(up);
    
    // 读入所有指令
    for (int i = 1; i <= m; i++) {
        char op[2];
        cin >> op;
        
        // 解析指令类型
        if (op[0] == '+') upd[i].first = 0;
        else if (op[0] == '-') upd[i].first = 1;
        else if (op[0] == '*') upd[i].first = 2;
        else if (op[0] == '@') upd[i].first = 3;
        
        read(upd[i].second);  // 读入参数
    }
    
    // 读入初始值数量
    read(n);
    
    // 读入初始值并记录原始索引
    for (int i = 1; i <= n; i++) {
        read(a[i].first);
        a[i].second = i;
    }
    
    // 按初始值排序（便于线段树处理）
    sort(a + 1, a + n + 1);
    
    // 构建线段树
    build(1, 1, n);
    
    // 依次处理每条指令
    for (int i = 1; i <= m; i++) {
        // 应用当前指令
        update(1, upd[i].first, upd[i].second);
        
        // 处理边界溢出
        if (tr[1].minn < down)
            todown(1, 1, n);
        if (tr[1].maxn > up)
            toup(1, 1, n);
    }
    
    // 查询所有结果
    query(1, 1, n);
    
    // 按原始顺序输出结果
    for (int i = 1; i <= n; i++) {
        write(ans[i]);
        enl;
    }
    
    return 0;
}

代码说明

关键数据结构

• upd[]：存储指令序列（类型和参数）
• a[]：存储初始值和原始索引，用于排序和结果映射
• tr[]：线段树节点，维护当前状态和延迟标记

函数变换模型

每个节点维护的变换函数为：

其中：

• $x$：当前值
• $x_0$：初始值
• 四种指令对应的参数变化：
  • +a: (mul=1, addx=0, add=a)
  • -a: (mul=1, addx=0, add=-a)
  • *a: (mul=a, addx=0, add=0)
  • @a: (mul=1, addx=a, add=0)

算法亮点

1. 批量处理：通过线段树同时处理所有初始值
2. 延迟传播：减少不必要的更新操作
3. 边界修正：自动处理溢出情况，保持值在有效范围内
4. 函数复合：通过线性变换的复合高效处理指令序列

复杂度分析

• 时间复杂度：$O((N+Q)\log Q)$
  • 每条指令处理：$O(\log Q)$
  • 边界修正：均摊 $O(\log Q)$
  • 最终查询：$O(Q)$
• 空间复杂度：$O(Q)$