# 算法模板——线段树8 （字符串回文变换）

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
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
128      built(1,1,n);
130      for i:=1 to m do
131          begin
133               case t of
134                    1:begin
136                           writeln(setup(j,k));
137                    end;
138                    2:begin
140                           writeln(getstr(1,1,n,j,k));
141                    end;
142                    3:begin
144                           cover(1,1,n,j,k,l);
145                    end;
146               end;
147          end;
148 end.

0 条评论

• ### 1854: [Scoi2010]游戏

1854: [Scoi2010]游戏 Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 2538  Solved:...

• ### 算法模板——线段树7（骰子翻转问题）

实现功能：首先输入一个长度为N的序列，由1-4组成（1表示向前滚一下，2表示向后滚一下，3表示向左滚一下，4表示向右滚一下，骰子原始状态：上1前2左4右5后3下...

• ### 1257: [CQOI2007]余数之和sum

1257: [CQOI2007]余数之和sum Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 2001  So...

• ### 2761: [JLOI2011]不重复数字（平衡树）

2761: [JLOI2011]不重复数字 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 2133  So...

• ### 1901: Zju2112 Dynamic Rankings

1901: Zju2112 Dynamic Rankings Time Limit: 10 Sec  Memory Limit: 128 MB Submit: ...

• ### 1050: [HAOI2006]旅行comf

1050: [HAOI2006]旅行comf Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 1495  So...

• ### 做人需要低调，编码不能「自私」

极端的人是可怕的，也许是你不经意间的傲慢行为，也许是你漫不经心怼人的话语，说不定就能呼唤起他们内心深处的小恶魔，毫无道理，也毫无预兆，你就有可能深受其害。