题号 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个小写字母的字符串
也就是说元素的值域很小,适用于数据范围较小的排序我们可以想到计数排序
计数排序:(思想:统计小于等于当前数的个数有多少个)
- 先用一个桶将所有元素出现的次数统计出来,记录元素出现的次数
- 然后对做一遍前缀和
- 则如果表示出现过,且从小到大排序后的出现位置是
线段树维护:
我们维护一个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; }