实现功能:输入一个长度为N的由26个大写字母组成的字符串,输入M条指令:"1 x y",将x到y的字串重组构成一个字典序最小的回文串,如果不能构成回文串输出False,否则True并完成变换;"2 x y"输出从x到y的子串;"3 x y t"将x到y的所有字全部变成chr(t+64)(即对应大写字母)
原理:用一个数组维护字母个数即可,然后再附带一个带tag的区间覆盖操作,实现回文串的重组
1 type
2 vec=array[0..26] of longint;
3 var
4 i,j,k,l,m,n,t:longint;
5 a:array[0..500000] of vec;
6 b:array[0..500000] of longint;
7 c:array[0..500000] of ansistring;
8 function empty:vec;inline;
9 var a1:vec;
10 begin
11 fillchar(a1,sizeof(a1),0);
12 exit(a1);
13 end;
14 function merge(a1,a2:vec):vec;inline;
15 var i:longint;
16 begin
17 for i:=1 to 26 do a1[i]:=a1[i]+a2[i];
18 exit(a1);
19 end;
20 function max(x,y:longint):longint;inline;
21 begin
22 if x>y then max:=x else max:=y;
23 end;
24 function min(x,y:longint):longint;inline;
25 begin
26 if x<y then min:=x else min:=y;
27 end;
28 function strr(x:longint;y:char):ansistring;inline;
29 var s1:ansistring;i:longint;
30 begin
31 s1:='';
32 for i:=1 to x do s1:=s1+y;
33 exit(s1);
34 end;
35 procedure ext(z,x,y:longint);inline;
36 begin
37 if b[z]=0 then exit;
38 if (x<>y) then
39 begin
40 b[z*2]:=b[z];
41 a[z*2]:=empty;
42 a[z*2][b[z*2]]:=(x+y) div 2-x+1;
43 c[z*2]:=strr((x+y) div 2-x+1,chr(b[z]+64));
44 b[z*2+1]:=b[z];
45 a[z*2+1]:=empty;
46 a[z*2+1][b[z*2+1]]:=y-(x+y) div 2;
47 c[z*2+1]:=strr(y-(x+y) div 2,chr(b[z]+64));
48 end;
49 a[z]:=empty;
50 a[z][b[z]]:=y-x+1;
51 c[z]:=strr(y-x+1,chr(b[z]+64));
52 b[z]:=0;
53 end;
54
55 procedure built(z,x,y:longint);
56 var c1:char;
57 begin
58 if x=y then
59 begin
60 read(c1);c1:=upcase(c1);c[z]:=c1;
61 a[z]:=empty;a[z][ord(c1)-64]:=1;
62 end
63 else
64 begin
65 built(z*2,x,(x+y) div 2);
66 built(z*2+1,(x+y) div 2+1,y);
67 c[z]:=c[z*2]+c[z*2+1];
68 a[z]:=merge(a[z*2],a[z*2+1]);
69 end;
70 b[z]:=0;
71 end;
72 function getsum(z,x,y,l,r:longint):vec;
73 var a1:vec;
74 begin
75 if l>r then exit(empty);
76 if b[z]>0 then
77 begin
78 a1:=empty;
79 a1[b[z]]:=r-l+1;
80 exit(a1);
81 end;
82 if (x=l) and (y=r) then exit(a[z]);
83 getsum:=merge(getsum(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2)),getsum(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r));
84 end;
85 procedure cover(z,x,y,l,r,t:longint);
86 begin
87 if l>r then exit;
88 if (x=l) and (y=r) then
89 begin
90 b[z]:=t;
91 a[z]:=empty;a[z][b[z]]:=r-l+1;
92 c[z]:=strr(r-l+1,chr(64+b[z]));
93 exit;
94 end;
95 ext(z,x,y);
96 cover(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2),t);
97 cover(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r,t);
98 c[z]:=c[z*2]+c[z*2+1];
99 a[z]:=merge(a[z*2],a[z*2+1]);
100 end;
101 function setup(x,y:longint):boolean;
102 var a1:vec;i,j,k,l:longint;
103 begin
104 a1:=getsum(1,1,n,x,y);
105 l:=0;
106 for i:=1 to 26 do
107 if odd(a1[i]) then
108 if l=0 then l:=i else exit(false);
109 j:=x;k:=y;
110 for i:=1 to 26 do
111 begin
112 cover(1,1,n,j,j+a1[i] div 2-1,i);
113 cover(1,1,n,k-a1[i] div 2+1,k,i);
114 j:=j+a1[i] div 2;k:=k-a1[i] div 2;
115 end;
116 if l>0 then cover(1,1,n,j,k,l);
117 exit(true);
118 end;
119 function getstr(z,x,y,l,r:longint):ansistring;inline;
120 begin
121 if l>r then exit('');
122 if b[z]>0 then exit(strr(r-l+1,chr(b[z]+64)));
123 if (x=l) and (y=r) then exit(c[z]);
124 exit(getstr(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2))+getstr(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r));
125 end;
126 begin
127 readln(n,m);
128 built(1,1,n);
129 readln;
130 for i:=1 to m do
131 begin
132 read(t);
133 case t of
134 1:begin
135 readln(j,k);
136 writeln(setup(j,k));
137 end;
138 2:begin
139 readln(j,k);
140 writeln(getstr(1,1,n,j,k));
141 end;
142 3:begin
143 readln(j,k,l);
144 cover(1,1,n,j,k,l);
145 end;
146 end;
147 end;
148 end.