Reincarnation

正因为梦易碎，才格外美好。

P2787 语文1（chin1）- 理理思维

发表于 更新于 分类于
本文字数： 4.7k 阅读时长 ≈ 4 分钟

手感不好，真该理理思维了……

题目简介

题目名称：语文1（）- 理理思维

题目来源：

评测链接：https://www.luogu.com.cn/problem/P2787

形式化题意：给定一个长度为 的字符串，维护 次操作：

  1. 求 中有多少个 ；
  2. 将 全部替换成 ；
  3. 对 进行排序（由大到小）。

其中 表示一个字符，大小写不敏感。

数据范围：

把操作编号看错加上 tag 打错调了半个小时……

考虑到值域很小，所以可以对每一个字符都建一棵大小为 的序列线段树（注意不是权值线段树），然后每一次操作将 棵线段树都维护一遍即可。

对于操作 ，同理，枚举 ，然后找当前区间出现个数，然后从 开始往后进行操作 即可。

设 ，时间复杂度为 ，稍微卡常，吸氧过。

AC Code
 
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
// ----- Eternally question-----
// Problem: P2787 语文1（chin1）- 理理思维
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2787
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-01-12 07:34:30
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e4+10,MAXS=27;
int N,Q;
char Str[MAXN];
struct Segment
{
	#define ls (p<<1)
	#define rs (p<<1|1)
	struct ST
	{
		int l,r,val,tag;
	}Tr[MAXN<<2];
	inline void pushUp(int p)
	{ Tr[p].val=Tr[ls].val+Tr[rs].val; }
	inline void pushDown(int p)
	{
		if(Tr[p].tag==-1) return ;
		Tr[ls].tag=Tr[rs].tag=Tr[p].tag;
		Tr[ls].val=Tr[p].tag*(Tr[ls].r-Tr[ls].l+1),
		Tr[rs].val=Tr[p].tag*(Tr[rs].r-Tr[rs].l+1);
		Tr[p].tag=-1;
	}
	void build(int p,int l,int r)
	{
		Tr[p]=(ST){l,r,0,-1};
		if(l==r) return ;
		int mid=(l+r)>>1;
		build(ls,l,mid),build(rs,mid+1,r);
	}
	void modifyCover(int p,int l,int r,int v)
	{
		if(l>r) return ;
		if(l<=Tr[p].l&&Tr[p].r<=r)
		{
			Tr[p].val=(Tr[p].r-Tr[p].l+1)*v,Tr[p].tag=v;
			return ;
		}
		pushDown(p);
		int mid=(Tr[p].l+Tr[p].r)>>1;
		if(l<=mid) modifyCover(ls,l,r,v);
		if(mid<r) modifyCover(rs,l,r,v);
		pushUp(p);
	}
	int querySum(int p,int l,int r)
	{
		if(l>r) return 0;
		if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].val;
		pushDown(p);
		int mid=(Tr[p].l+Tr[p].r)>>1,res=0;
		if(l<=mid) res+=querySum(ls,l,r);
		if(mid<r) res+=querySum(rs,l,r);
		return res;
	}
}Tr[MAXS];
// std::vector<int>Nums;
inline char trans(char c)
{ return c>='a'?(c-'a'+'A'):(c); }
// int Val[MAXN];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);
	for(int i=0;i<26;++i) Tr[i].build(1,1,N);
	scanf("%s",Str+1);
	// for(int i=1;i<=N;++i) Nums.push_back(Str[i]);
	// std::sort(Nums.begin(),Nums.end());
	// Nums.erase(std::unique(Nums.begin(),Nums.end()),Nums.end());
	// for(int i=1;i<=N;++i) Val[i]=std::lower_bound(Nums.begin(),Nums.end(),Str[i])-Nums.begin();
	// for(int i=1;i<=N;++i) write(Val[i],' ');puts("");
	for(int i=1;i<=N;++i) Str[i]=trans(Str[i]);
	// for(int i=1;i<=N;++i) write(Str[i]);puts("");
	for(int i=1;i<=N;++i) Tr[Str[i]-'A'].modifyCover(1,i,i,1);
	for(int opt,ql,qr;Q--;)
	{
		read(opt,ql,qr);
		if(opt==3)
		{
			int pos=ql;
			for(int i=0;i<26;++i)
			{
				int cnt=Tr[i].querySum(1,ql,qr);
				if(!cnt) continue;
				if(pos>qr) break;
				Tr[i].modifyCover(1,ql,qr,0);
				Tr[i].modifyCover(1,pos,pos+cnt-1,1);
				pos+=cnt;
			}
		}
		else
		{
			char s[3];
			scanf("%s",s);
			s[0]=trans(s[0]);
			if(opt==2)
			{
				for(int i=0;i<26;++i) Tr[i].modifyCover(1,ql,qr,0);
				Tr[(int)s[0]-'A'].modifyCover(1,ql,qr,1);
			}
			if(opt==1) write(Tr[(int)s[0]-'A'].querySum(1,ql,qr),'\n');
		}
	}
	return 0;
}
/*

*/
相关文章