CodeForces - 558E.A Simple Task(线段树-区间重排)

104 阅读 0 评论 69 点赞

我是靠谱客的博主英俊小松鼠，这篇文章主要介绍CodeForces - 558E.A Simple Task(线段树-区间重排)，现在分享给大家，希望可以做个参考。

题目

给你一个长度为n(n<=1e5)的字符串，

和q(q<=5e4)次修改操作，

每次修改输入i,j,k三个数，

k==1，表示对[i,j]区间按字典序不降序排序

k==0，表示对[i,j]区间按字典序不增序排序

要求输出修改之后的字符串

思路来源

归神の例会

题解

开26棵线段树，重排时，

只需先类似计数排序统计出[i,j]段每个字母出现的个数，

再根据k的值选择增序或降序，

对每棵线段树内对应的区间位置先清零后在对应位置赋1即可

查询时，每个位置单点查询有没有字母，查到就break

心得

其实还是区间赋值啦，板子改一改就能AC了

只是要注意几个细节，比如输入字符串的下标，num[j]==0时直接跳过等等

只是自己写的最后询问答案时候，变成了26棵树一一logn询问，总感觉有点不妥……

所幸复杂度没超，总复杂度O(26*(n+q)*logn)

代码

复制代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
//基数排序思想 统计出来每个区间对应'a'到'z'各多少个字母
//'a'-'z'每个字母开一棵线段树用于区间赋值 
char s[maxn];
int num[26];
int pos;//下一字母的起始位置 
int dat[26][maxn*5],cov[26][maxn*5];
int n,q;
int l,r,op;
void pushup(int a[],int b[],int p)
{
	a[p]=a[p<<1]+a[p<<1|1];
	if((~b[p<<1])&&(~b[p<<1|1]))b[p]=-1;
}
void build(int p,int l,int r)
{
	for(int i=0;i<26;++i)
	cov[i][p]=-1;//-1表示没有操作,与区间赋0区别 
	if(l==r)
	{
		for(int i=0;i<26;++i)
		{
			if(i==s[l]-'a')dat[i][p]=1;
			else dat[i][p]=0;
		}
		return;
	}
	int mid=(l+r)/2;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	for(int i=0;i<26;++i)
	pushup(dat[i],cov[i],p);
}
void pushdown(int a[],int b[],int p,int l,int r)
{
	if(~b[p])
	{
		int mid=(l+r)/2;
		a[p<<1]=b[p]*(mid-l+1);
		a[p<<1|1]=b[p]*(r-mid);
		b[p<<1]=b[p];
		b[p<<1|1]=b[p];
		b[p]=-1;
	}
}
void update(int a[],int b[],int p,int l,int r,int ql,int qr,int v)//区间赋1或赋0 
{
	if(ql<=l&&r<=qr)
	{
		a[p]=v*(r-l+1);
		b[p]=v;
		return;
	}
	pushdown(a,b,p,l,r); 
	int mid=(l+r)/2;
	if(ql<=mid)update(a,b,p<<1,l,mid,ql,qr,v);
	if(qr>mid)update(a,b,p<<1|1,mid+1,r,ql,qr,v);
	pushup(a,b,p);
}
int ask(int a[],int b[],int p,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr)return a[p];
	pushdown(a,b,p,l,r);
	int mid=(l+r)/2,ans=0;
	if(ql<=mid)ans+=ask(a,b,p<<1,l,mid,ql,qr);
	if(qr>mid)ans+=ask(a,b,p<<1|1,mid+1,r,ql,qr);
	return ans; 
}
int main()
{
	scanf("%d%d",&n,&q);
	scanf("%s",s+1);//细节1：[1,n]  
	build(1,1,n);
	for(int i=1;i<=q;++i)
	{
		scanf("%d%d%d",&l,&r,&op);
		pos=l;
		//细节2：清零会被赋值覆盖 故不用清零 
		for(int j=0;j<26;++j)
		{
		 num[j]=ask(dat[j],cov[j],1,1,n,l,r); 
		 update(dat[j],cov[j],1,1,n,l,r,0);
	    }
	    if(op==1)
	    {
	    	for(int j=0;j<26;++j)
	    	{
	    		if(!num[j])continue;//细节3 
	    		update(dat[j],cov[j],1,1,n,pos,pos+num[j]-1,1);//pos+num[j]-1>=pos 要求num[j]>=1 
	    		pos=pos+num[j];
	    	}
	    }
	    else 
	    {
	    	for(int j=25;j>=0;--j)
	    	{
	    		if(!num[j])continue;
	    		update(dat[j],cov[j],1,1,n,pos,pos+num[j]-1,1);
	    		pos=pos+num[j];
	    	}
	    }
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=0;j<26;++j)
		{
			if(ask(dat[j],cov[j],1,1,n,i,i)>0)
			{
				putchar(j+'a');
				break;
			}
		}
	}
	puts("");
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
//基数排序思想 统计出来每个区间对应'a'到'z'各多少个字母
//'a'-'z'每个字母开一棵线段树用于区间赋值 
char s[maxn];
int num[26];
int pos;//下一字母的起始位置 
int dat[26][maxn*5],cov[26][maxn*5];
int n,q;
int l,r,op;
void pushup(int a[],int b[],int p)
{
	a[p]=a[p<<1]+a[p<<1|1];
	if((~b[p<<1])&&(~b[p<<1|1]))b[p]=-1;
}
void build(int p,int l,int r)
{
	for(int i=0;i<26;++i)
	cov[i][p]=-1;//-1表示没有操作,与区间赋0区别 
	if(l==r)
	{
		for(int i=0;i<26;++i)
		{
			if(i==s[l]-'a')dat[i][p]=1;
			else dat[i][p]=0;
		}
		return;
	}
	int mid=(l+r)/2;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	for(int i=0;i<26;++i)
	pushup(dat[i],cov[i],p);
}
void pushdown(int a[],int b[],int p,int l,int r)
{
	if(~b[p])
	{
		int mid=(l+r)/2;
		a[p<<1]=b[p]*(mid-l+1);
		a[p<<1|1]=b[p]*(r-mid);
		b[p<<1]=b[p];
		b[p<<1|1]=b[p];
		b[p]=-1;
	}
}
void update(int a[],int b[],int p,int l,int r,int ql,int qr,int v)//区间赋1或赋0 
{
	if(ql<=l&&r<=qr)
	{
		a[p]=v*(r-l+1);
		b[p]=v;
		return;
	}
	pushdown(a,b,p,l,r); 
	int mid=(l+r)/2;
	if(ql<=mid)update(a,b,p<<1,l,mid,ql,qr,v);
	if(qr>mid)update(a,b,p<<1|1,mid+1,r,ql,qr,v);
	pushup(a,b,p);
}
int ask(int a[],int b[],int p,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr)return a[p];
	pushdown(a,b,p,l,r);
	int mid=(l+r)/2,ans=0;
	if(ql<=mid)ans+=ask(a,b,p<<1,l,mid,ql,qr);
	if(qr>mid)ans+=ask(a,b,p<<1|1,mid+1,r,ql,qr);
	return ans; 
}
int main()
{
	scanf("%d%d",&n,&q);
	scanf("%s",s+1);//细节1：[1,n]  
	build(1,1,n);
	for(int i=1;i<=q;++i)
	{
		scanf("%d%d%d",&l,&r,&op);
		pos=l;
		//细节2：清零会被赋值覆盖 故不用清零 
		for(int j=0;j<26;++j)
		{
		 num[j]=ask(dat[j],cov[j],1,1,n,l,r); 
		 update(dat[j],cov[j],1,1,n,l,r,0);
	    }
	    if(op==1)
	    {
	    	for(int j=0;j<26;++j)
	    	{
	    		if(!num[j])continue;//细节3 
	    		update(dat[j],cov[j],1,1,n,pos,pos+num[j]-1,1);//pos+num[j]-1>=pos 要求num[j]>=1 
	    		pos=pos+num[j];
	    	}
	    }
	    else 
	    {
	    	for(int j=25;j>=0;--j)
	    	{
	    		if(!num[j])continue;
	    		update(dat[j],cov[j],1,1,n,pos,pos+num[j]-1,1);
	    		pos=pos+num[j];
	    	}
	    }
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=0;j<26;++j)
		{
			if(ask(dat[j],cov[j],1,1,n,i,i)>0)
			{
				putchar(j+'a');
				break;
			}
		}
	}
	puts("");
	return 0;
}