【题解】A Simple Task 线段树 CodeForces – 558E

于由XZYQvQ发布

1. 题目

传送门=￣ω￣=

大意：给你一个长度为 N 的字符串 ($N\leq 10^5$)，给你 M 个操作（$M\leq 50000$），每次操作给定 l,r，要求将字符串的区间 [l,r] 按字典序升序或降序排序，最后输出所有操作之后的字符串。

2. 题解

用线段树当桶用。

搞 26 棵线段树，第 i 棵代表了小写字符’a’+i（i 从 0 开始）

即用线段树统计每个区间内某个小写字母出现了多少次。

设 26 棵线段树分别为 $T[0],T[1],T[2],…,T[24],T[25]$，$T[i].query(l,r)$表示统计区间 [l,r] 中出现了多少个字符’a’+i，$T[i].update(l,r,k)$表示对代表字符’a’+i 的线段树进行区间覆盖操作（赋为 k）

那么如果我们要统计字符’a’ 在区间 [2,5] 出现了多少次，那么就写：

T[0].query(2,5)

还比如我们要统计字符’z’ 在区间 [1,7] 出现了多少次，那么就写：

T[25].query(1,7)

大概就是这个意思。

然后初始的时候每个区间都设为 0。

接着设给出的字符串为 s（为 char 型，下标从 1 开始）

那么初始化就这么写：

for(int i=1;i<=s.length();i++)
    T[s[i]-'a'].update(i,i,1);

即：让字母 s[i] 在区间 [i,i] 的个数变为 1

对于每次排序操作：

数据给出了三个参数：l,r,k，k=1 时表示对区间 [l,r] 升序排序，k=0 时表示对区间 [l,r] 降序排序。

我们首先统计 26 个字母在区间 [l,r] 中出现了几次，设区间 [l,r] 中字符’a’+i 出现了 $cnt[i]$次。

1. 题目

传送门=￣ω￣=

大意：给你一个长度为 N 的字符串 ($N\leq 10^5$)，给你 M 个操作（$M\leq 50000$），每次操作给定 l,r，要求将字符串的区间 [l,r] 按字典序升序或降序排序，最后输出所有操作之后的字符串。

2. 题解

用线段树当桶用。

搞 26 棵线段树，第 i 棵代表了小写字符’a’+i（i 从 0 开始）

即用线段树统计每个区间内某个小写字母出现了多少次。

设 26 棵线段树分别为 $T[0],T[1],T[2],…,T[24],T[25]$，$T[i].query(l,r)$表示统计区间 [l,r] 中出现了多少个字符’a’+i，$T[i].update(l,r,k)$表示对代表字符’a’+i 的线段树进行区间覆盖操作（赋为 k）

那么如果我们要统计字符’a’ 在区间 [2,5] 出现了多少次，那么就写：

T[0].query(2,5)

还比如我们要统计字符’z’ 在区间 [1,7] 出现了多少次，那么就写：

T[25].query(1,7)

大概就是这个意思。

然后初始的时候每个区间都设为 0。

接着设给出的字符串为 s（为 char 型，下标从 1 开始）

那么初始化就这么写：

for(int i=1;i<=s.length();i++)
    T[s[i]-'a'].update(i,i,1);

即：让字母 s[i] 在区间 [i,i] 的个数变为 1

对于每次排序操作：

数据给出了三个参数：l,r,k，k=1 时表示对区间 [l,r] 升序排序，k=0 时表示对区间 [l,r] 降序排序。

我们首先统计 26 个字母在区间 [l,r] 中出现了几次，设区间 [l,r] 中字符’a’+i 出现了 $cnt[i]$次。

那么代码这么写：

for(int i=0,cnt[26];i<26;i++)
    cnt[i]=T[i].query(l,r);

然后我们将每个线段树的区间 [l,r] 清空：

for(int i=0;i<26;i++)
    T[i].update(l,r,0);

这时候我们得到了每个字符在区间内出现了多少次，以升序排序为例：

排序后的区间将会是这种情况：

前 cnt[0] 个字符全部是’a’，接着 cnt[1] 个字符全部是’b’，接着 cnt[2] 个字符全部是’c’… 接着 cnt[i] 个字符全部是’a’+i。

那么我们只要再来区间覆盖即可：

for(int i=0,tot=a;i<26;i++)
    T[i].update(tot,tot+cnt[i]-1),tot+=cnt[i];

最后统计答案：
怎么求答案第 i 位上的字符呢？
可以枚举 x，若 T[x].query(i,i) 为 1，那么答案第 i 为上的字符就是’a’+x

于是我们就在 $O(26Mlog_2 N)$的复杂度内解决了这个问题。

原题时限 5s，然而模拟考试中时限 1s，可以直接开 O2 卡过，当然我也想了一些优化成果以 996ms 的时间卡过。

优化：

  1. 因为清空和查询必然在一起执行，所以可以直接把它们写一个函数中
  2. 查询答案可以跑 dfs，不要一个一个位置地枚举，要直接一次算出所有答案
  3. 读入优化（包括字符串读入优化，最后是字符串的读入优化让我卡进了 996ms）

具体看代码吧：

#include <bits/stdc++.h>
#define LS(a) (a<<1)
#define RS(a) ((a<<1)|1)
#define NS (100005)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;dig=0;
    while(c=getchar(),!isdigit(c));
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int n,m,ans[NS];
char s[NS];
struct N{int l,r,d,z;};
struct seg
{
    N e[NS<<2];
    void build(int l,int r,int a)
    {
        e[a].l=l,e[a].r=r,e[a].d=0,e[a].z=-1;
        if(l==r)return;
        build(l,(l+r)>>1,LS(a)),build(((l+r)>>1)+1,r,RS(a));
    }
    void pdown(int a)
    {
        e[LS(a)].d=(e[LS(a)].r-e[LS(a)].l+1)*e[a].z;
        e[RS(a)].d=(e[RS(a)].r-e[RS(a)].l+1)*e[a].z;
        e[LS(a)].z=e[RS(a)].z=e[a].z,e[a].z=-1;
    }
    void pup(int a){e[a].d=e[LS(a)].d+e[RS(a)].d;}
    void update(int l,int r,int a)
    {
        if(l>r)return;
        if(e[a].d==e[a].r-e[a].l+1)return;
        if(l<=e[a].l&&e[a].r<=r){e[a].d=e[a].r-e[a].l+1,e[a].z=1;return;}
        if(e[a].z>-1)pdown(a);
        if(l<=e[LS(a)].r)update(l,r,LS(a));
        if(r>=e[RS(a)].l)update(l,r,RS(a));
        pup(a);
    }
    int query(int l,int r,int a)
    {
        if(e[a].d==0)return 0;
        if(l<=e[a].l&&e[a].r<=r)
        {
            int tem=e[a].d;
            e[a].d=0,e[a].z=0;
            return tem;
        }
        if(e[a].z>-1)pdown(a);
        int tot=0;
        if(l<=e[LS(a)].r)tot+=query(l,r,LS(a));
        if(r>=e[RS(a)].l)tot+=query(l,r,RS(a));
        pup(a);
        return tot;
    }
    void get_ans(int c,int a)
    {
        if(e[a].d==0)return;
        if(e[a].l==e[a].r){ans[e[a].l]=c;return;}
        if(e[a].z>-1)pdown(a);
        get_ans(c,LS(a)),get_ans(c,RS(a));
    }
}T[26];
int main()
{
    IN(n),IN(m);
    while(s[1]=getchar(),!isalpha(s[1]));
    for(int i=2;i<=n;i++)s[i]=getchar();
    for(int i=0;i<26;i++)T[i].build(1,n,1);
    for(int i=1;i<=n;i++)T[s[i]-'a'].update(i,i,1);
    for(int i=1,a,b,c,cnt[26];i<=m;i++)
    {
        IN(a),IN(b),IN(c);
        for(int i=0;i<26;i++)cnt[i]=T[i].query(a,b,1);
        if(c)for(int i=0,tot=a;i<26;i++)
            T[i].update(tot,tot+cnt[i]-1,1),tot+=cnt[i];
        else for(int i=25,tot=a;i>=0;i--)
            T[i].update(tot,tot+cnt[i]-1,1),tot+=cnt[i];
    }
    for(int i=25;i>=0;i--)T[i].get_ans(i,1);
    for(int i=1;i<=n;i++)putchar('a'+ans[i]);
    return 0;
}

那么代码这么写：

for(int i=0,cnt[26];i<26;i++)
    cnt[i]=T[i].query(l,r);

然后我们将每个线段树的区间 [l,r] 清空：

for(int i=0;i<26;i++)
    T[i].update(l,r,0);

这时候我们得到了每个字符在区间内出现了多少次，以升序排序为例：

排序后的区间将会是这种情况：

前 cnt[0] 个字符全部是’a’，接着 cnt[1] 个字符全部是’b’，接着 cnt[2] 个字符全部是’c’… 接着 cnt[i] 个字符全部是’a’+i。

那么我们只要再来区间覆盖即可：

for(int i=0,tot=a;i<26;i++)
    T[i].update(tot,tot+cnt[i]-1),tot+=cnt[i];

最后统计答案：
怎么求答案第 i 位上的字符呢？
可以枚举 x，若 T[x].query(i,i) 为 1，那么答案第 i 为上的字符就是’a’+x

于是我们就在 $O(26Mlog_2 N)$的复杂度内解决了这个问题。

原题时限 5s，然而模拟考试中时限 1s，可以直接开 O2 卡过，当然我也想了一些优化成果以 996ms 的时间卡过。

优化：

  1. 因为清空和查询必然在一起执行，所以可以直接把它们写一个函数中
  2. 查询答案可以跑 dfs，不要一个一个位置地枚举，要直接一次算出所有答案
  3. 读入优化（包括字符串读入优化，最后是字符串的读入优化让我卡进了 996ms）

具体看代码吧：

#include <bits/stdc++.h>
#define LS(a) (a<<1)
#define RS(a) ((a<<1)|1)
#define NS (100005)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;dig=0;
    while(c=getchar(),!isdigit(c));
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int n,m,ans[NS];
char s[NS];
struct N{int l,r,d,z;};
struct seg
{
    N e[NS<<2];
    void build(int l,int r,int a)
    {
        e[a].l=l,e[a].r=r,e[a].d=0,e[a].z=-1;
        if(l==r)return;
        build(l,(l+r)>>1,LS(a)),build(((l+r)>>1)+1,r,RS(a));
    }
    void pdown(int a)
    {
        e[LS(a)].d=(e[LS(a)].r-e[LS(a)].l+1)*e[a].z;
        e[RS(a)].d=(e[RS(a)].r-e[RS(a)].l+1)*e[a].z;
        e[LS(a)].z=e[RS(a)].z=e[a].z,e[a].z=-1;
    }
    void pup(int a){e[a].d=e[LS(a)].d+e[RS(a)].d;}
    void update(int l,int r,int a)
    {
        if(l>r)return;
        if(e[a].d==e[a].r-e[a].l+1)return;
        if(l<=e[a].l&&e[a].r<=r){e[a].d=e[a].r-e[a].l+1,e[a].z=1;return;}
        if(e[a].z>-1)pdown(a);
        if(l<=e[LS(a)].r)update(l,r,LS(a));
        if(r>=e[RS(a)].l)update(l,r,RS(a));
        pup(a);
    }
    int query(int l,int r,int a)
    {
        if(e[a].d==0)return 0;
        if(l<=e[a].l&&e[a].r<=r)
        {
            int tem=e[a].d;
            e[a].d=0,e[a].z=0;
            return tem;
        }
        if(e[a].z>-1)pdown(a);
        int tot=0;
        if(l<=e[LS(a)].r)tot+=query(l,r,LS(a));
        if(r>=e[RS(a)].l)tot+=query(l,r,RS(a));
        pup(a);
        return tot;
    }
    void get_ans(int c,int a)
    {
        if(e[a].d==0)return;
        if(e[a].l==e[a].r){ans[e[a].l]=c;return;}
        if(e[a].z>-1)pdown(a);
        get_ans(c,LS(a)),get_ans(c,RS(a));
    }
}T[26];
int main()
{
    IN(n),IN(m);
    while(s[1]=getchar(),!isalpha(s[1]));
    for(int i=2;i<=n;i++)s[i]=getchar();
    for(int i=0;i<26;i++)T[i].build(1,n,1);
    for(int i=1;i<=n;i++)T[s[i]-'a'].update(i,i,1);
    for(int i=1,a,b,c,cnt[26];i<=m;i++)
    {
        IN(a),IN(b),IN(c);
        for(int i=0;i<26;i++)cnt[i]=T[i].query(a,b,1);
        if(c)for(int i=0,tot=a;i<26;i++)
            T[i].update(tot,tot+cnt[i]-1,1),tot+=cnt[i];
        else for(int i=25,tot=a;i>=0;i--)
            T[i].update(tot,tot+cnt[i]-1,1),tot+=cnt[i];
    }
    for(int i=25;i>=0;i--)T[i].get_ans(i,1);
    for(int i=1;i<=n;i++)putchar('a'+ans[i]);
    return 0;
}
分类： 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注