558E - A Simple Task

Problem - E - Codeforces

• そもそも counting sort というのを初めて知った。使用制限があるが O(n) でソートできる高速ソート。それでも O(N*Q) になってしまう計算量をどう落とすか？
• 想定解法は segment tree を使うやつらしいけど、segment tree まだちゃんと勉強してないので別実装にした。(遅延評価実装面倒そうだし。)
• Codeforces #312 Div2 E. A Simple Task - kmjp's blogの解法を参照。(editorial のコメントでも似た解法の人がいた。そっちも参照。)
• 文字列を区間と文字の組と考えて counting sort してやる。解法が短くてわかりやすくてカッコイイ。

class Div2E {
public:
    // counting_sort O(N) を使う。
    // 愚直な実装なら O(26*N*Q)
    void solve_TLE(void) {
            int N,Q;
            cin>>N>>Q;
            string str;
            cin>>str;

            REP(_, Q)
            {
                int x,y,d;
                cin>>x>>y>>d;
                --x;
                --y;
                // 文字の出現回数をカウント
                vector<int> cnt(26,0);
                for (int i = x; i <= y; ++i)
                    ++cnt[str[i]-'a'];

                int k = x;
                REP(i, 26)
                {
                    // d の値に応じて順 or 逆順に見る
                    int j = (d==1)? i : 25-i;
                    // 出現してない文字は使わない
                    if (cnt[j] == 0)
                        continue;
                    REP(ii, cnt[j])
                        str[k++] = j+'a';
                }
            }
            cout<<str<<endl;
    }
    // counting_sort を高速化する。
    // 想定解法は segment tree 26 個を使って
    //  1. [x,y] 間の a-z の出現回数を取得する。
    //  2. ソート後の [x,y] 間の a-z の出現回数を更新する。 <- 遅延評価をつかって O(log(N)) にする必要がある。
    //
    // 以下は segment tree を使わない別解法
    void solve_optim() {
            int N,Q;
            cin>>N>>Q;
            string str;
            cin>>str;

            // 文字列を開始・終了位置と文字の区間の集合として表す
            //     [i,j,'a']
            // ...xxxaaaaaaxxxx...
            //       i    j
            set<tuple<int,int,char>> S;
            int last = 0;
            FOR(i, 1, N)
            {
                if (str[last] == str[i])
                    continue;
                S.emplace(last, i-1, str[last]);
                last = i;
            }
            S.emplace(last, N-1, str[last]);

            const int inf = (1<<30);
            REP(_, Q)
            {
                int x,y,d;
                cin>>x>>y>>d;
                --x;
                --y;

                // O(log(n))
                // [x,y] を含む区間を探す
                //    [x    ,  y]
                //  [i0,j0]...[i1,j1]
                auto itX = S.lower_bound(make_tuple(x,inf,inf));
                auto itY = S.lower_bound(make_tuple(y,inf,inf));
                auto itYE = itY;
                --itX;
                --itY;

                assert(get<0>(*itX) <= x && x <= get<1>(*itX));
                assert(get<0>(*itY) <= y && y <= get<1>(*itY));
                // ソート必要なし
                if (itX == itY)
                    continue;

                // 文字の出現回数をカウント
                vector<int> cnt(26,0);

                // sort が進むに連れ S のサイズが小さくなるから
                // amotized O(log(n))
                for (auto it = itX; it != itYE; ++it)
                {
                    int i,j;
                    char c;
                    tie(i,j,c) = *it;
                    //   [x  ,   y]
                    // [i , j]
                    i = max(x,i);
                    j = min(j,y);
                    cnt[c-'a'] += (j-i+1); // count
                }
                // ソート済み文字列を振り分け
                vector<tuple<int,int,char>> words;

                // 境界処理
                //   [x , y]
                // [i, j]       ->   [i,x-1][x,j][j+1,
                int  ii;
                char cc;
                tie(ii,ignore,cc) = *itX;
                if (ii < x)
                    words.emplace_back(ii,x-1,cc);
                tie(ignore,ii,cc) = *itY;
                if (y < ii)
                    words.emplace_back(y+1,ii,cc);

                // 区間を削除
                S.erase(itX,itYE);

                int k = x;
                REP(i, 26)
                {
                    // d の値に応じて順 or 逆順に見る
                    int j = (d==1)? i : 25-i;
                    // 出現してない文字は使わない
                    if (cnt[j] == 0)
                        continue;
                    S.emplace(k,k+cnt[j]-1,j+'a');
                    k += cnt[j]; // 位置ずらし
                }
                for (auto w : words)
                    S.insert(w);
            }
            string ans;
            for (auto w : S)
            {
                int i,j;
                char c;
                tie(i,j,c) = w;
                ans += string(j-i+1,c);
            }
            cout<<ans<<endl;
    }
    void solve(void) {
            solve_optim();
    }
};