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]出现了多少次,那么就写:

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

大概就是这个意思。

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

接着设给出的字符串为s(为char型,下标从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]出现了多少次,那么就写:

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

大概就是这个意思。

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

接着设给出的字符串为s(为char型,下标从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]$次。

那么代码这么写:

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

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

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

前cnt[0]个字符全部是'a',接着cnt[1]个字符全部是'b',接着cnt[2]个字符全部是'c'...接着cnt[i]个字符全部是'a'+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)

具体看代码吧:

那么代码这么写:

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

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

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

前cnt[0]个字符全部是'a',接着cnt[1]个字符全部是'b',接着cnt[2]个字符全部是'c'...接着cnt[i]个字符全部是'a'+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)

具体看代码吧: