jiry_2's Blog

第一次发现线段树可以写得那么高端洋气上档次。旋转和翻转忽略掉，对于每个询问把位置变为原来的位置即可。然后在线段树中记录区间的左界右界，合并的时候如果相等则减一（要注意在C中可能整个串都为同一个颜色，这就不能减）。然后便是裸的区间修改了，瞎搞搞，花了我两天多时间才A掉，细节太复杂，代码写得又臭又长。。。

program p1493;
	type
		result=record
			left,right,num:longint;
		end;
	var
		x:array[1..500000] of longint;
		num,left,right,bj:array[1..2000000] of longint;
		xz2,fz,xz,n,q,i,j,c,k1,k2,k3,k:longint;
		p,p1,p2:result;
		ch:char;
	procedure swap(var k1,k2:longint);
		var	
			i:longint;
		begin
			i:=k1; k1:=k2; k2:=i;
		end;
	procedure buildtree(len,l,r:longint);
		var
			i,j:longint;
		begin
			left[len]:=x[l]; right[len]:=x[r];
			if l<>r then begin
				buildtree(len*2,l,(l+r) shr 1);
				buildtree(len*2+1,(l+r) shr 1+1,r);
				num[len]:=num[len*2]+num[len*2+1];
				if left[len*2+1]=right[len*2] then 
					dec(num[len]);
			end else
				num[len]:=1;
		end;
	function changenum(k:longint):longint;
		var	
			i:longint;
		begin
			i:=(k+n-xz) mod n+1;
			if fz=1 then i:=(n+1-i) mod n+1;
			exit(i);
		end;
	function find(k1,k2,k3,k4,k5:longint):result;
		var
			k,i,j:result;
		begin
			if (k2>k5) or (k3<k4) then begin
				k.left:=0; k.right:=0; k.num:=0; exit(k);
			end;
			if bj[k1]<>0 then begin
				k.left:=bj[k1]; k.right:=bj[k1]; k.num:=1; exit(k);
			end;
			if (k2>=k4) and (k3<=k5) then begin
				k.left:=left[k1]; k.right:=right[k1]; k.num:=num[k1]; exit(k);
			end;
			i:=find(k1*2,k2,(k2+k3) shr 1,k4,k5);
			j:=find(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5);
			if i.num=0 then exit(j);
			if j.num=0 then exit(i);
			k.left:=i.left; k.right:=j.right; k.num:=i.num+j.num;
			if (i.right=j.left) and (i.right<>0) then dec(k.num);
			exit(k);
		end;
	procedure maintain(k1,k2,k3:longint);
		begin
			if bj[k1]<>0 then begin
				left[k1]:=bj[k1]; right[k1]:=bj[k1]; num[k1]:=1;
				exit;
			end;
			if k2=k3 then begin
				left[k1]:=x[k2]; right[k1]:=x[k2]; num[k1]:=1;
				exit;
			end;
			left[k1]:=left[k1*2]; right[k1]:=right[2*k1+1];
			num[k1]:=num[k1*2]+num[k1*2+1];
			if left[k1*2+1]=right[k1*2] then 
				dec(num[k1]);
		end;
	procedure changetotal(k1,k2,k3,k4,k5,k6:longint);
		begin
			if (k2>k5) or (k3<k4) then begin maintain(k1,k2,k3); exit; end;
			if (k2>=k4) and (k3<=k5) then
				bj[k1]:=k6
			else begin
				if bj[k1]>0 then begin 
					bj[k1*2]:=bj[k1]; bj[k1*2+1]:=bj[k1]; bj[k1]:=0;
				end;
				changetotal(k1*2,k2,(k2+k3) shr 1,k4,k5,k6);
				changetotal(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6);
			end;
			maintain(k1,k2,k3);
		end;
	function getchar:char;
		var	
			ch:char;
		begin
			read(ch);
			while (ch<'A') or (ch>'Z') do read(ch);
			exit(ch);
		end;
	begin
		readln(n,c);
		fillchar(bj,sizeof(bj),0);
		for i:=1 to n do
			read(x[i]);
		readln;
		buildtree(1,1,n);
		fz:=0; xz:=1;
		readln(q);
		for i:=1 to q do begin
			ch:=getchar;
			if ch='C' then begin
				read(ch);
				if ch='S' then begin
					readln(k1,k2);
					k1:=changenum(k1);
					k2:=changenum(k2);
					if fz=1 then swap(k1,k2);
					if k1>k2 then begin
						p1:=find(1,1,n,k1,n);
						p2:=find(1,1,n,1,k2);
						p.num:=p1.num+p2.num;
						p.left:=p1.left; p.right:=p2.right;
						if p1.right=p2.left then dec(p.num);
					end else begin
						p:=find(1,1,n,k1,k2);
					end;
					writeln(p.num);
				end else begin
					p:=find(1,1,n,1,n);
					if p.left=p.right then dec(p.num);
					if p.num=0 then p.num:=1;
					writeln(p.num);
					{for j:=1 to n do
						write(find(1,1,n,j,j).left,' ');
					readln;}
				end;
			end else if ch='P' then begin
				readln(k1,k2,k3);
				k1:=changenum(k1); k2:=changenum(k2);
				if fz=1 then swap(k1,k2);
				{WRITELN(K1,' ',K2);}
				if k1>k2 then begin
					changetotal(1,1,n,1,k2,k3);
					changetotal(1,1,n,k1,n,k3);
				end else
					changetotal(1,1,n,k1,k2,k3);
			end else if ch='S' then begin
				readln(k1,k2);
				k1:=changenum(k1); k2:=changenum(k2);
				if fz=1 then swap(k1,k2);
				{WRITELN(K1,' ',K2);}
				j:=find(1,1,n,k1,k1).left;
				k:=find(1,1,n,k2,k2).left;
				changetotal(1,1,n,k1,k1,k);
				changetotal(1,1,n,k2,k2,j);
			end else if ch='F' then begin
				fz:=(fz+1) mod 2;
				xz:=(n+1-xz) mod n+1;
			end else begin
				readln(k1);
				xz:=(xz+k1-1) mod n+1;
			end;
		end;
	end.