实现功能：输入一个长度为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 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           begin104                a1:=getsum(1,1,n,x,y);105                l:=0;106                for i:=1 to 26 do107                    if odd(a1[i]) then108                       if l=0 then l:=i else exit(false);109                j:=x;k:=y;110                for i:=1 to 26 do111                    begin112                         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          begin121               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 begin127      readln(n,m);128      built(1,1,n);129      readln;130      for i:=1 to m do131          begin132               read(t);133               case t of134                    1:begin135                           readln(j,k);136                           writeln(setup(j,k));137                    end;138                    2:begin139                           readln(j,k);140                           writeln(getstr(1,1,n,j,k));141                    end;142                    3:begin143                           readln(j,k,l);144                           cover(1,1,n,j,k,l);145                    end;146               end;147          end;148 end.