Codeforces Round #312 (Div. 2) E. A Simple Task

問題

codeforces.com

解法

毎回のクエリでは, 区間内に存在する文字数を記録し, その文字数ごとにそれぞれの文字を区間に並べなおす, ということをします。
例えば
abababbba
という文字列で
2 6 1
というクエリが渡された場合,
区間[2, 6] には a が 2 文字, b が 3 文字あります。よって, 区間[2, 6] を aabbb と並べ直せば良いわけですが, これは要するに
区間[2, 3] は a が 2 文字で他の文字はナシ, 区間[4, 6] には b が 3 文字で他の文字はナシ, というようにすれば良いということです。

この操作をするために, 遅延評価つきセグメント木を使いました。
やっとコツわかってきたんですが, 区間が包含されて収まったところから先は lazy で抑えれば良いんですが収まったところそのものは遅延だけじゃなくてちゃんと確定させないといけないんですね(確定させたあと戻ってきたところでは tree の値が確定してないと困るので)。

const int MAXN = 100010;
int tree[4*MAXN][27], lazy[4*MAXN][27];
char s[MAXN];

void build(int k, int l, int r) {
    for (int i = 0; i < 26; i++) lazy[k][i] = -1;
    if (r-l == 1) {
        tree[k][s[l]-'a'] = 1;
        return;
    }
    build(2*k+1, l, (l+r)/2);
    build(2*k+2, (l+r)/2, r);
    for (int i = 0; i < 26; i++) {
        tree[k][i] = tree[2*k+1][i] + tree[2*k+2][i];
    }
}

int query(int k, int l, int r, int x, int y, int j) {
    if (lazy[k][j] != -1) {
        tree[k][j] = lazy[k][j] * (r-l);
        if (r-l > 1) {
            lazy[2*k+1][j] = lazy[k][j];
            lazy[2*k+2][j] = lazy[k][j];
        }
        lazy[k][j] = -1;
    }
    if (r <= x || y <= l) return 0;
    if (x <= l && r <= y) return tree[k][j];
    return query(2*k+1, l, (l+r)/2, x, y, j) + query(2*k+2, (l+r)/2, r, x, y, j);
}

void update(int k, int l, int r, int x, int y, int val, int j) {
    if (lazy[k][j] != -1) {
        tree[k][j] = lazy[k][j] * (r-l);
        if (r-l > 1) {
            lazy[2*k+1][j] = lazy[k][j];
            lazy[2*k+2][j] = lazy[k][j];
        }
        lazy[k][j] = -1;
    }
    if (r <= x || y <= l) {
        return;
    }
    if (x <= l && r <= y) {
        lazy[k][j] = val;
        tree[k][j] = val*(r-l);
        if (r-l > 1) {
            lazy[2*k+1][j] = lazy[k][j];
            lazy[2*k+2][j] = lazy[k][j];
        }
        lazy[k][j] = -1;
        return;
    }
    update(2*k+1, l, (l+r)/2, x, y, val, j);
    update(2*k+2, (l+r)/2, r, x, y, val, j);
    tree[k][j] = tree[2*k+1][j] + tree[2*k+2][j];
}

void get(int k, int l, int r, int j) {
    if (lazy[k][j] != -1) {
        tree[k][j] = lazy[k][j] * (r-l);
        if (r-l > 1) {
            lazy[2*k+1][j] = lazy[k][j];
            lazy[2*k+2][j] = lazy[k][j];
        }
        lazy[k][j] = -1;
    }
    if (!tree[k][j]) return;
    if (r-l == 1) {
        s[l] = 'a'+j;
        return;
    }
    get(2*k+1, l, (l+r)/2, j);
    get(2*k+2, (l+r)/2, r, j);
}

int cnt[26];

int main() {
    int n, q;
    cin >> n >> q;
    scanf("%s", s);
    build(0, 0, n);
    while (q--) {
        int x, y, up;
        scanf("%d%d%d", &x, &y, &up);
        x--;
        int cur = x;
        if (!up) cur = y;
        for (int i = 0; i < 26; i++) cnt[i] = query(0, 0, n, x, y, i);
        for (int i = 0; i < 26; i++) update(0, 0, n, x, y, 0, i);
        for (int i = 0; i < 26; i++) {
            if (cnt[i] == 0) continue;
            if (up) {
                update(0, 0, n, cur, cur+cnt[i], 1, i);
                cur += cnt[i];
            } else {
                update(0, 0, n, cur-cnt[i], cur, 1, i);
                cur -= cnt[i];
            }
        }
    }
    for (int i = 0; i < 26; i++) get(0, 0, n, i);
    printf("%s\n", s);
    return 0;
}