Codeforces 558E A Simple Task (计数排序+线段树优化)

98 阅读 0 评论 65 点赞

我是靠谱客的博主深情咖啡豆，这篇文章主要介绍Codeforces 558E A Simple Task (计数排序+线段树优化)，现在分享给大家，希望可以做个参考。

This task is very simple. Given a string S of length n and q queries each query is on the format i j k which means sort the substring consisting of the characters from i to j in non-decreasing order if k = 1 or in non-increasing order if k = 0.

Output the final string after applying the queries.

Input

The first line will contain two integers n, q (1 ≤ n ≤ 105, 0 ≤ q ≤ 50 000), the length of the string and the number of queries respectively.

Next line contains a string S itself. It contains only lowercase English letters.

Next q lines will contain three integers each i, j, k (1 ≤ i ≤ j ≤ n, $\text{[math]}$ ).

Output

Output one line, the string S after applying the queries.

   Sample test(s) 
 

     input 
   
复制代码10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1
10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1

     output 
   
复制代码cbcaaaabddcbcaaaabdd

     input 
   
复制代码10 1
agjucbvdfk
1 10 1
10 1
agjucbvdfk
1 10 1

     output 
   
复制代码abcdfgjkuvabcdfgjkuv

Note

First sample test explanation:

$\text{[math]}$

题意：

给定一个长度为n的字符串，有q次操作，每次操作将一个区间内的字符按升序或降序排列，输出q次操作后的字符串，串中只包含小写英文字母.

分析：

考虑到字符集大小只有26，联想到计数排序，对一个区间做一次排序相当于对区间内每一种字符分别统计一遍个数后，再按照字符的顺序（升序或降序）依次重新填进区间内，可以用26棵权值线段树分别维护每一种字符的位置，复杂度O(26nlogn+52qlogn)。

代码：

复制代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=100005;
int cnt[26];
char str[MAXN],ans[MAXN];
struct node
{
    int l,r,m,v,lazy;
}s[26][MAXN<<2];
void push_up(int n,int id)
{
    s[id][n].v=s[id][n<<1].v+s[id][n<<1|1].v;
}
void push_down(int n,int id)
{
    if(s[id][n].lazy<0)return;
    s[id][n<<1].v=(s[id][n<<1].r-s[id][n<<1].l)*s[id][n].lazy;
    s[id][n<<1].lazy=s[id][n].lazy;
    s[id][n<<1|1].v=(s[id][n<<1|1].r-s[id][n<<1|1].l)*s[id][n].lazy;
    s[id][n<<1|1].lazy=s[id][n].lazy;
    s[id][n].lazy=-1;
}
void build(int l,int r,int n,int id)
{
    int m=(l+r)>>1;
    s[id][n].l=l;
    s[id][n].r=r;
    s[id][n].m=m;
    s[id][n].lazy=-1;
    if(r-l==1)
    {
        s[id][n].v=(str[l-1]=='a'+id);
        return;
    }
    build(l,m,n<<1,id);
    build(m,r,n<<1|1,id);
    push_up(n,id);
}
void update(int l,int r,int n,int op,int id)
{
    if(s[id][n].l==l && s[id][n].r==r)
    {
        s[id][n].v=(s[id][n].r-s[id][n].l)*op;
        s[id][n].lazy=op;
        return;
    }
    push_down(n,id);
    if(r<=s[id][n].m)update(l,r,n<<1,op,id);
    else if(l>=s[id][n].m)update(l,r,n<<1|1,op,id);
    else
    {
        update(l,s[id][n].m,n<<1,op,id);
        update(s[id][n].m,r,n<<1|1,op,id);
    }
    push_up(n,id);
}
int query(int l,int r,int n,int id)
{
    if(s[id][n].l==l && s[id][n].r==r)
        return s[id][n].v;
    push_down(n,id);
    if(r<=s[id][n].m)
        return query(l,r,n<<1,id);
    if(l>=s[id][n].m)
        return query(l,r,n<<1|1,id);
    return query(l,s[id][n].m,n<<1,id)
            +query(s[id][n].m,r,n<<1|1,id);
}
int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    scanf("%s",str);
    for(int i=0;i<26;i++)build(1,n+1,1,i);
    int l,r,k;
    while(q--)
    {
        scanf("%d%d%d",&l,&r,&k);
        for(int i=0;i<26;i++)
        {
            cnt[i]=query(l,r+1,1,i);
            update(l,r+1,1,0,i);
        }
        if(k==1)
        {
            int loc=l;
            for(int i=0;i<26;i++)
            {
                if(cnt[i]>0)update(loc,loc+cnt[i],1,1,i);
                loc+=cnt[i];
            }
        }
        else
        {
            int loc=l;
            for(int i=25;i>=0;i--)
            {
                if(cnt[i]>0)update(loc,loc+cnt[i],1,1,i);
                loc+=cnt[i];
            }
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=0;j<26;j++)
            if(query(i,i+1,1,j))
            {
                ans[i-1]='a'+j;
                break;
            }
    printf("%sn",ans);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=100005;
int cnt[26];
char str[MAXN],ans[MAXN];
struct node
{
    int l,r,m,v,lazy;
}s[26][MAXN<<2];
void push_up(int n,int id)
{
    s[id][n].v=s[id][n<<1].v+s[id][n<<1|1].v;
}
void push_down(int n,int id)
{
    if(s[id][n].lazy<0)return;
    s[id][n<<1].v=(s[id][n<<1].r-s[id][n<<1].l)*s[id][n].lazy;
    s[id][n<<1].lazy=s[id][n].lazy;
    s[id][n<<1|1].v=(s[id][n<<1|1].r-s[id][n<<1|1].l)*s[id][n].lazy;
    s[id][n<<1|1].lazy=s[id][n].lazy;
    s[id][n].lazy=-1;
}
void build(int l,int r,int n,int id)
{
    int m=(l+r)>>1;
    s[id][n].l=l;
    s[id][n].r=r;
    s[id][n].m=m;
    s[id][n].lazy=-1;
    if(r-l==1)
    {
        s[id][n].v=(str[l-1]=='a'+id);
        return;
    }
    build(l,m,n<<1,id);
    build(m,r,n<<1|1,id);
    push_up(n,id);
}
void update(int l,int r,int n,int op,int id)
{
    if(s[id][n].l==l && s[id][n].r==r)
    {
        s[id][n].v=(s[id][n].r-s[id][n].l)*op;
        s[id][n].lazy=op;
        return;
    }
    push_down(n,id);
    if(r<=s[id][n].m)update(l,r,n<<1,op,id);
    else if(l>=s[id][n].m)update(l,r,n<<1|1,op,id);
    else
    {
        update(l,s[id][n].m,n<<1,op,id);
        update(s[id][n].m,r,n<<1|1,op,id);
    }
    push_up(n,id);
}
int query(int l,int r,int n,int id)
{
    if(s[id][n].l==l && s[id][n].r==r)
        return s[id][n].v;
    push_down(n,id);
    if(r<=s[id][n].m)
        return query(l,r,n<<1,id);
    if(l>=s[id][n].m)
        return query(l,r,n<<1|1,id);
    return query(l,s[id][n].m,n<<1,id)
            +query(s[id][n].m,r,n<<1|1,id);
}
int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    scanf("%s",str);
    for(int i=0;i<26;i++)build(1,n+1,1,i);
    int l,r,k;
    while(q--)
    {
        scanf("%d%d%d",&l,&r,&k);
        for(int i=0;i<26;i++)
        {
            cnt[i]=query(l,r+1,1,i);
            update(l,r+1,1,0,i);
        }
        if(k==1)
        {
            int loc=l;
            for(int i=0;i<26;i++)
            {
                if(cnt[i]>0)update(loc,loc+cnt[i],1,1,i);
                loc+=cnt[i];
            }
        }
        else
        {
            int loc=l;
            for(int i=25;i>=0;i--)
            {
                if(cnt[i]>0)update(loc,loc+cnt[i],1,1,i);
                loc+=cnt[i];
            }
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=0;j<26;j++)
            if(query(i,i+1,1,j))
            {
                ans[i-1]='a'+j;
                break;
            }
    printf("%sn",ans);
    return 0;
}