5829. 【NOIP提高A组模拟2018.8.18】 string
程序员文章站
2024-03-20 11:03:10
...
Description
给定一个由小写字母组成的字符串 s。有 m 次操作,每次操作给 定 3 个参数 l,r,x。如果 x=1,将 s[l]~s[r]升序排序;如果 x=0,将 s[l]~s[r] 降序排序。你需要求出最终序列。
Input
第一行两个整数 n,m。第二行一个字符串 s。接下来 m 行每行三 个整数 l,r,x。
Output
一行一个字符串表示答案。
Sample Input
5 2
cabcd
1 3 1
3 5 0
Sample Output
abdcc
Data Constraint
对于 40%的数据,n,m<=1000。
对于 100%的数据,n,m<=100000
Solution
用线段树维护区间内 a~z 的个数,每次询问拆成 26 个 区间修改操 作。 时间复杂度 O(mlogn*26)。
Code1
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ls x<<1
#define rs x<<1|1
#pragma GCC optimize(3)
using namespace std;
int s[100010];
int n,m,l,r,x,lzy[100010<<2];
int tree[100010<<2][26],f[26];
char ch;
__attribute__((optimize("-O3")))
void update(int x){
for(int i=0;i<26;i++) tree[x][i]=tree[ls][i]+tree[rs][i];
}
__attribute__((optimize("-O3")))
void add(int x,int l,int r){
if(!lzy[x]) return;
if(l!=r){
int mid=(l+r)>>1;
int s=mid-l+1;
if(lzy[x]==2){
for(int i=0;i<26;i++){
int k=min(tree[x][i],s);
tree[ls][i]=k;tree[x][i]-=k;s-=k;
}
}
else{
for(int i=25;i>=0;i--){
int k=min(tree[x][i],s);
tree[ls][i]=k;tree[x][i]-=k;s-=k;
}
}
for(int i=0;i<26;i++){
tree[rs][i]=tree[x][i];tree[x][i]+=tree[ls][i];
}
lzy[rs]=lzy[ls]=lzy[x];lzy[x]=0;
}
}
__attribute__((optimize("-O3")))
void build(int x,int l,int r){
if(l==r){tree[x][s[l]]++;return;}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
update(x);
}
__attribute__((optimize("-O3")))
void getsum(int x,int l,int r,int s,int t){
if(l==s&&r==t){
for(int i=0;i<26;i++){
tree[0][i]+=tree[x][i];
tree[x][i]=0;
}
return;
}
add(x,l,r);
int mid=(l+r)>>1;
if(t<=mid) getsum(ls,l,mid,s,t);
else if(s>mid) getsum(rs,mid+1,r,s,t);
else{
getsum(ls,l,mid,s,mid);
getsum(rs,mid+1,r,mid+1,t);
}
}
__attribute__((optimize("-O3")))
void find(int x,int l,int r,int s,int t,int p){
if(l==s&&r==t){
int s=r-l+1;
if(p==2){
for(int i=0;i<26;i++){
int k=min(tree[0][i],s);
tree[x][i]=k;tree[0][i]-=k;s-=k;
}
}
else{
for(int i=25;i>=0;i--){
int k=min(tree[0][i],s);
tree[x][i]=k;tree[0][i]-=k;s-=k;
}
}
lzy[x]=p;
return;
}
add(x,l,r);
int mid=(l+r)>>1;
if(t<=mid) find(ls,l,mid,s,t,p);
else if(s>mid) find(rs,mid+1,r,s,t,p);
else{
find(ls,l,mid,s,mid,p);
find(rs,mid+1,r,mid+1,t,p);
}
update(x);
}
__attribute__((optimize("-O3")))
void findans(int x,int l,int r){
if(l==r){
for(int i=0;i<26;i++){
if(tree[x][i]){
printf("%c",i+'a');
break;
}
}
return;
}
if(lzy[x]) add(x,l,r);
int mid=(l+r)>>1;
findans(ls,l,mid);
findans(rs,mid+1,r);
}
__attribute__((optimize("-O3")))
int main(){
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
scanf("%d%d\n",&n,&m);
for(int i=1;i<=n;i++){
ch=getchar();s[i]=ch-'a';
}
build(1,1,n);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&l,&r,&x);
getsum(1,1,n,l,r);
find(1,1,n,l,r,x+1);
}
findans(1,1,n);
return 0;
}
作者:zsjzliziyang
QQ:1634151125
转载及修改请注明
本文地址:https://blog.csdn.net/zsjzliziyang/article/details/81812887
上一篇: 铺地毯【NOIP2011提高组第1题】
下一篇: 变态青蛙跳台阶
推荐阅读
-
【NOIP提高A组模拟2018.8.18】 number
-
5829. 【NOIP提高A组模拟2018.8.18】 string
-
【数位DP】JZOJ 5831. 【NOIP提高A组模拟2018.8.18】 number
-
2017.08.19【NOIP提高组】模拟赛B组总结
-
2017.08.06【NOIP提高组】模拟赛B组总结
-
2017.11.25【NOIP提高组】模拟赛B组总结
-
2017.08.05【NOIP提高组】模拟赛B组总结
-
JZOJ 2017.12.09【NOIP提高组】模拟赛C组
-
2020.09.05【NOIP提高组&普及组】模拟赛C组1总结
-
2017.08.18【NOIP提高组】模拟赛B组总结