题目大意

维护一个长度为 $n$ 的序列 $a$，支持三种操作：

1. 区间取最小值：对所有 $i$，$a_i = \min(a_i, v)$
2. 区间加下标：对所有 $i$，$a_i = a_i + i$
3. 区间和查询：查询 $\sum_{i=l}^r a_i$

算法思路

核心观察

操作2（加下标）是这道题的关键难点。由于加的是下标 $i$ 而不是常数，不同位置的元素增加量不同，这使得传统的懒标记难以处理。

主要解法：时间分治 + 线段树

1. 时间分治预处理

关键思路：将操作2的累积次数视为"时间"，对于每个操作1，我们可以确定在哪些时间点它会对哪些位置生效。

• 记录每个操作2发生的时间点
• 对于每个操作1 $(v)$，在时间 $t$ 时，它相当于一条直线：$y = -t \cdot x + v$
• 对于位置 $i$，在时间 $t$ 时，操作1生效的条件是：$a_i \geq -t \cdot i + v$

2. 凸壳优化

使用李超线段树来维护这些直线，快速判断在某个时间点、某个位置上，哪些操作1会生效。

3. 主线段树

维护以下信息：

• s1, t1：与操作1相关的和与时间标记
• s2, t2：与操作2相关的和与时间标记
• mx, mt：最大值及其时间
• c1：计数

支持：

• 区间取min操作
• 区间加下标操作
• 区间和查询

复杂度分析

• 预处理：$O(n \log^2 n)$
• 主算法：$O((n+q) \log n)$
• 总复杂度：$O(n \log^2 n + q \log n)$

代码关键部分解析

1. 李超线段树（lct）

struct lct {
    // 维护直线 y = k*x + b
    void update(int &p, int l, int r, int i); // 插入直线
    ll query(int p, int l, int r, int x);     // 查询x处的最小值
};

2. 时间分治（solve函数）

void solve(int l, int r, int x, int y) {
    // 递归确定每个位置在哪些时间点被哪些操作1影响
    // 使用李超线段树快速判断
}

3. 主线段树

struct node {
    ll s1, t1, mx, mt, c1;  // 操作1相关
    ll s2, t2;              // 操作2相关
};

void oper(int p, ll k1, ll k2);  // 应用操作
void cove(int p, ll v);          // 区间取min

实现细节

1. 懒标记处理：需要同时处理两种操作的懒标记
2. 边界情况：注意大数运算和边界条件
3. 内存管理：动态开点线段树需要注意内存分配

总结

这道题综合运用了：

• 时间分治思想
• 李超线段树维护直线
• 复杂懒标记线段树
• 区间最值操作

是考察高级数据结构应用的典型题目，需要深入理解各种线段树变种的原理和实现技巧。