CF558E

93 阅读 0 评论 62 点赞

我是靠谱客的博主缓慢小天鹅，最近开发中收集的这篇文章主要介绍CF558E，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

非常好的一道题，是线段树的常见玩法

将字符串转化为1~26个数

对区间开一棵线段树，用两个数组分别维护区间中1~26每个数的个数以及一个区间覆盖标记，表示这个区间是否被某一个值覆盖了

在每次排序时，首先查出这个区间中1~26每个数出现的次数，然后因为是排过序的，所以相等的数排完序之后一定是连续的一段区间，这样如果升序，我们就对整个区间从小到大进行覆盖，否则从大到小覆盖

最后遍历整棵线段树输出即可

一句话总结：每次排序只需做一次区间查询，26次区间覆盖，这样时间复杂度O（26nlogn）

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define ls tree[rt].lson
#define rs tree[rt].rson
#define rt1 rt<<1
#define rt2 (rt<<1)|1
using namespace std;
struct Tree
{
bool tag[30];
int s[30];
int lson;
int rson;
}tree[400005];
struct node
{
int v[30];
}zero;
int n,q;
int a[100005];
char s[100005];
void pushdown(int rt)
{
if(ls==rs)
{
return;
}
for(int i=1;i<=26;i++)
{
if(tree[rt].tag[i])
{
for(int j=1;j<=26;j++)
{
tree[rt1].tag[j]=0;
tree[rt1].s[j]=0;
tree[rt2].tag[j]=0;
tree[rt2].s[j]=0;
}
tree[rt1].tag[i]=1;
tree[rt2].tag[i]=1;
tree[rt1].s[i]=tree[rt1].rson-tree[rt1].lson+1;
tree[rt2].s[i]=tree[rt2].rson-tree[rt2].lson+1;
tree[rt].tag[i]=0;
break;
}
}
}
void buildtree(int rt,int l,int r)
{
tree[rt].lson=l;
tree[rt].rson=r;
if(l==r)
{
tree[rt].s[a[l]]=1;
return;
}
int mid=(l+r)>>1;
buildtree(rt1,l,mid);
buildtree(rt2,mid+1,r);
for(int i=1;i<=26;i++)
{
tree[rt].s[i]=tree[rt1].s[i]+tree[rt2].s[i];
}
}
node add(node x,node y)
{
node ret=zero;
for(int i=1;i<=26;i++)
{
ret.v[i]=x.v[i]+y.v[i];
}
return ret;
}
node query(int rt,int l,int r)
{
if(ls>r||rs<l)
{
return zero;
}else if(ls>=l&&rs<=r)
{
node ret=zero;
for(int i=1;i<=26;i++)
{
ret.v[i]=tree[rt].s[i];
}
return ret;
}
pushdown(rt);
int mid=(ls+rs)>>1;
return add(query(rt1,l,r),query(rt2,l,r));
}
void update(int rt,int l,int r,int val)
{
if(ls>r||rs<l)
{
return;
}
if(ls>=l&&rs<=r)
{
for(int i=1;i<=26;i++)
{
tree[rt].s[i]=0;
tree[rt].tag[i]=0;
}
tree[rt].tag[val]=1;
tree[rt].s[val]=rs-ls+1;
return;
}
pushdown(rt);
int mid=(ls+rs)>>1;
if(l<=mid)
{
update(rt1,l,r,val);
}
if(r>mid)
{
update(rt2,l,r,val);
}
for(int i=1;i<=26;i++)
{
tree[rt].s[i]=tree[rt1].s[i]+tree[rt2].s[i];
}
}
void pushit(int rt)
{
pushdown(rt);
if(ls==rs)
{
return;
}
pushit(rt1);
pushit(rt2);
}
void print(int rt)
{
if(ls==rs)
{
for(int i=1;i<=26;i++)
{
if(tree[rt].s[i])
{
printf("%c",i-1+'a');
return;
}
}
}
print(rt1);
print(rt2);
}
inline int read()
{
int f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
//	freopen("third.in","r",stdin);
//	freopen("third.out","w",stdout);
n=read(),q=read();
scanf("%s",s+1);
for(int i=1;i<=n;i++)
{
a[i]=s[i]-'a'+1;
}
buildtree(1,1,n);
for(int i=1;i<=q;i++)
{
int l=read(),r=read(),typ=read();
node temp=query(1,l,r);
if(typ==1)
{
for(int j=1;j<=26;j++)
{
update(1,l,l+temp.v[j]-1,j);
l+=temp.v[j];
}
}else
{
for(int j=26;j>=1;j--)
{
update(1,l,l+temp.v[j]-1,j);
l+=temp.v[j];
}
}
}
pushit(1);
print(1);
printf("n");
return 0;
}