【每日一题】2021年4月9日题目 A Simple Task

题号 NC111013
名称 A Simple Task
来源 CF558E

时间限制：C/C++ 5秒，其他语言10秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

给定一个长度的由小写值字母构成的字符串，给定组询问形式为

l r k

如果,令区间内的元素按照非递增的顺序排序

如果,令区间内的元素按照非递减的顺序排序

输出执行次操作后的序列

样例

示例1
输入
10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1
输出
cbcaaaabdd

示例2
输入
10 1
agjucbvdfk
1 10 1
输出
abcdfgjkuv

算法1

(线段树区间覆盖 + 维护区间排序 + 计数排序)

又是一道线段树的套路题,毕竟线段树只有做过的套路题和没做过的套路题

我们发现给定的是一个只有26个小写字母的字符串

也就是说元素的值域很小，适用于数据范围较小的排序我们可以想到计数排序

计数排序：(思想：统计小于等于当前数的个数有多少个)

1. 先用一个桶将所有元素出现的次数统计出来,记录元素出现的次数
2. 然后对做一遍前缀和
3. 则如果表示出现过，且从小到大排序后的出现位置是

线段树维护：

我们维护一个lazy表示区间覆盖的标志，sum储存区间和

用一个单独的线段树维护每一个字母在某个区间出现的次数

如果对区间进行（从大到小排序）的操作，则从元素a ~ z的顺序遍历不同线段树的区间依次将字母从左端堆积起来

如果对区间进行1（从小到大排序）的操作，则从元素z ~ a的顺序遍历不同线段树的区间依次将字母从左端堆积起来

最后对单个区间访问每个字母输出答案

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
//#include <unordered_map>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
const int N = 100010;
struct Node
{
    int l,r;
    int cnt;
    int lazy;
}tr[30][N * 4];
int n,m;
char str[N];
int s[N];

void pushup(int u,int i)
{
    tr[i][u].cnt = (tr[i][lc].cnt + tr[i][rc].cnt);
}

void pushdown(int u,int t)
{
    if(tr[t][u].lazy != -1)
    {
        tr[t][lc].lazy = tr[t][rc].lazy = tr[t][u].lazy;
        if(tr[t][u].lazy == 0)
        {
            tr[t][lc].cnt = tr[t][rc].cnt = 0;
        }else
        {
            tr[t][lc].cnt = (tr[t][lc].r - tr[t][lc].l + 1);
            tr[t][rc].cnt = (tr[t][rc].r - tr[t][rc].l + 1);
        }
        tr[t][u].lazy = -1;
    }
}

void build(int u,int l,int r)
{
    for(int i = 0;i < 26;i ++)
        tr[i][u] = {l,r,0,-1};
    if(l == r)
    {
        tr[s[l]][u].cnt = 1;
        return;
    }
    int mid = l + r >> 1;
    build(lc,l,mid);
    build(rc,mid + 1,r);
    for(int i = 0;i < 26;i ++)
        pushup(u,i);
}

void modify(int u,int l,int r,int t,int k)
{
    if(tr[t][u].l >= l && tr[t][u].r <= r)
    {
        if(k == 0) tr[t][u].cnt = 0;
        if(k == 1) tr[t][u].cnt = (tr[t][u].r - tr[t][u].l + 1);
        tr[t][u].lazy = k;
        return;
    }
    pushdown(u,t);
    int mid = (tr[t][u].l + tr[t][u].r) >> 1;
    if(l <= mid) modify(lc,l,r,t,k);
    if(r > mid) modify(rc,l,r,t,k);
    pushup(u,t);
}

int query(int u,int l,int r,int t)
{
    if(tr[t][u].l >= l && tr[t][u].r <= r) return tr[t][u].cnt;
    pushdown(u,t);
    int mid = (tr[t][u].l + tr[t][u].r) >> 1;
    int res = 0;
    if(l <= mid) res += query(lc,l,r,t);
    if(r > mid) res += query(rc,l,r,t);
    return res;
}

void solve()
{
    scanf("%d%d",&n,&m);
    scanf("%s",str + 1);
    for(int i = 1;i <= n;i ++) s[i] = str[i] - 'a';
    build(1,1,n);
    while(m --)
    {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        if(k == 1)
        {
            int ans = 0,j = l;
            for(int i = 0;j <= r && i < 26;i ++)
            {
                ans = query(1,l,r,i);
                if(!ans) continue;
                modify(1,l,r,i,0);
                modify(1,j,j + ans - 1,i,1);
                j += ans;
            }
        }else
        {
            int ans = 0,j = l;
            for(int i = 25;j <= r && i >= 0;i --)
            {
                ans = query(1,l,r,i);
                if(!ans) continue;
                modify(1,l,r,i,0);
                modify(1,j,j + ans - 1,i,1);
                j += ans;
            }
        }
    }
    for(int i = 1;i <= n;i ++)
    {
        int j;
        for(j = 0;j < 26;j ++)
        {
            if(query(1,i,i,j) != 0)
                break;
        }
        str[i] = j + 'a';
    }
    printf("%s\n",str + 1);
}

int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #else
    #endif // LOCAL
    int T = 1;
    // init(N - 1);
    // scanf("%d",&T);
    while(T --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}