Codeforces 558E A Simple Task (简单题)

66 阅读 0 评论 44 点赞

我是靠谱客的博主无情黑米，最近开发中收集的这篇文章主要介绍Codeforces 558E A Simple Task (简单题)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目类型 简单题

题目意思

对于一个最多 1e5 长的字符串(只包含小写字母) 有 50000 个操作

每个操作参数为 l, r, k (当k == 1时表示将子串 (l, r) 中的子符非降序排序当 k == 0时非升序)

问 50000 个操作后得到的字符串是什么

解题方法

分析一下可以发现突破口在于字符串只包含小写字母，即最多26种不同字符

那么如果某一段字符区间排序后形成的就是一段段相同的字符且段数最多只是26段

当一个操作是在一段相同字符里面进行的相当于不执行

方法一：

把字符串连续相同的部分压缩在一起例如 bbbbddddcca 压缩成 4b4d2c1a (可以记录每一段相同字符的起始位置)

当需要更新 [l, r]的状态时可以二分找到需要更新的起始段和结束段，把中间要更新的段通过计数排序重新整理，其他不受影响的相同字符段不需要变动

当更新位于同一相同字符段时不需要更新

方法二：

建立26棵线段树分别保存某一种字符在某个区间内的总数

那么在更新 [l, r]时可以 query 每个字符在 [l, r] 的数量然后用计数排序的方法得到新的 [l, r]的情况把这个新的情况更新到线段树中

最后对于字符串每一个位置的 query 各个字符在这个位置的数量如果某个字符在这个位置有数量说明最终这个位置上就是这个字符输出即可

过程中要使用懒惰标记具体看代码 (stat[w][rt] == 0 说明这一整段都不包含 w+'a' 这个字符; stat[w][rt] == 1 说明这一整段都是 w+'a'这个字符)

参考代码 - 有疑问的地方在下方留言看到会尽快回复的

方法一

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int MAXN = (int)1e5 + 10;
char str[MAXN];
int n_str[MAXN];
int type[MAXN*4];

struct S {
    int ch;
    int npre;
    int pos;
}s[MAXN];

void bsearch(int k, int l, int r, int& rL, int& rR) {
    int L = 0, R = k-1;
    while(L <= R) {
        int mid = (L+R)/2;
        if(l >= s[mid].pos && l <= s[mid].pos + s[mid].npre -1) {
            rL = mid;
            break;
        }
        else if(l < s[mid].pos) R = mid - 1;
        else L = mid + 1;
    }

    L = 0, R = k-1;
    while(L <= R) {
        int mid = (L+R)/2;
        if(r >= s[mid].pos && r <= s[mid].pos + s[mid].npre -1) {
            rR = mid;
            break;
        }
        else if(r < s[mid].pos) R = mid - 1;
        else L = mid + 1;
    }
}

int main() {
    freopen("in", "r", stdin);
    int n, q;
    while(scanf("%d%d", &n, &q) != EOF) {
        scanf("%s", str);
        int sum[30];
        for( int i=0; i<n; i++ ) n_str[i] = str[i] - 'a';
        int k = 0;
        for( int i=0; i<n; i++ ) {
            int j;
            for( j=i+1; j<n && n_str[j] == n_str[j-1]; j++ ) ;
            s[k].ch = n_str[i];
            s[k].npre = j - i;
            s[k++].pos = i;
            i = j-1;
        }

        for( int i=0; i<q; i++ ) {
            int l, r;
            int t;
            scanf("%d%d%d", &l, &r, &t);
            l--, r--;
            int L;
            int R;
            bsearch(k, l, r, L, R);
            if(L == R) continue;
            memset(sum, 0, sizeof(sum));
            int dL = L+1;
            if(l == s[L].pos) dL = L; 
            else {
                sum[s[L].ch] += s[L].npre - (l - s[L].pos);
                s[L].npre = l - s[L].pos;
            }
            int dR = R;
            if(r == s[R].pos+s[R].npre-1) dR = R+1; 
            else {
                sum[s[R].ch] += r - s[R].pos + 1;
                s[R].npre = s[R].npre - (r - s[R].pos + 1);
                s[R].pos = r+1;
            }
            for( int j=dL; j<dR; j++ ) {
                sum[s[j].ch] += s[j].npre;
            }
            int cnt = 0;
            for( int j=0; j<26; j++ ) if(sum[j]) cnt++;
            if(dL + cnt + k - dR != k) {
                if(dL+cnt > dR) {
                    for( int j=k-1; j>=dR; j-- ) {
                        s[dL+cnt+(j-dR)] = s[j];
                    }
                }
                else {
                    for( int j=dR; j<k; j++ ) {
                        s[dL+cnt+(j-dR)] = s[j];
                    }
                }
            }
            k = dL + cnt + k - dR;
            if(t == 1) { //s
                for( int j=0; j<26; j++ ) {
                    if(sum[j]) {
                        s[dL].ch = j;
                        s[dL].npre = sum[j];
                        s[dL].pos = s[dL-1].pos + s[dL-1].npre;
                        dL++;
                    }
                }
            }
            else {
                for( int j=25; j>=0; j-- ) {
                    if(sum[j]) {
                        s[dL].ch = j;
                        s[dL].npre = sum[j];
                        s[dL].pos = s[dL-1].pos + s[dL-1].npre;
                        dL++;
                    }
                }
            }
        }
        for( int i=0; i<k; i++ ) for( int j=0; j<s[i].npre; j++ ) printf("%c", s[i].ch+'a');
        printf("n");
    }
    return 0;
}

方法二

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

#define ls (rt<<1)
#define rs ((rt<<1)|1)
#define mid ((l+r)>>1)

const int MAXN = 1e5 + 10;
char str[MAXN];
int n_str[MAXN];
int num[27][MAXN*4];
int stat[27][MAXN*4];

void pushdown(int rt, int l, int r, int w) {
    if(stat[w][rt] != -1) {
        if(l == r) return ;
        stat[w][ls] = stat[w][rs] = stat[w][rt];
        if(stat[w][rt]) {
            num[w][ls] = mid - l + 1;
            num[w][rs] = r - mid;
        }
        else num[w][ls] = num[w][rs] = 0;
        stat[w][rt] = -1;
    }
}

void update(int rt, int l, int r, int L, int R, int w, int type) {
    pushdown(rt, l, r, w);
    if(l == L && r == R) {
        stat[w][rt] = type;
        if(type) num[w][rt] = r - l + 1;
        else num[w][rt] = 0;
        return ;
    }
    if(R <= mid) update(ls, l, mid, L, R, w, type);
    else if(L > mid) update(rs, mid + 1, r, L, R, w, type);
    else {
        update(ls, l, mid, L, mid, w, type);
        update(rs, mid + 1, r, mid + 1, R, w, type);
    }
    num[w][rt] = num[w][ls] + num[w][rs];
}

int query(int rt, int l, int r, int L, int R, int w) {
    pushdown(rt, l, r, w);
    if(l == L && r == R) return num[w][rt];
    if(R <= mid) return query(ls, l, mid, L, R, w);
    else if(L > mid) return query(rs, mid + 1, r, L, R, w);
    else {
        return query(ls, l, mid, L, mid, w) + query(rs, mid + 1, r, mid + 1, R, w);
    }
    num[w][rt] = num[w][ls] + num[w][rs];
}


int main() {
    freopen("in", "r", stdin);
    int n, q;
    while(scanf("%d%d", &n, &q) != EOF) {
        scanf("%s", str);
        int sum[30];
        memset(num, 0, sizeof(num));
        memset(stat, -1, sizeof(stat));
        for( int i=0; i<n; i++ ) {
            n_str[i] = str[i] - 'a';
            update(1, 0, n-1, i, i, n_str[i], 1);
        }
        for( int i=0; i<q; i++ ) {
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            l--, r--;
            for( int j=0; j<26; j++ ) {
                sum[j] = query(1, 0, n-1, l, r, j);
                update(1, 0, n-1, l, r, j, 0);
            }
            if(k == 1) {
                int pos = l;
                for( int j=0; j<26; j++ ) {
                    while(j < 26 && sum[j] == 0) j++;
                    if(j >= 26) break;
                    update(1, 0, n-1, pos, pos + sum[j] - 1, j, 1);
                    pos += sum[j];
                }
            }
            else {
                int pos = l;
                for( int j=25; j>=0; j-- ) {
                    while(j >=0  && sum[j] == 0) j--;
                    if(j < 0) break;
                    update(1, 0, n-1, pos, pos + sum[j] - 1, j, 1);
                    pos += sum[j];
                }
            }
        }
        for( int i=0; i<n; i++ ) {
            for( int j=0; j<26; j++ ) {
                if(query(1, 0, n-1, i, i, j)) {
                    printf("%c", j+'a');
                    break;
                }
            }
        }
        printf("n");
    }
    return 0;
}