ACM模版

描述

题解

一开始看到讨论区有人说，将排序部分改成 O(n) 就行了，然后我就傻傻的以为，计数排序搞一下就行了，然后，果然，无情 TLE 了四五组数据，后来知道了这个可以用线段树写，建 26 棵线段树，分别维护每种字母在不同区间的出现次数（计数部分），试了试，依然挂了一组数据，然后加上了输入输出外挂，险过，差一丢丢就挂了……

后来呢，看到有人用 splay 解得，有些厉害了，我还没有用 splay 写过题呢，这次学习一下，真是一个不错的东西，虽然代码有些繁琐，但是效果真是立竿见影，跑得贼溜！！！

看来今天晚上要着重复习复习伸展树了~~~

这次提供的代码既不是线段树也不是伸展树，而是 STL 中 set 的应用， set 的内部实现是红黑树，也是强大的很。这个代码思路也是极其有趣，维护一个 cnt[i][j] 表示以 i 开头的紧跟着的有序序列的每种字母的个数，维护过程需要两个函数，分裂（ split() ）和合并（ merge() ）操作，先将区间根据 l 和 r+1 分裂，然后将该区间合并在一起保存到 cnt[l][j] 表示从 l 开始的有序序列的每种字母的个数，保存一个 vis[] 标记每个合并后的区间的有序方向。是不是很巧妙，简直了！！！

代码

#include <cstdio>
#include <vector>
#include <iostream>
#include <set>

using namespace std;

const int MAXN = 1e5 + 10;
const int MAXK = 26;

int n, q;
bool vis[MAXN];
char s[MAXN];
char ans[MAXN];
int cnt[MAXN][MAXK];    // cnt[i][j] 以 i 开头的后边紧跟着的有序序列每种字母的个数
set<int> si;

void split(int p)
{
    int l, len;
    auto it = si.lower_bound(p);
    if (*it == p)
    {
        return ;
    }
    len = *it;
    l = *(--it);
    len -= l;

    vis[p] = vis[l];

    if (!vis[l])
    {
        for (int i = 0; i < MAXK; i++)
        {
            if (len - cnt[l][i] > p - l)
            {
                cnt[p][i] += cnt[l][i];
                len -= cnt[l][i];
                cnt[l][i] = 0;
            }
            else
            {
                int num = len - (p - l);
                cnt[p][i] += num;
                cnt[l][i] -= num;
                break;
            }
        }
    }
    else
    {
        for (int i = MAXK - 1; i >= 0; i--)
        {
            if (len - cnt[l][i] > p - l)
            {
                cnt[p][i] += cnt[l][i];
                len -= cnt[l][i];
                cnt[l][i] = 0;
            }
            else
            {
                int num = len - (p - l);
                cnt[p][i] += num;
                cnt[l][i] -= num;
                break;
            }
        }
    }

    si.insert(p);
}

void merge(int l, int r, int k)
{
    vis[l] = k;
    vector<int> v;
    auto end = si.find(r);
    auto sta = si.find(l);

    for (sta++; sta != end; sta++)
    {
        for (int i = 0; i < MAXK; i++)
        {
            cnt[l][i] += cnt[*sta][i];
            cnt[*sta][i] = 0;
        }
        v.push_back(*sta);
    }

    for (int x : v)
    {
        si.erase(x);
    }
}

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

int main()
{
    scan_d(n), scan_d(q);
    scanf("%s", s + 1);

    for (int i = 1; i <= n; i++)
    {
        cnt[i][s[i] - 'a']++;
        si.insert(i);
        vis[i] = 1;
    }
    si.insert(n + 1);

    int l, r, k;
    while (q--)
    {
        scan_d(l), scan_d(r), scan_d(k);
        split(l), split(r + 1);
        merge(l, r + 1, k);
    }

    int pos = 1;
    for (int x : si)
    {
        if (vis[x])
        {
            for (int i = 0; i < MAXK; i++)
            {
                for (int j = 0; j < cnt[x][i]; j++)
                {
                    ans[pos++] = 'a' + i;
                }
            }
        }
        else
        {
            for (int i = MAXK - 1; i >= 0; i--)
            {
                for (int j = 0; j < cnt[x][i]; j++)
                {
                    ans[pos++] = 'a' + i;
                }
            }
        }
    }

    puts(ans + 1);

    return 0;
}