1
9
2014
0

树套树专题

树套树是我写到至今最DT的数据库结构了吧。。。

【BZOJ3196】【Tyvj 1730】二逼平衡树

线段树套TREAP,nlog3n

program p3196;
    type
        tree=record
            l,r,w,f,size:longint;
        end;
    var
        t:array[0..4000000] of tree;
        x,root:array[0..500000] of longint;
        i,j,n,m,len,ans,l,r,mid,k1,k2,k3,k4,k5,k6:longint;
        ch:char;
    function min(k1,k2:longint):longint;
        begin
            if k1<k2 then exit(k1) else exit(k2);
        end;
    function max(k1,k2:longint):longint;
        begin
            if k1<k2 then exit(k2) else exit(k1);
        end;
    procedure zig(pf,f,k:longint);
        begin
            if t[pf].l=f then t[pf].l:=k else if t[pf].r=f then t[pf].r:=k;
            t[f].l:=t[k].r; t[k].r:=f; t[f].size:=t[t[f].l].size+t[t[f].r].size+1;
            t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
        end;
    procedure zag(pf,f,k:longint);
        begin
            if t[pf].l=f then t[pf].l:=k else if t[pf].r=f then t[pf].r:=k;
            t[f].r:=t[k].l; t[k].l:=f; t[f].size:=t[t[f].l].size+t[t[f].r].size+1;
            t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
        end;
    procedure insert(f,k1,k2:longint);
        begin
            inc(t[k1].size);
            if t[k1].w>t[k2].w then begin
                if t[k1].l=0 then t[k1].l:=k2 else insert(k1,t[k1].l,k2);
                if t[k1].f<t[k2].f then zig(f,k1,k2);
            end else begin
                if t[k1].r=0 then t[k1].r:=k2 else insert(k1,t[k1].r,k2);
                if t[k1].f<t[k2].f then zag(f,k1,k2);
            end;
        end;
    procedure buildtree(k1,k2,k3:longint);
        var
            now,i,j:longint;
        begin
            root[k1]:=len+1; now:=len-k2+1; len:=len+k3-k2+1;
            for i:=k2 to k3 do begin
                t[i+now].w:=x[i]; t[i+now].size:=1; t[i+now].f:=random(1000000);
                if i<>k2 then begin
                    insert(0,root[k1],i+now); 
                    if (t[i+now].l=root[k1]) or (t[i+now].r=root[k1]) then root[k1]:=i+now; 
                end;
            end;
            if k2<>k3 then begin
                buildtree(k1*2,k2,(k2+k3) shr 1);
                buildtree(k1*2+1,(k2+k3) shr 1+1,k3);
            end;
        end;
    function findallnum(k1,k2:longint):longint;
        begin
            if k1=0 then exit(0);
            if k2<t[k1].w then exit(findallnum(t[k1].l,k2));
            exit(findallnum(t[k1].r,k2)+1+t[t[k1].l].size);
        end;
    function pd(k1,k2,k3,k4,k5,k6:longint):longint;
        var
            k:longint;
        begin
            if (k2>k5) or (k3<k4) then exit(0);
            if (k2>=k4) and (k3<=k5) then exit(findallnum(root[k1],k6));
            exit(pd(k1*2,k2,(k2+k3) shr 1,k4,k5,k6)+pd(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6));
        end;
    function findwhere(k,k1,k2,f:longint):longint;
        var
            k3,k4:longint;
        begin
            if t[k1].w=k2 then begin
                while true do begin
                    if t[k1].l=0 then begin
                        if f=0 then root[k]:=t[k1].r else begin
                            if k1=t[f].l then t[f].l:=t[k1].r else t[f].r:=t[k1].r;
                        end;
                        t[k1].r:=0;
                        exit(k1);
                    end else if t[k1].r=0 then begin
                        if f=0 then root[k]:=t[k1].l else begin
                            if k1=t[f].l then t[f].l:=t[k1].l else t[f].r:=t[k1].l;
                        end;
                        t[k1].l:=0;
                        exit(k1);
                    end else begin
                        k3:=f;
                        if t[t[k1].l].f>t[t[k1].r].f then begin f:=t[k1].l; zig(k3,k1,t[k1].l); end else begin f:=t[k1].r; zag(k3,k1,t[k1].r); end;
                        if k3=0 then root[k]:=f;
                        dec(t[f].size);
                    end;
                end;
            end;
            dec(t[k1].size);
            if t[k1].w>k2 then exit(findwhere(k,t[k1].l,k2,k1)) else exit(findwhere(k,t[k1].r,k2,k1));
        end;
    procedure change(k1,k2,k3,k4,k6,k5:longint);
        var
            k:longint;
        begin
            if (k2>k4) or (k3<k4) then exit;
            if (k2=k3) then begin
                t[root[k1]].w:=k5; exit;
            end;
            k:=findwhere(k1,root[k1],k6,0); t[k].size:=1;
            t[k].w:=k5; insert(0,root[k1],k);  
            if (t[k].l=root[k1]) or (t[k].r=root[k1]) then root[k1]:=k;
            change(k1*2,k2,(k2+k3) shr 1,k4,k6,k5);
            change(k1*2+1,(k2+k3) shr 1+1,k3,k4,k6,k5);
        end;
    function findnum(k1,k2,k3,k4,k5,k6:longint):longint;
        begin
            if (k2>k5) or (k3<k4) then exit(0);
            if (k2>=k4) and (k3<=k5) then exit(findallnum(root[k1],k6));
            exit(findnum(k1*2,k2,(k2+k3) shr 1,k4,k5,k6)+findnum(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6));
        end;
    function findlesss(k1,k2:longint):longint;
        begin
            if k1=0 then exit(-maxlongint);
            if k2<=t[k1].w then exit(findlesss(t[k1].l,k2));
            exit(max(findlesss(t[k1].r,k2),t[k1].w));
        end;
    function findmore(k1,k2:longint):longint;
        begin
            if k1=0 then exit(maxlongint);
            if k2>=t[k1].w then exit(findmore(t[k1].r,k2));
            exit(min(findmore(t[k1].l,k2),t[k1].w));
        end;
    function findmax(k1,k2,k3,k4,k5,k6:longint):longint;
        begin
            if (k2>k5) or (k3<k4) then exit(-maxlongint);
            if (k2>=k4) and (k3<=k5) then {begin
                writeln(k2,' ',k3,' ',k4,' ',k5,' ',k6,' ',findlesss(root[k1],k6));}
                exit(findlesss(root[k1],k6));
            {end;}
            exit(max(findmax(k1*2,k2,(k2+k3) shr 1,k4,k5,k6),findmax(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6)));
        end;
    function findmin(k1,k2,k3,k4,k5,k6:longint):longint;
        begin
            if (k2>k5) or (k3<k4) then exit(maxlongint);
            if (k2>=k4) and (k3<=k5) then exit(findmore(root[k1],k6));
            exit(min(findmin(k1*2,k2,(k2+k3) shr 1,k4,k5,k6),findmin(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6)));
        end;
    begin
        readln(n,m);
        for i:=1 to n do read(x[i]); readln;
        len:=0; buildtree(1,1,n);
        for i:=1 to m do begin
            read(k6);
            if k6=2 then begin
                readln(k1,k2,k3); 
                l:=0; r:=1000000001;
                while l<r do begin
                    mid:=(l+r) shr 1; k4:=pd(1,1,n,k1,k2,mid);
                    if k4>=k3 then begin
                        ans:=mid; r:=mid;
                    end else l:=mid+1;
                end;
                writeln(ans);
            end else if k6=3 then begin
                readln(k1,k2);
                change(1,1,n,k1,x[k1],k2);
                x[k1]:=k2;
            end else if k6=1 then begin
                readln(k1,k2,k3);
                writeln(findnum(1,1,n,k1,k2,k3-1)+1);
            end else if k6=4 then begin
                readln(k1,k2,k3);
                writeln(findmax(1,1,n,k1,k2,k3));
            end else if k6=5 then begin
                readln(k1,k2,k3);
                writeln(findmin(1,1,n,k1,k2,k3));
            end;
        end;
    end.

【BZOJ2141】排队

用树套树来维护逆序对个数。挺巧妙的。nlog2n

program p2141;
    type
        tree=record
            father,l,r,w,size:longint;
        end;
    var
        t:array[0..2000000] of tree;
        w,root,x,y:array[0..3000000] of longint;
        i,j,n,m,len,k1,k2:longint;
        tot:int64;
    procedure zig(k:longint);
        var
            f:longint;
        begin
            f:=t[k].father; t[k].father:=t[f].father;
            if f=t[t[f].father].l then t[t[f].father].l:=k else if f=t[t[f].father].r then t[t[f].father].r:=k;
            t[f].l:=t[k].r; t[t[f].l].father:=f; t[k].r:=f; t[f].father:=k;
            t[f].size:=t[t[f].l].size+t[t[f].r].size+1; t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
        end;
    procedure zag(k:longint);
        var
            f:longint;
        begin
            f:=t[k].father; t[k].father:=t[f].father;
            if f=t[t[f].father].l then t[t[f].father].l:=k else if f=t[t[f].father].r then t[t[f].father].r:=k;
            t[f].r:=t[k].l; t[t[f].r].father:=f; t[k].l:=f; t[f].father:=k;
            t[f].size:=t[t[f].l].size+t[t[f].r].size+1; t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
        end;
    procedure up(k,k1:longint);
        var
            f1,f2:longint;
        begin
            while (k<>k1) do begin
                f1:=t[k].father; f2:=t[f1].father;
                if f1=k1 then begin
                    if k=t[f1].l then zig(k) else zag(k);
                    exit;
                end;
                if k=t[f1].l then begin
                    if f1=t[f2].l then begin zig(f1); zig(k); end else begin zig(k); zag(k); end;
                end else if f1=t[f2].l then begin zag(k); zig(k); end else begin zag(f1); zag(k); end;
                if f2=k1 then exit;
                end;
        end;
    procedure insert(k1,k2:longint);
        begin
            inc(t[k1].size);
            if t[k2].w>t[k1].w then begin
                if t[k1].r=0 then begin t[k1].r:=k2; t[k2].father:=k1; end else insert(t[k1].r,k2);
            end else begin
                if t[k1].l=0 then begin t[k1].l:=k2; t[k2].father:=k1; end else insert(t[k1].l,k2);
            end;
        end;
    procedure buildtree(k1,k2,k3:longint);
        var
            now,i,j:longint;
        begin
            inc(len); root[k1]:=len; now:=len-k2; len:=len+k3-k2;
            for i:=k2 to k3 do begin
                t[now+i].w:=w[i]; t[now+i].size:=1;
                if i<>k2 then begin
                    insert(root[k1],now+i);
                    {if k1=1 then begin
                        writeln(root[k1]);
                        for j:=1 to n do
                            writeln(t[j].l,' ',t[j].r,' ',t[j].size,' ',t[j].father,' ',t[j].w);
                        readln;
                    end;}
                    up(now+i,root[k1]); root[k1]:=now+i;
                end;
            end;
            if k2<>k3 then begin
                buildtree(k1*2,k2,(k2+k3) shr 1);
                buildtree(k1*2+1,(k2+k3) shr 1+1,k3);
            end;
        end;
    procedure sort(first,en:longint);
        var
            i,j:longint;
        begin
            i:=first; j:=en; x[0]:=x[i];
            while i<j do begin
                while (i<j) and ((w[x[j]]>w[x[0]]) or ((w[x[j]]=w[x[0]]) and (x[j]>=x[0]))) do dec(j);
                if i<j then x[i]:=x[j];
                while (i<j) and ((w[x[i]]<w[x[0]]) or ((w[x[i]]=w[x[0]]) and (x[i]<x[0]))) do inc(i);
                if i<j then x[j]:=x[i];
            end;
            x[i]:=x[0];
            if i>first+1 then sort(first,i-1);
            if i<en-1 then sort(i+1,en);
        end;
    function lowbit(k:longint):longint;
        begin
            exit(k and (-k));
        end;
    procedure addin(k:longint);
        var
            i:longint;
        begin
            i:=k;
            while i<=n do begin
                x[i]:=x[i]+1;
                i:=i+lowbit(i);
            end;
        end;
    function addup(k:longint):longint;
        var
            i,j:longint;
        begin
            j:=0; i:=k;
            while i>0 do begin
                j:=j+x[i];
                i:=i-lowbit(i);
            end;
            exit(j);
        end;
    procedure swap(var k1,k2:longint);
        var
            i:longint;
        begin
            i:=k1; k1:=k2; k2:=i;
        end;
    function findallless(k1,k2:longint):longint;
        begin
            if k1=0 then exit(0);
            if t[k1].w>k2 then exit(findallless(t[k1].l,k2));
            exit(findallless(t[k1].r,k2)+t[t[k1].l].size+1);
        end;
    function findallmore(k1,k2:longint):longint;
        begin
            if k1=0 then exit(0);
            if t[k1].w<k2 then exit(findallmore(t[k1].r,k2));
            exit(findallmore(t[k1].l,k2)+t[t[k1].r].size+1);
        end;
    function findless(k1,k2,k3,k4,k5,k6:longint):longint;
        begin
            if (k2>k5) or (k3<k4) then exit(0);
            if (k2>=k4) and (k3<=k5) then exit(findallless(root[k1],k6));
            exit(findless(k1*2,k2,(k2+k3) shr 1,k4,k5,k6)+findless(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6));
        end;
    function findmore(k1,k2,k3,k4,k5,k6:longint):longint;
        begin
            if (k2>k5) or (k3<k4) then exit(0);
            if (k2>=k4) and (k3<=k5) then exit(findallmore(root[k1],k6));
            exit(findmore(k1*2,k2,(k2+k3) shr 1,k4,k5,k6)+findmore(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6));
        end;
    function findwhere(k1,k2:longint):longint;
        begin
            if t[k1].w=k2 then exit(k1);
            if t[k1].w<k2 then exit(findwhere(t[k1].r,k2));
            exit(findwhere(t[k1].l,k2));
        end;
    function findleft(k:longint):longint;
        begin
            while t[k].l<>0 do k:=t[k].l;
            exit(k);
        end;
    function findright(k:longint):longint;
        begin
            while t[k].r<>0 do k:=t[k].r;
            exit(k);
        end;
    procedure change(k1,k2,k3,k4,k5:longint);
        var
            k,i,j,k6,k7:longint;
        begin
            if (k2>k4) or (k3<k4) then exit;
            if (k2=k3) then begin
                t[root[k1]].w:=k5; exit;
            end;
            k:=findwhere(root[k1],w[k4]); up(k,root[k1]); root[k1]:=k;
            if t[k].l=0 then begin
                t[k].size:=1; t[t[k].r].father:=0; root[k1]:=t[k].r; t[k].r:=0;
            end else if t[k].r=0 then begin
                t[k].size:=1; t[t[k].l].father:=0; root[k1]:=t[k].l; t[k].l:=0;
            end else begin
                k6:=findright(t[k].l); k7:=findleft(t[k].r);
                up(k6,k); up(k7,t[k6].r); root[k1]:=k6; t[k7].l:=0;
                dec(t[k7].size); dec(t[k6].size); t[k].father:=0;
            end;
            t[k].w:=k5; insert(root[k1],k);
            change(k1*2,k2,(k2+k3) shr 1,k4,k5); change(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5);
        end;
    begin
        {assign(input,'data.in'); reset(input);
        assign(output,'dat1a.out'); rewrite(output);}
        readln(n);
        for i:=1 to n do read(w[i]);
        len:=0;
        fillchar(t,sizeof(t),0);
        fillchar(root,sizeof(root),0);
        buildtree(1,1,n);
        for i:=1 to n do x[i]:=i;
        sort(1,n);
        for i:=1 to n do y[x[i]]:=i;
        fillchar(x,sizeof(x),0);
        for i:=n downto 1 do begin
            tot:=tot+addup(y[i]-1);
            addin(y[i]);
        end;
        writeln(tot);
        readln(m);
        {while true do begin
            read(i); writeln(findmore(1,1,n,1,n,i)); writeln(findless(1,1,n,1,n,i)); end;}
        for i:=1 to m do begin
            {writeln(root[1]);}{
        for j:=1 to n do
                writeln(t[j].l,' ',t[j].r,' ',t[j].size,' ',t[j].father,' ',t[j].w);}
            readln(k1,k2);
            if w[k1]=w[k2] then begin writeln(tot); continue; end;
            if k1>k2 then swap(k1,k2);
        {   writeln(findmore(1,1,n,1,n,w[k1]+1),' ',findless(1,1,n,1,n,w[k1]-1),' ',findless(1,1,n,1,n,w[k2]-1),' ',findmore(1,1,n,1,n,w[k2]+1));
        }   if k1+1<>k2 then tot:=tot+findmore(1,1,n,k1+1,k2-1,w[k1]+1)-findless(1,1,n,k1+1,k2-1,w[k1]-1)+findless(1,1,n,k1+1,k2-1,w[k2]-1)-findmore(1,1,n,k1+1,k2-1,w[k2]+1);
            if w[k1]<w[k2] then inc(tot) else dec(tot);
            change(1,1,n,k1,w[k2]); 
            {for j:=1 to n do
                writeln(t[j].l,' ',t[j].r,' ',t[j].size,' ',t[j].father,' ',t[j].w);}
            change(1,1,n,k2,w[k1]);
            swap(w[k1],w[k2]);
            writeln(tot);
        end;
    end.

【BZOJ2120】数颜色

用颜色种类个数的SPLAY来维护同种颜色的下一只画笔的位置。用树套树来求解。nlog2n。据说树状数组套主席树也可以做,但我太弱了不会。

 

program p2120;
	type
		tree=record
		l,r,father,w,size:longint;
	end;
	var
		root,first:array[0..800000] of longint;
		ro:array[0..2000000] of longint;
		t:array[0..4000000] of tree;
		w,x:array[0..20000] of longint;
		i,j,n,m,k1,k2,len:longint;
		ch:char;
	procedure zig(k:longint);
		var
			f:longint;
		begin
			f:=t[k].father; t[k].father:=t[f].father;
			if f=t[t[f].father].l then t[t[f].father].l:=k else if f=t[t[f].father].r then t[t[f].father].r:=k;
			t[f].father:=k; t[f].l:=t[k].r; t[t[f].l].father:=f; t[k].r:=f;
			t[f].size:=t[t[f].l].size+t[t[f].r].size+1; t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
		end;
	procedure zag(k:longint);
		var
			f:longint;
		begin
			f:=t[k].father; t[k].father:=t[f].father;
			if f=t[t[f].father].l then t[t[f].father].l:=k else if f=t[t[f].father].r then t[t[f].father].r:=k;
			t[f].father:=k; t[f].r:=t[k].l; t[t[f].r].father:=f; t[k].l:=f;
			t[f].size:=t[t[f].l].size+t[t[f].r].size+1; t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
		end;
	procedure up(k1,k2:longint);
		var
			f1,f2:longint;
		begin
			while (k1<>k2) and (t[k1].father<>k2) do begin
				f1:=t[k1].father; f2:=t[f1].father;
				if f2=k2 then begin
					if k1=t[f1].l then zig(k1) else zag(k1);
					exit;
				end;
				if k1=t[f1].l then begin
					if f1=t[f2].l then begin zig(f1); zig(k1); end else begin zig(k1); zag(k1); end;
				end else if f1=t[f2].l then begin zag(k1); zig(k1); end else begin zag(f1); zag(k1); end;
			end;
		end;
	procedure insert(k1,k2:longint);
		begin
			if k1=0 then exit;
			inc(t[k1].size);
			if t[k1].w<t[k2].w then begin
				if t[k1].r=0 then begin t[k1].r:=k2; t[k2].father:=k1; end else insert(t[k1].r,k2);
			end else if t[k1].l=0 then begin t[k1].l:=k2; t[k2].father:=k1; end else insert(t[k1].l,k2);
		end;
	function min(k1,k2:longint):longint;
		begin
			if k1<k2 then exit(k1) else exit(k2);
		end;
	function findless(k1,k2:longint):longint;
		begin
			if k1=0 then exit(maxlongint);
			if t[k1].w<=k2 then exit(findless(t[k1].r,k2));
			exit(min(findless(t[k1].l,k2),t[k1].w));
		end;
	procedure buildtree(k1,k2,k3:longint);
		var
			i,j,now:longint;
		begin
			now:=len-k2; root[k1]:=len; len:=len+k3-k2+1; first[k1]:=now;
			for i:=k2 to k3 do begin
				t[now+i].w:=x[i]; t[now+i].size:=1;
				if i<>k2 then begin
					insert(root[k1],now+i); up(now+i,0); root[k1]:=now+i;
				end;
			end;
			if k2<>k3 then begin
				buildtree(k1*2,k2,(k2+k3) shr 1);
				buildtree(k1*2+1,(k2+k3) shr 1+1,k3);
			end;
		end;
	procedure getchar(var ch:char);
		begin
			repeat
				read(ch);
			until(ch>='A') and (ch<='Z');
		end;
	function findbig(k1,k2:longint):longint;
		begin
			if k1=0 then exit(0);
			if t[k1].w>k2 then exit(findbig(t[k1].l,k2)+1+t[t[k1].r].size);
			exit(findbig(t[k1].r,k2));
		end;
	function findanswer(k1,k2,k3,k4,k5:longint):longint;
		begin
			if (k2>k5) or (k3<k4) then exit(0);
			if (k2>=k4) and (k3<=k5) then exit(findbig(root[k1],k5));
			exit(findanswer(k1*2,k2,(k2+k3) shr 1,k4,k5)+findanswer(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5));
		end;
	function findmorewhere(k1,k2:longint):longint;
		var
			k:longint;
		begin
			if k1=0 then exit(0);
			if t[k1].w>=t[k2].w then exit(findmorewhere(t[k1].l,k2));
			k:=findmorewhere(t[k1].r,k2);
			if k=0 then exit(k1) else exit(k);
		end;
	function findleft(k:longint):longint;
		begin
			while t[k].l<>0 do k:=t[k].l;
			exit(k);
		end;
	function findright(k:longint):longint;
		begin
			while t[k].r<>0 do k:=t[k].r;
			exit(k);
		end;
	procedure delete(k1,k2:longint);
		var
			l,r:longint;
		begin
			up(k2,0); root[k1]:=k2;
			if t[k2].l=0 then begin
				t[t[k2].r].father:=0; t[k2].size:=1; root[k1]:=t[k2].r;	t[k2].r:=0; 
			end else if t[k2].r=0 then begin
				t[t[k2].l].father:=0; t[k2].size:=1; root[k1]:=t[k2].l;	t[k2].l:=0;
			end else begin
				l:=findright(t[k2].l); r:=findleft(t[k2].r);
				up(l,0); up(r,l); root[k1]:=l;
				dec(t[l].size); dec(t[r].size); 
				t[r].l:=0; t[k2].father:=0;
			end;
		end;
	procedure changetreew(k1,k2,k3:longint);
		var
			k:longint;
		begin
			k:=first[k1]+k2;
			delete(k1,k); t[k].w:=k3;
			insert(root[k1],k); up(k,0); root[k1]:=k;
		end;
	procedure changew(k1,k2,k3,k4,k5:longint);
		begin
			if (k2>k4) or (k3<k4) then exit;
			changetreew(k1,k4,k5);
			if k2=k3 then exit;
			changew(k1*2,k2,(k2+k3) shr 1,k4,k5);
			changew(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5);
		end;
	procedure changex(k,color:longint);
		var
			l,r:longint;
		begin
			up(k,0); ro[w[k]]:=k;
			if t[k].l=0 then begin
				t[t[k].r].father:=0; t[k].size:=1; ro[w[k]]:=t[k].r; t[k].r:=0; 
			end else if t[k].r=0 then begin
				t[t[k].l].father:=0; t[k].size:=1; ro[w[k]]:=t[k].l;
				l:=findright(t[k].l); x[l]:=n+1;
				changew(1,1,n,l,n+1); t[k].l:=0;
			end else begin
				l:=findright(t[k].l); r:=findleft(t[k].r);
				up(l,0); up(r,l); ro[w[k]]:=l;
				dec(t[l].size); dec(t[r].size); 
				t[r].l:=0; t[k].father:=0;
				x[l]:=r; changew(1,1,n,l,r);
			end;
			insert(ro[color],k); up(k,0); ro[color]:=k;
			if t[k].l<>0 then begin
				l:=findright(t[k].l); changew(1,1,n,k,x[l]); changew(1,1,n,l,k); x[k]:=x[l]; x[l]:=k;
			end else if t[k].r<>0 then begin
				r:=findleft(t[k].r); changew(1,1,n,k,r); x[k]:=r;
			end else begin
				x[k]:=n+1; changew(1,1,n,k,n+1);
			end;
		end;
	begin
		readln(n,m);
		fillchar(root,sizeof(root),0);
		fillchar(ro,sizeof(ro),0);
		fillchar(t,sizeof(t),0);
		for i:=1 to n do begin
			read(w[i]);
			t[i].w:=i; t[i].size:=1;
			insert(ro[w[i]],i); up(i,0); ro[w[i]]:=i; 
		end;
		for i:=1 to n do begin
			up(i,0);
			if t[i].r=0 then x[i]:=n+1 else x[i]:=findleft(t[i].r);
		end;
		len:=n+1;
		buildtree(1,1,n);
		for i:=1 to m do begin
			{for j:=1 to n do writeln(x[j],' ',w[j]);
			for j:=1 to 6 do writeln(ro[j]); 
			for j:=1 to n do writeln(j,' ',t[j].l,' ',t[j].r,' ',t[j].size,' ',t[j].w,' ',ro[w[j]]);
			writeln;
			for j:=1 to n*2 do writeln(first[j],' ',root[j]);
			for j:=1+n to n*2 do writeln(j,' ',t[j].l,' ',t[j].r,' ',t[j].size,' ',t[j].w);
			}getchar(ch);
			if ch='Q' then begin
				readln(k1,k2);
				writeln(findanswer(1,1,n,k1,k2));
			end else begin
				readln(k1,k2);
				if w[k1]=k2 then continue;
				changex(k1,k2); w[k1]:=k2;
			end;
		end;
	end.
Category: 数据结构 | Tags: | Read Count: 2788

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com