[CF558E] A Simple Task

[CF558E] A Simple Task - 线段树

Description

给定一个长度不超过 (10^5) 的字符串（小写英文字母），和不超过 50000 个操作。每个操作 L R K 表示给区间 [L,R] 的字符串排序，K=1 为升序，K=0 为降序。

Solution

线段树，每个结点维护区间内 26 个字母的出现次数，对每次排序操作暴力重新覆盖。

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct SegmentTree
{
    int n;

    struct Node
    {
        array<int, 27> a;
        int tag=0;
        void put(int x, int len)
        {
            tag = x + 1;
            for (int i = 0; i < 26; i++)
                a[i] = 0;
            a[x] = len;
        }
        Node operator+(const Node &rhs) const
        {
            auto res = *this;
            for (int i = 0; i < 26; i++)
                res.a[i] += rhs.a[i];
            res.tag=0;
            return res;
        }
    };

    vector<Node> nodes;

    SegmentTree(int n) : n(n)
    {
        nodes.resize(4 * n + 8);
    }

    void pushup(int p)
    {
        nodes[p] = nodes[p * 2] + nodes[p * 2 + 1];
    }

    void pushdown(int p, int l, int r)
    {
        if (nodes[p].tag)
        {
            nodes[p * 2].put(nodes[p].tag - 1, (l + r) / 2 - l + 1);
            nodes[p * 2 + 1].put(nodes[p].tag - 1, r - (l + r) / 2);
            nodes[p].tag = 0;
        }
    }

    void build(int p, int l, int r, const string &str)
    {
        if (l == r)
            nodes[p].put(str[l - 1] - 'a', 1);
        else
        {
            build(p * 2, l, (l + r) / 2, str);
            build(p * 2 + 1, (l + r) / 2 + 1, r, str);
            pushup(p);
        }
    }

    void Build(const string &str)
    {
        build(1, 1, n, str);
    }

    void modify(int p, int l, int r, int ql, int qr, int x)
    {
        if (l > qr || r < ql)
            return;
        if (l >= ql && r <= qr)
            nodes[p].put(x, r - l + 1);
        else
        {
            pushdown(p, l, r);
            modify(p * 2, l, (l + r) / 2, ql, qr, x);
            modify(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr, x);
            pushup(p);
        }
    }

    void Modify(int ql, int qr, int x)
    {
        if (ql > qr)
            return;
        // cout << "Modify " << ql << ", " << qr << ", " << x << endl;
        modify(1, 1, n, ql, qr, x);
    }

    Node query(int p, int l, int r, int ql, int qr)
    {
        if (l > qr || r < ql)
            return Node();
        if (l >= ql && r <= qr)
            return nodes[p];
        pushdown(p, l, r);
        return query(p * 2, l, (l + r) / 2, ql, qr) + query(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr);
    }

    Node Query(int ql, int qr)
    {
        return query(1, 1, n, ql, qr);
    }

    void SortAsc(int ql, int qr)
    {
        Node res = Query(ql, qr);
        int l = ql;
        for (int i = 0; i < 26; i++)
        {
            int r = l + res.a[i] - 1;
            Modify(l, r, i);
            l = r + 1;
        }
        assert(l == qr + 1);
    }

    void SortDesc(int ql, int qr)
    {
        Node res = Query(ql, qr);
        int l = ql;
        for (int i = 25; i >= 0; i--)
        {
            int r = l + res.a[i] - 1;
            Modify(l, r, i);
            l = r + 1;
        }
        assert(l == qr + 1);
    }

    void print(int p, int l, int r)
    {
        if (l == r)
        {
            for (int i = 0; i < 26; i++)
                if (nodes[p].a[i])
                {
                    cout << (char)(i + 'a');
                }
        }
        else
        {
            pushdown(p, l, r);
            print(p * 2, l, (l + r) / 2);
            print(p * 2 + 1, (l + r) / 2 + 1, r);
        }
    }

    void Print()
    {
        print(1, 1, n);
    }
};

signed main()
{
    ios::sync_with_stdio(false);

    int n, m;
    string s;
    cin >> n >> m >> s;

    SegmentTree seg(n);
    seg.Build(s);

    for (int i = 1; i <= m; i++)
    {
        int l, r, k;
        cin >> l >> r >> k;

        if (k == 1)
        {
            seg.SortAsc(l, r);
        }
        else
        {
            seg.SortDesc(l, r);
        }

        // seg.Print();
    }

    seg.Print();
}