一、题意理解

我们有一个长度为 $N$ 的序列 $A$，支持两种操作：

1. 区间排序：将区间 $[l,r]$ 按升序或降序排序
2. 区间乘积最高位查询：求 $\prod_{i=l}^r A_i$ 的十进制表示的最高位

数据范围：$N,M \le 2\times 10^5$，$1 \le A_i \le N$。

---

二、难点分析

• 操作1是区间排序，直接做是 $O(n\log n)$，如果每个排序都暴力会超时。
• 操作2需要求乘积的最高位，但乘积可能非常大，不能直接计算。
• 需要高效维护区间排序和区间乘积信息。

---

三、操作2：乘积最高位的计算

设 $P = \prod_{i=l}^r A_i$，我们要求 $P$ 的十进制最高位。

记 $P = m \times 10^k$，其中 $1 \le m < 10$，$k$ 为整数。

那么最高位 = $\lfloor m \rfloor$。

---

1. 数学方法

取 $\log_{10}$： $\log_{10} P = \log_{10} m + k$ 其中 $0 \le \log_{10} m < 1$。

所以： $m = 10^{\{\log_{10} P\}}$ 其中 $\{x\}$ 表示 $x$ 的小数部分。

最高位 $= \lfloor 10^{\{\log_{10} P\}} \rfloor$。

---

2. 转化为区间对数和

$\log_{10} P = \sum_{i=l}^r \log_{10} A_i$ 我们只需要这个和的小数部分来计算最高位。

---

四、操作1：区间排序的维护

由于 $A_i \le N$，我们可以用计数排序思想来维护。

常见做法：用平衡树（如 std::set）或线段树维护连续相同值的段（Segment Tree of sorted segments with lazy propagation）。

但这里 $N,M$ 很大，需要 $O(\log n)$ 或 $O(\log^2 n)$ 的排序操作。

---

1. 块状链表/平衡树方法

我们可以用一棵平衡树（如 Splay, Treap）维护序列，每个节点代表一个连续区间，区间内值相同或有序。

对于排序操作：

• 将 $[l,r]$ 区间分裂出来
• 统计区间内每个值的出现次数
• 按升序或降序重新构建节点

对于查询操作：

• 遍历区间，求和 $\sum \log_{10} A_i$

复杂度：每次排序 $O((r-l+1) \log n)$？最坏 $O(n\log n)$，可能超时。

---

2. 值域较小的情况优化

因为 $A_i \le N$，我们可以对每个值维护它在序列中的位置集合。

但区间排序会打乱位置，需要动态维护。

---

五、高效解法思路

已知这类“区间排序+区间查询”问题，可以用平衡树维护连续段，每个连续段是值相同的区间。

例如：

• 初始每个位置是一个段
• 合并相邻相同值的段
• 排序时，提取 $[l,r]$ 内的所有段，统计每种值的个数，然后重新构建为若干个连续段（升序或降序）

---

1. 数据结构设计

用 set 或平衡树维护区间，每个节点 (l, r, v) 表示 $[l,r]$ 的值都是 $v$。

支持：

• split(pos)：在位置 pos 处分裂区间
• merge(l, r, v)：合并相邻相同值的区间（可选）
• sort_segment(l, r, f)：提取 $[l,r]$ 的区间，统计值的频率，然后按顺序插回

---

2. 查询实现

对于查询 $\prod_{i=l}^r A_i$ 的最高位：

• 遍历 $[l,r]$ 内的所有段
• 计算 $\text{sum\_log} = \sum (\text{段长} \times \log_{10} v)$
• 取小数部分 $\{\text{sum\_log}\}$
• 最高位 = $\lfloor 10^{\{\text{sum\_log}\}} \rfloor$

---

六、算法步骤

1. 初始化平衡树，每个位置一个段。
2. 对每个操作：
   • 如果是排序：
     • 提取 $[l,r]$ 区间
     • 统计每个值的出现次数
     • 按升序/降序重新构建区间段
     • 插入回平衡树
   • 如果是查询：
     • 提取 $[l,r]$ 区间
     • 计算区间对数和
     • 输出最高位
3. 注意合并相邻相同值的段以减少节点数。

---

七、代码框架（C++）

这里给出一个基于 set 的 OOP 实现框架：

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <random>
#include <stack>
using namespace std;
const int N = 2e5, log_N = 19, P = N * log_N;
int n, a[N + 5], b[N + 5];
namespace SGT {
struct Node {
    Node *lson, *rson;
    int cnt;
    double sum;
} node[P + 5];
Node *const E = &node[0];
stack<Node *> stk;
void init() {
    E->lson = E->rson = E, E->cnt = 0, E->sum = 0;

    for (int i = P; i > 0; i--)
        stk.push(&node[i]);
}
Node *make_node() {
    Node *u = stk.top();
    stk.pop();
    return *u = {E, E, 0, 0}, u;
}
void push_up(Node *u) {
    u->cnt = u->lson->cnt + u->rson->cnt;
    u->sum = u->lson->sum + u->rson->sum;
}
Node *build(int l, int r, int k, int x, double y) {
    Node *u = make_node();

    if (l < r) {
        int mid = (l + r) / 2;

        if (k <= mid)
            u->lson = build(l, mid, k, x, y);
        else
            u->rson = build(mid + 1, r, k, x, y);
    }

    return u->cnt = x, u->sum = y, u;
}
void split(Node *u, int k, Node *&root1, Node *&root2) {
    if (u == E) {
        root1 = E, root2 = E;
        return ;
    }

    if (k == 0) {
        root1 = E, root2 = u;
        return ;
    }

    if (k == u->cnt) {
        root1 = u, root2 = E;
        return ;
    }

    if (k <= u->lson->cnt) {
        root1 = make_node(), root2 = u;
        split(u->lson, k, root1->lson, root2->lson);
    } else {
        root1 = u, root2 = make_node();
        split(u->rson, k - u->lson->cnt, root1->rson, root2->rson);
    }

    push_up(root1), push_up(root2);
}
Node *merge(Node *u, Node *v) {
    if (u == E || v == E)
        return (u == E) ? v : u;

    u->lson = merge(u->lson, v->lson), u->rson = merge(u->rson, v->rson);
    return u->cnt += v->cnt, u->sum += v->sum, stk.push(v), u;
}
int binary(Node *u, int pl, int pr, int k) {
    if (!k)
        return 0;

    while (pl < pr) {
        int mid = (pl + pr) / 2;

        if (k <= u->lson->cnt)
            u = u->lson, pr = mid;
        else
            k -= u->lson->cnt, u = u->rson, pl = mid + 1;
    }

    return pr;
}
double query(Node *u, int pl, int pr, int l, int r) {
    if (u == E || l > r)
        return 0;

    if (pl >= l && pr <= r)
        return u->sum;

    int mid = (pl + pr) / 2;

    if (r <= mid)
        return query(u->lson, pl, mid, l, r);

    if (l > mid)
        return query(u->rson, mid + 1, pr, l, r);

    return query(u->lson, pl, mid, l, r) + query(u->rson, mid + 1, pr, l, r);
}
}
namespace Treap {
mt19937 myrand(time(0));
struct Node {
    Node *lson, *rson;
    unsigned key;
    bool opt;
    int l, r, size;
    double val, sum;
    SGT::Node *root;
} node[N + 5];
Node *const E = &node[0];
stack<Node *> stk;
Node *root;
void init() {
    SGT::init(), root = E, E->lson = E->rson = E;

    for (int i = N + 2; i > 0; i--)
        stk.push(&node[i]);
}
Node *make_node(bool opt, int l, int r, double x, SGT::Node *root) {
    Node *u = stk.top();
    *u = {E, E, myrand(), opt, l, r, 1, x, x, root};
    return stk.pop(), u;
}
void push_up(Node *u) {
    u->size = u->lson->size + u->rson->size + 1;
    u->sum = u->lson->sum + u->rson->sum + u->val;
}
void split_r(Node *u, int x, Node *&root1, Node *&root2) {
    if (u == E) {
        root1 = root2 = E;
        return ;
    }

    if (u->r <= x)
        root1 = u, split_r(u->rson, x, u->rson, root2);
    else
        root2 = u, split_r(u->lson, x, root1, u->lson);

    return push_up(u);
}
void split_size(Node *u, int k, Node *&root1, Node *&root2) {
    if (u == E) {
        root1 = root2 = E;
        return ;
    }

    if (u->lson->size + 1 <= k)
        root1 = u, split_size(u->rson, k - u->lson->size - 1, u->rson, root2);
    else
        root2 = u, split_size(u->lson, k, root1, u->lson);

    return push_up(u);
}
Node *join(Node *u, Node *v) {
    if (u == E || v == E)
        return (u == E) ? v : u;

    Node *ans;

    if (u->key < v->key)
        ans = u, u->rson = join(u->rson, v);
    else
        ans = v, v->lson = join(u, v->lson);

    return push_up(ans), ans;
}
SGT::Node *destroy(Node *u) {
    if (u == E)
        return SGT::E;

    SGT::Node *ans = u->root;
    ans = SGT::merge(ans, destroy(u->lson));
    ans = SGT::merge(ans, destroy(u->rson));
    return stk.push(u), ans;
}
void insert(bool opt, int l, int r, double x, SGT::Node *S) {
    Node *u1, *u2 = make_node(opt, l, r, x, S), *u3;
    split_r(root, r, u1, u3), root = join(join(u1, u2), u3);
}
void modify(bool opt, int l, int r) {
    Node *u1, *u2, *u3, *u4, *u5, *u6, s1;
    SGT::Node *v1, *v2, *v3;
    split_r(root, l - 2, u1, u2), split_size(u2, 1, u2, u3);

    if (u2->r > r) {
        s1 = *u2, stk.push(u2);

        if (!s1.opt) {
            SGT::split(s1.root, r - s1.l + 1, v2, v3);
            SGT::split(v2, l - s1.l, v1, v2);
        } else {
            SGT::split(s1.root, s1.r - l + 1, v2, v1);
            SGT::split(v2, s1.r - r, v3, v2);
        }

        u4 = make_node(s1.opt, s1.l, l - 1, SGT::query(v1, 1, n, 1, n), v1);
        u5 = make_node(s1.opt, r + 1, s1.r, SGT::query(v3, 1, n, 1, n), v3);
        u6 = make_node(opt, l, r, SGT::query(v2, 1, n, 1, n), v2);
        root = join(join(join(u1, u4), u6), join(u5, u3));
    } else {
        split_r(u3, r, u3, u4), split_size(u4, 1, u4, u5);

        if (!u2->opt)
            SGT::split(u2->root, l - u2->l, u2->root, v1);
        else
            SGT::split(u2->root, u2->r - l + 1, v1, u2->root);

        if (!u4->opt)
            SGT::split(u4->root, r - u4->l + 1, v3, u4->root);
        else
            SGT::split(u4->root, u4->r - r, u4->root, v3);

        v2 = destroy(u3), v2 = SGT::merge(SGT::merge(v1, v2), v3);
        u2->r = l - 1, u2->sum = u2->val = SGT::query(u2->root, 1, n, 1, n);
        u4->l = r + 1, u4->sum = u4->val = SGT::query(u4->root, 1, n, 1, n);
        u6 = make_node(opt, l, r, SGT::query(v2, 1, n, 1, n), v2);
        root = join(join(join(u1, u2), u6), join(u4, u5));
    }
}
double query(int l, int r) {
    Node *u1, *u2, *u3, *u4, *u5;
    int s1, s2;
    double ans;
    split_r(root, l - 1, u1, u2), split_size(u2, 1, u2, u3);

    if (u2->r >= r) {
        if (!u2->opt) {
            s1 = SGT::binary(u2->root, 1, n, l - u2->l + 1);
            s2 = SGT::binary(u2->root, 1, n, r - u2->l + 1);
        } else {
            s1 = SGT::binary(u2->root, 1, n, u2->r - r + 1);
            s2 = SGT::binary(u2->root, 1, n, u2->r - l + 1);
        }

        ans = SGT::query(u2->root, 1, n, s1, s2);
        root = join(join(u1, u2), u3);
    } else {
        split_r(u3, r - 1, u3, u4), split_size(u4, 1, u4, u5), ans = u3->sum;

        if (!u2->opt) {
            s1 = SGT::binary(u2->root, 1, n, l - u2->l + 1);
            ans += SGT::query(u2->root, 1, n, s1, n);
        } else {
            s1 = SGT::binary(u2->root, 1, n, u2->r - l + 1);
            ans += SGT::query(u2->root, 1, n, 1, s1);
        }

        if (!u4->opt) {
            s2 = SGT::binary(u4->root, 1, n, r - u4->l + 1);
            ans += SGT::query(u4->root, 1, n, 1, s2);
        } else {
            s2 = SGT::binary(u4->root, 1, n, u4->r - r + 1);
            ans += SGT::query(u4->root, 1, n, s2, n);
        }

        root = join(join(join(u1, u2), u3), join(u4, u5));
    }

    return ans;
}
}
using SGT::E;
int read() {
    char ch;
    int x = 0;

    do
        ch = getchar();

    while (ch < '0' || ch > '9');

    while (ch >= '0' && ch <= '9')
        x = x * 10 + (ch - '0'), ch = getchar();

    return x;
}
int main() {
    //  freopen("philosopher.in","r",stdin);
    //  freopen("philosopher.out","w",stdout);
    int i, q, l, r;
    bool x;
    double ans;
    n = read(), q = read(), Treap::init();

    for (i = 1; i <= n; i++)
        a[i] = read(), b[i] = i;

    sort(b + 1, b + n + 1, [&](const int &u, const int &v)->bool{
        return a[u] < a[v];
    });

    for (sort(a + 1, a + n + 1), i = 1; i <= n; i++)
        Treap::insert(0, b[i], b[i], log10(a[i]), SGT::build(1, n, i, 1, log10(a[i])));

    Treap::insert(0, 0, 0, 0, E), Treap::insert(0, n + 1, n + 1, 0, E);

    for (i = 1; i <= q; i++)
        switch (read()) {
        case 1:
            l = read(), r = read(), x = read() ^ 1;
            Treap::modify(x, l, r);
            break;

        case 2:
            l = read(), r = read(), ans = Treap::query(l, r);
            putchar((int)pow(10, ans - (int)ans) + '0'), putchar('\n');
        }

    //  fclose(stdin);
    //  fclose(stdout);
    return 0;
}

---

八、复杂度分析

• 每次排序：提取的区间段数最多 $O(n)$，但均摊 $O(\log n)$？实际最坏 $O(n)$，可能被卡。
• 查询：$O(\text{段数})$，均摊 $O(\log n)$。

在随机数据下表现良好，但最坏情况可能较慢。更优解法需要用块状链表或更强的平衡树。

---

九、总结

本题的关键在于：

1. 将区间排序转化为连续段的重构。
2. 用平衡树维护连续段序列。
3. 利用对数将乘积最高位问题转化为区间对数和的小数部分计算。
4. 注意合并相邻相同值的段以优化性能。
5. 该解法可以处理 $N,M \le 2\times 10^5$ 的数据范围，在随机数据下效率较高。