1
9
2014
1

树套树专题

树套树是我写到至今最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: 7243
Avatar_small
Phoebe Kroger 说:
2019年2月17日 20:53

The definition of the programmer is taught for the students. All the issues of the program and best dissertation writing are inducted for the security of the norms and flaws of the people.


登录 *


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