codeforces 558 E. A Simple Task (线段树优化计数排序)

题目链接

题意:给出一个字符串,仅由小写字母组成。现在给出q个操作,每个操作l,r,k三个参数,k=1表示把区间[l,r]变为升序排列,k=0表示把区间[l,r]变为降序排列。

思路:首先,最重要的一点是,由于只有26个字母,联想到计数排序。

对于字符集数目比较小情况,一定要想到计数排序。

对于字符集数目比较小情况,一定要想到计数排序。

对于字符集数目比较小情况,一定要想到计数排序。

那么我们回顾计数排序,不妨考虑升序排列的情况,是怎么做的呢?

做法是统计该区间中每种字符的个数,然后按照字符的大小,从小到大在区间上从左到右得放置每种字符。

大概是这样子:

for(int j=x;j<=y;j++)
  cnt[s[j] - 'a']++;
ind = 0;
for(int j=x;j<=y;j++)
{
  while(cnt[ind] == 0)
    ind++;
  s[j] = ind + 'a';
  cnt[ind]--;
}

然而这个复杂度每次是o(n)的。。。

我们需要用线段树来优化计数排序的过程。。。

思考计数排序其实分为两个过程:

一是统计某区间中每个字符的个数。

二是将字符按照字符的大小顺序重新放回区间。

我们可以建26棵线段树,一种字母对应一棵。

对于过程一,我们可以直接query.

对于过程2,由于相同的字母总是相邻在一起的,因此可以用线段树成段更新来优化,也就是lazy标记。

tree[id][rt]表示第id棵线段树对应的区间中字母id+'a'-1的个数。

lazy[id][rt]三种值,-1表示没有标记,0表示重置标记,1表示被某种字母覆盖的标记。(重置的意思是,该区间被排序了,但是还不确定该区间上字母是哪些)

输出的时候,对于某个位置,只要query到26个字母中值不为0的那个输出就好了。

总的复杂度:O(26qlgn)

代码注释中还有部分细节和理解

/* ***********************************************
Author :111qqz
Created Time :2016年10月04日 星期二 23时59分11秒
File Name :code/cf/problem/558E.cpp
 ************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <deque>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <bitset>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
int tree[27][N<<2];//26棵线段树,表示26个字母在对应区间中的个数。
int lazy[27][N<<2];//lazy存储的是某段区间是否被某个字母覆盖. -1表示初始没有标记,0表示该区间被重置,1表示该区间被某种颜色覆盖。
int n,q;
char st[N];
int cnt[27]; //计数排序.
void PushUp(int rt,int id)
{
    tree[id][rt] = tree[id][rt<<1] + tree[id][rt<<1|1];
}
void PushDown(int l,int r,int rt,int id)
{
    if (lazy[id][rt]==-1) return ;
    if (l==r) return;
    lazy[id][rt<<1] = lazy[id][rt<<1|1] = lazy[id][rt]; //可以把一段区间被某种字母覆盖看做被染色。。。不过我们不需要知道被哪种字母染色,只需要知道是否被染色。
    if (lazy[id][rt]) //如果一段区间被某种字母覆盖,那么该区间某种字母的数目就是区间长度,这也是PushDown需要传递区间端点l,r进来的原因。
    {
	int m = (l+r)>>1;
	tree[id][rt<<1] = m-l+1;
	tree[id][rt<<1|1] = r-m; //区间长度
    }
    else tree[id][rt<<1] = tree[id][rt<<1|1] = 0 ; //如果被重置了,清空线段树数组。
    lazy[id][rt] = -1;
    //关于lazy标记的思考:lazy标记是为了延迟更新。。。因此PushDown操作的内容其实和update时候的东西是非常相似的。。。
}
void build ( int l,int r,int rt)
{
    if (l==r)
    {
	int id = st[l]-'a'+1;
	tree[id][rt] = 1;
	lazy[id][rt] = 1;
	return;
    }
    int m = (l+r)>>1;
    build(lson);
    build(rson);
    for ( int i = 1 ; i <= 26 ; i++) //26棵线段树,每一层向上更新的时候每一棵都要记得更新。
	PushUp(rt,i);
}
void update(int L,int R,int sc,int l,int r,int rt,int id)
{
    if (L<=l&&r<=R)
    {
	lazy[id][rt] = sc; //sc为0表示重置区间,sc为1表示该区间被id+'a'-1的字母覆盖。
	if (sc) tree[id][rt] = r-l+1;
	else tree[id][rt] = 0;
	return;
    }
    PushDown(l,r,rt,id);
    int m = (l+r)>>1;
    if (L<=m) update(L,R,sc,lson,id);
    if (R>=m+1) update(L,R,sc,rson,id);
    PushUp(rt,id);
}
int query(int L,int R,int l,int r,int rt,int id)
{
    if (L<=l&&r<=R) return tree[id][rt];
    PushDown(l,r,rt,id);
    int m = (l+r)>>1;
    int ret = 0 ;
    if (L<=m) ret = ret + query(L,R,lson,id);
    if (R>=m+1) ret = ret + query(L,R,rson,id);
    PushUp(rt,id);
    return ret;
}
int main()
{
#ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
#endif
    ms(tree,0);
    ms(lazy,-1);
    cin>>n>>q;
    scanf("%s",st+1);
    build(1,n,1);
    while (q--)
    {
	int l,r,k;
	scanf("%d%d%d",&l,&r,&k);
	for ( int i = 1 ; i <= 26 ; i++)
	{
	    cnt[i] = query(l,r,1,n,1,i);
	  update(l,r,0,1,n,1,i); //初始要把[l,r]区间的每个字母的线段树区间重置,因为排序会打乱,在下面按照k的不同以不同方式(正序,逆序)更新。
	}
	if (k==1)
	{
	    int pos = l;
	    for ( int i = 1 ; i <= 26 ; i++)
	    {
		if (cnt[i]==0) continue;
		update(pos,pos+cnt[i]-1,1,1,n,1,i);
		pos = pos + cnt[i];
	    }
	}
	else
	{
	    int pos = l;
	    for ( int i = 26 ; i >= 1 ; i--)
	    {
		if (cnt[i]==0) continue;
		update(pos,pos+cnt[i]-1,1,1,n,1,i);
		pos = pos + cnt[i];
	    }
	}
    }
    for ( int i = 1 ; i <= n ; i++)
    {
	for ( int j = 1 ; j <= 26 ; j++)
	{
	    if (query(i,i,1,n,1,j))  //在第i个位置26个字母只可能有一种值为1,其余都为0,输出的时候query就好了。
	    {
		printf("%c",j+'a'-1);
		break;
	    }
	}
    }
#ifndef ONLINE_JUDGE  
    fclose(stdin);
#endif
    return 0;
}