专栏首页HansBug's Lab算法模板——线段树8 (字符串回文变换)

算法模板——线段树8 (字符串回文变换)

实现功能:输入一个长度为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.     

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1854: [Scoi2010]游戏

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

    HansBug
  • 算法模板——线段树7(骰子翻转问题)

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

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

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

    HansBug
  • 2761: [JLOI2011]不重复数字(平衡树)

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

    HansBug
  • 1901: Zju2112 Dynamic Rankings

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

    HansBug
  • 1050: [HAOI2006]旅行comf

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

    HansBug
  • 做人需要低调,编码不能「自私」

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

    Bug生活2048
  • 【卷积神经网络-进化史】从LeNet到AlexNet一切的开始( LeNet)王者回归(AlexNet)Refenence

    zhwhong
  • SAP CRM Fiori My Opportunity应用的性能分析

    [https://fiorilaunchpad-faasperf.dispatcher.neo.ondemand.com/sap/opu/odata/sap/C...

    Jerry Wang
  • 原 荐 JS数组追加数组采用push.app

    HT_hightopo

扫码关注云+社区

领取腾讯云代金券