思路与算法

维护26棵独立二值懒线段树，第c棵表示每个位置是不是字母c。每次对[l,r]查询26种频次，按x的升降顺序为各字母分配连续目标段；有该字母时先将其原区间清0，再将目标段设1。操作字段按描述和样例使用l,r,x，保留原输入小节误写说明。

正确性说明

每棵二值树精确表示一种字母出现位置，区间计数得到待排序串的完整多重集合。清0移除该字母旧位置，再在唯一排序的连续段置1，所有目标段互不重叠且恰覆盖原区间，故同时完成正确排序。区间赋0/1的懒标记保持各节点计数为子段真值数，逐操作归纳正确。

复杂度

26棵树的建树和数组初始化O(26N)，每次26次计数和至多52次二值区间赋值均O(logN)，总O(26(N+MlogN))时间，最终每树遍历至多O(N)也计入。空间O(26N)，每棵树计数32位、懒标记8位；单次递归栈O(logN)。

易错点

输入样例1 3 1是l=1,r=3,x=1。清空节点旧频次后再设字母，懒标记-1表示无标记；只处理非零频次段。 采用独立二值树避免每次更新再扫描26维合并的多余常数；原生超时记录保留，原100000操作和1秒限时不变。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct BinaryTree {
    int n;
    vector<int> cnt;
    vector<signed char> tag;
    BinaryTree(int n) : n(n), cnt(4 * n), tag(4 * n, -1) {
    }
    void apply(int v, int l, int r, int x) {
        cnt[v] = (r - l + 1) * x;
        tag[v] = x;
    }
    void push(int v, int l, int r) {
        if (tag[v] >= 0 && l < r) {
            int m = (l + r) / 2;
            apply(v * 2, l, m, tag[v]);
            apply(v * 2 + 1, m + 1, r, tag[v]);
            tag[v] = -1;
        }
    }
    void build(int v, int l, int r, const string &s, int c) {
        if (l == r) {
            cnt[v] = s[l] - 'a' == c;
            return;
        }
        int m = (l + r) / 2;
        build(v * 2, l, m, s, c);
        build(v * 2 + 1, m + 1, r, s, c);
        cnt[v] = cnt[v * 2] + cnt[v * 2 + 1];
    }
    int query(int v, int l, int r, int a, int b) {
        if (a <= l && r <= b)
            return cnt[v];
        push(v, l, r);
        int m = (l + r) / 2, z = 0;
        if (a <= m)
            z += query(v * 2, l, m, a, b);
        if (b > m)
            z += query(v * 2 + 1, m + 1, r, a, b);
        return z;
    }
    void assign(int v, int l, int r, int a, int b, int x) {
        if (a <= l && r <= b) {
            apply(v, l, r, x);
            return;
        }
        push(v, l, r);
        int m = (l + r) / 2;
        if (a <= m)
            assign(v * 2, l, m, a, b, x);
        if (b > m)
            assign(v * 2 + 1, m + 1, r, a, b, x);
        cnt[v] = cnt[v * 2] + cnt[v * 2 + 1];
    }
    void output(int v, int l, int r, string &s, char c) {
        if (!cnt[v])
            return;
        if (cnt[v] == r - l + 1) {
            fill(s.begin() + l, s.begin() + r + 1, c);
            return;
        }
        push(v, l, r);
        int m = (l + r) / 2;
        output(v * 2, l, m, s, c);
        output(v * 2 + 1, m + 1, r, s, c);
    }
};
int main() {
    int n, m;
    string s;
    cin >> n >> m >> s;
    vector<BinaryTree> trees;
    trees.reserve(26);
    for (int c = 0; c < 26; c++) {
        trees.emplace_back(n);
        trees[c].build(1, 0, n - 1, s, c);
    }
    while (m--) {
        int l, r, x;
        cin >> l >> r >> x;
        --l;
        --r;
        array<int, 26> a{};
        for (int c = 0; c < 26; c++)
            a[c] = trees[c].query(1, 0, n - 1, l, r);
        int at = l;
        for (int j = 0; j < 26; j++) {
            int c = x ? j : 25 - j;
            if (!a[c])
                continue;
            trees[c].assign(1, 0, n - 1, l, r, 0);
            trees[c].assign(1, 0, n - 1, at, at + a[c] - 1, 1);
            at += a[c];
        }
    }
    for (int c = 0; c < 26; c++)
        trees[c].output(1, 0, n - 1, s, 'a' + c);
    cout << s << '\n';
}