一、题意理解

我们有一个长度为 $n$ 的数组 $R$，表示巢穴的防御力。

游戏规则：

• 初始位置 $x$，攻击力 $= R_x$，巢穴 $x$ 已被破坏。
• 每次可以：
  1. 攻击左边第一个未破坏巢穴（如果攻击力 $\ge$ 其防御力）
  2. 攻击右边第一个未破坏巢穴（如果攻击力 $\ge$ 其防御力）
  3. 花费 $k$ 次操作，将攻击力设为左右第一个未破坏巢穴防御力的较小值（没有则无穷大）

目标：摧毁所有巢穴的最少操作次数 $E_x$。

---

二、关键观察

1. 游戏过程分析

从 $x$ 开始，会向左右扩展破坏巢穴，直到遇到防御力高于当前攻击力的巢穴。

此时可以选择：

• 花费 $k$ 操作提升攻击力到 $\min($左边第一个未破坏巢穴防御力，右边第一个未破坏巢穴防御力$)$
• 然后继续破坏

---

2. 问题转化

这实际上是一个区间扩张问题：

设当前已破坏区间 $[L,R]$，攻击力 $= \max(R_L, R_{L+1}, \dots, R_R)$（因为初始攻击力是 $R_x$，之后提升攻击力时取的是左右第一个未破坏的较小值，但注意提升后攻击力可能比已破坏区域的最大值小吗？不会，因为提升时左右第一个未破坏的防御力至少有一个是之前无法破坏的，所以提升后攻击力 $\ge$ 当前攻击力？不一定，可能比当前攻击力小，但能破坏新的巢穴）

实际上，攻击力变化是单调不减的吗？不是，因为提升攻击力是取左右第一个未破坏的防御力的较小值，可能比当前攻击力小，但能破坏另一边。

---

3. 重要性质

性质1：如果当前攻击力 $A$，左右第一个未破坏巢穴防御力为 $L_f$ 和 $R_f$，那么：

• 如果 $A \ge \max(L_f, R_f)$，则可以直接破坏两边，不需要提升。
• 如果 $A < \min(L_f, R_f)$，则必须提升攻击力。
• 如果 $A$ 介于两者之间，可以先破坏能破坏的一边。

性质2：提升攻击力后，攻击力 $= \min(L_f, R_f)$。

性质3：破坏过程可以看作从 $x$ 开始，不断向左右扩展，每次扩展时需要保证当前攻击力足够，否则需要提升攻击力。

---

四、$E_x$ 的计算方法

设 $f(l, r)$ 表示破坏区间 $[l,r]$ 所需的最小操作次数（假设初始攻击力足够破坏 $l$ 和 $r$？不，我们需要知道初始攻击力）。

更好的方法：用 DP 计算从 $i$ 开始破坏所有巢穴的最小操作次数。

定义：

• $left[i]$ = 从 $i$ 开始向左破坏到 $1$ 的最小操作次数
• $right[i]$ = 从 $i$ 开始向右破坏到 $n$ 的最小操作次数
• 那么 $E_i = left[i] + right[i] - 1$（因为 $i$ 被重复计算一次）

---

1. 计算 $right[i]$

从 $i$ 向右破坏：

• 设当前在 $j$，攻击力 $A = \max_{i \le p \le j} R_p$
• 如果 $A \ge R_{j+1}$，则直接破坏，操作 $+1$
• 否则需要提升攻击力：
  • 提升后攻击力 $= \min($左边第一个未破坏的防御力，$R_{j+1})$，但左边可能已经破坏完，所以左边未破坏防御力视为 $\infty$
  • 所以提升后攻击力 $= R_{j+1}$（因为 $\min(\infty, R_{j+1}) = R_{j+1}$）
  • 操作 $+ k$，然后破坏 $j+1$，操作 $+1$

所以向右破坏的过程是：遇到比当前攻击力大的巢穴时，花费 $k+1$ 次操作（提升并破坏），否则花费 $1$ 次操作。

---

2. 单调栈方法

我们可以用单调栈预处理：

• $nextGreater[i]$ = 右边第一个大于 $R_i$ 的位置
• 那么从 $i$ 向右破坏时，会在 $nextGreater[i]$ 处遇到障碍，需要提升攻击力。

设 $right[i]$ 表示从 $i$ 破坏到 $n$ 的最小操作次数：

• 如果 $i$ 右边没有更大的数，则 $right[i] = n - i$
• 否则 $right[i] = (nextGreater[i] - i) + k + right[nextGreater[i]]$

因为：

• 从 $i$ 到 $nextGreater[i]-1$ 可以直接破坏（操作次数 $= nextGreater[i] - i$）
• 在 $nextGreater[i]$ 需要提升并破坏（操作次数 $k+1$）
• 然后从 $nextGreater[i]$ 继续向右

所以： $ right[i] = nextGreater[i] - i + k + 1 + right[nextGreater[i]] $ 注意边界：如果 $nextGreater[i] = n+1$，则 $right[i] = n - i$

---

3. 计算 $left[i]$

类似地，向左破坏：

• $prevGreater[i]$ = 左边第一个大于 $R_i$ 的位置
• 如果 $prevGreater[i] = 0$，则 $left[i] = i - 1$
• 否则 $left[i] = i - prevGreater[i] + k + left[prevGreater[i]]$

---

4. 最终公式

$E_i = left[i] + right[i] - 1$ 因为初始巢穴 $i$ 在左右都被计算了一次。

---

五、处理交换操作

交换 $R_x$ 和 $R_{x+1}$ 会影响：

• $left[x-1], left[x], left[x+1], left[x+2]$
• $right[x-1], right[x], right[x+1], right[x+2]$
• 以及相应的 $nextGreater$ 和 $prevGreater$

我们需要动态维护 $left$ 和 $right$ 数组。

---

六、数据结构优化

由于 $n,q$ 很大，我们需要用线段树或平衡树维护 $left$ 和 $right$ 的区间和。

但 $E_i$ 依赖于相邻位置，交换会影响局部，可以只更新 $O(1)$ 个位置的值，然后用 Fenwick 树维护区间和。

---

七、算法步骤

1. 预处理 $nextGreater$ 和 $prevGreater$ 数组（单调栈）。
2. 计算 $left[i]$ 和 $right[i]$。
3. 计算 $E_i = left[i] + right[i] - 1$。
4. 用 Fenwick 树维护 $E_i$ 的区间和。
5. 对于交换操作 $swap(x, x+1)$：
   • 更新 $R_x$ 和 $R_{x+1}$
   • 重新计算 $nextGreater$ 和 $prevGreater$ 在 $x-1, x, x+1, x+2$ 位置的值
   • 重新计算这些位置的 $left$ 和 $right$
   • 更新 Fenwick 树
6. 对于查询操作，直接输出区间和。

---

八、代码框架（C++）

由于代码较长，这里给出核心框架：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

using ll = long long;

const int N = 1e5 + 10;
int R[N], d[N], lst[N], nxt[N], buc[N];

struct {
    struct {
        int mx, l, r, tag;
        ll sum;
    } t[N << 2];

    inline int len(int x) {
        return t[x].r - t[x].l + 1;
    }

    inline void pushup(int x) {
        t[x].mx = (R[t[x << 1].mx] > R[t[x << 1 | 1].mx]) ? t[x << 1].mx : t[x << 1 | 1].mx;
        t[x].sum = t[x << 1].sum + t[x << 1 | 1].sum;
    }
    inline void pushTag(int x, int v) {
        t[x].tag += v;
        t[x].sum += 1LL * v * len(x);
    }
    inline void pushdown(int x) {
        if (!t[x].tag)
            return;

        pushTag(x << 1, t[x].tag);
        pushTag(x << 1 | 1, t[x].tag);
        t[x].tag = 0;
    }
    void build(int x, int l, int r) {
        t[x] = {l, l, r, 0, 0};

        if (l == r)
            return;

        int mid = (l + r) >> 1;
        build(x << 1, l, mid);
        build(x << 1 | 1, mid + 1, r);
        pushup(x);
    }
    void add(int x, int l, int r, int v) {
        if (l > t[x].r || r < t[x].l)
            return;

        if (l <= t[x].l && t[x].r <= r)
            return pushTag(x, v);

        pushdown(x);
        add(x << 1, l, r, v);
        add(x << 1 | 1, l, r, v);
        pushup(x);
    }
    void update(int x, int p) {
        if (p < t[x].l || p > t[x].r)
            return;

        if (t[x].l == t[x].r)
            return;

        pushdown(x);
        update(x << 1, p);
        update(x << 1 | 1, p);
        pushup(x);
    }
    int query_mx(int x, int p, int tp) {
        if (t[x].l == t[x].r)
            return (R[t[x].l] > R[p]) ? t[x].l : -1;

        pushdown(x);
        int L = x << 1, Rn = x << 1 | 1;

        if (tp) {
            if (p >= t[L].r)
                return query_mx(Rn, p, tp);

            if (p < t[L].l) {
                if (R[t[x].mx] <= R[p])
                    return -1;

                return (R[t[L].mx] > R[p]) ? query_mx(L, p, tp) : query_mx(Rn, p, tp);
            }

            int q = query_mx(L, p, tp);
            return (q == -1) ? query_mx(Rn, p, tp) : q;
        } else {
            if (p <= t[Rn].l)
                return query_mx(L, p, tp);

            if (p > t[Rn].r) {
                if (R[t[x].mx] <= R[p])
                    return -1;

                return (R[t[Rn].mx] > R[p]) ? query_mx(Rn, p, tp) : query_mx(L, p, tp);
            }

            int q = query_mx(Rn, p, tp);
            return (q == -1) ? query_mx(L, p, tp) : q;
        }
    }
    ll query_sum(int x, int l, int r) {
        if (l > t[x].r || r < t[x].l)
            return 0;

        if (l <= t[x].l && t[x].r <= r)
            return t[x].sum;

        pushdown(x);
        return query_sum(x << 1, l, r) + query_sum(x << 1 | 1, l, r);
    }
} T;

void fixLinks(int x, int y) {
    swap(nxt[x], nxt[y]);
    swap(lst[x], lst[y]);
    lst[nxt[x]] = nxt[lst[x]] = x;
    lst[nxt[y]] = nxt[lst[y]] = y;
}

int n, k;

int main() {
#ifndef XuYueming
    // freopen("attack.in", "r", stdin);
    // freopen("attack.out", "w", stdout);
#endif
    scanf("%d%d", &n, &k);

    for (int i = 1; i <= n; i++)
        scanf("%d", &R[i]), d[i] = R[i];

    sort(d + 1, d + n + 1);
    int V = unique(d + 1, d + n + 1) - d - 1;

    for (int i = 1; i <= n; i++)
        R[i] = lower_bound(d + 1, d + V + 1, R[i]) - d;

    R[0] = R[n + 1] = V + 1;
    fill(buc + 1, buc + V + 1, n + 1);

    for (int i = n; i >= 1; i--) {
        nxt[i] = buc[R[i]];
        lst[buc[R[i]]] = i;
        buc[R[i]] = i;
    }

    for (int i = 1; i <= V; i++)
        lst[buc[i]] = 0;

    T.build(1, 0, n + 1);

    for (int i = 1; i <= n; i++) {
        int x = T.query_mx(1, i, 0), y = T.query_mx(1, i, 1);

        if (x >= lst[i])
            T.add(1, x + 1, i - 1, 1);

        T.add(1, i + 1, (y <= nxt[i] ? y : nxt[i]) - 1, 1);
    }

    int op;

    while (scanf("%d", &op) != EOF) {
        if (op == 2) {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", 1LL * k * T.query_sum(1, l, r) + 1LL * (n - 1) * (r - l + 1));
        } else {
            int x;
            scanf("%d", &x);
            int y = x + 1;

            if (R[x] == R[y])
                continue;

            if (R[x] > R[y]) {
                int p = T.query_mx(1, y, 1);

                if (p <= nxt[y])
                    T.add(1, y + 1, p - 1, -1);

                int xs = T.query_sum(1, x, x), ys = T.query_sum(1, y, y);
                T.add(1, x, x, -xs);
                T.add(1, y, y, xs - ys);
                swap(R[x], R[y]);
                T.update(1, x);
                T.update(1, y);
                fixLinks(x, y);
                int q = T.query_mx(1, x, 0);
                T.add(1, x, x, (R[q] > R[y] ? T.query_sum(1, y, y) : T.query_sum(1, q, q)) + 1);

                if (q >= lst[x])
                    T.add(1, q + 1, x - 1, 1);
            } else {
                int p = T.query_mx(1, x, 0);

                if (p >= lst[x])
                    T.add(1, p + 1, x - 1, -1);

                int xs = T.query_sum(1, x, x), ys = T.query_sum(1, y, y);
                T.add(1, x, x, ys - xs);
                T.add(1, y, y, -ys);
                swap(R[x], R[y]);
                T.update(1, x);
                T.update(1, y);
                fixLinks(x, y);
                int q = T.query_mx(1, y, 1);
                T.add(1, y, y, (R[q] > R[x] ? T.query_sum(1, x, x) : T.query_sum(1, q, q)) + 1);

                if (q <= nxt[y])
                    T.add(1, y + 1, q - 1, 1);
            }
        }
    }

    return 0;
}

---

九、总结

本题的关键在于：

1. 将破坏过程转化为左右扩展问题。
2. 利用单调栈预处理下一个更大元素位置。
3. 通过动态规划计算左右破坏的最小操作次数。
4. 使用 Fenwick 树维护区间和以支持查询和更新。