jiry_2's Blog

树套树是我写到至今最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.

 LCT，传说中的动态树，写得我蛋疼啊。

【BZOJ2002】【hnoi2012】弹飞绵羊

裸LCT，只需要维护深度。

program p2002;
    type
        tree=record
            l,r,father,size:longint;
        end;
    var
        t:array[0..200100] of tree;
        root:array[0..200100] of boolean;
        z,i,j,n,m,k1,k2,k3:longint;
    procedure change(k:longint);
        begin
            t[t[k].l].father:=k; t[t[k].r].father:=k;
            t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
        end;
    procedure zig(i:longint); 
        begin
            z:=t[i].r;t[i].r:=t[z].l;t[t[i].r].father:=i;t[z].l:=i;
            if i=t[t[i].father].l then t[t[i].father].l:=z else
            if i=t[t[i].father].r then t[t[i].father].r:=z;
            t[z].father:=t[i].father;t[i].father:=z;
            root[z]:=root[i] xor root[z];
            root[i]:=root[i] xor root[z];
            t[i].size:=t[t[i].l].size+t[t[i].r].size+1;
            t[z].size:=t[t[z].l].size+t[t[z].r].size+1;
       end;
    procedure zag(i:longint); 
       begin
            z:=t[i].l;t[i].l:=t[z].r;t[t[i].l].father:=i;t[z].r:=i;
            if i=t[t[i].father].l then t[t[i].father].l:=z else
            if i=t[t[i].father].r then t[t[i].father].r:=z;
            t[z].father:=t[i].father;t[i].father:=z;
            root[z]:=root[i] xor root[z];
            root[i]:=root[i] xor root[z];
            t[i].size:=t[t[i].l].size+t[t[i].r].size+1;
            t[z].size:=t[t[z].l].size+t[t[z].r].size+1;
       end;
    procedure up(k1:longint);
        var
            i,j:longint;
        begin
          while root[k1]=false do
                if t[t[k1].father].l=k1 then zag(t[k1].father) else zig(t[k1].father);
        end;
    procedure all_change(k:longint);
        var
            f:longint;
        begin
            up(k);
            while t[k].father<>0 do begin
                f:=t[k].father;
                up(f);
                root[t[f].r]:=true; root[k]:=false;
                t[f].r:=k; t[f].size:=t[t[f].r].size+t[t[f].l].size+1;
                up(k);
            end;
        end;
    begin
        fillchar(root,sizeof(root),true);
        readln(n);
        fillchar(t,sizeof(t),0);
        for i:=1 to n do begin
            read(t[i].father); t[i].size:=1; t[i].father:=t[i].father+i; if t[i].father>n then t[i].father:=n+1;
        end;
        t[n+1].size:=1;
        readln(m);
        for i:=1 to m do begin
            read(k1,k2); inc(k2);
            if k1=1 then begin
                all_change(k2); writeln(t[t[k2].l].size);
            end else begin
                read(k3);
                up(k2); t[t[k2].l].father:=t[k2].father;
                root[t[k2].l]:=true; t[k2].l:=0;
                t[k2].father:=k2+k3; if t[k2].father>n then t[k2].father:=n+1;
                t[k2].size:=t[t[k2].r].size+1;
            end;
        end;

【BZOJ2049】【Sdoi2008】Cave 洞穴勘测

LCT，只需要维护联通。

program p2049;
    type
        tree=record
            l,r,father:longint;
        end;
    var
        t:array[0..500000] of tree;
        rev:array[0..500000] of boolean;
        i,j,n,k1,k2,k3,k4,m:longint;
        ch:char;
    function splay_root(k:longint):boolean;
        begin
            exit((t[k].father<>0) and ((t[t[k].father].l=k) or (t[t[k].father].r=k)));
        end;
    procedure swap(var k1,k2:longint);
        var
            k:longint;
        begin
            k:=k1; k1:=k2; k2:=k;
        end;
    procedure fz(k:longint);
        begin
            if k=0 then exit;
            swap(t[k].l,t[k].r); rev[k]:=rev[k] xor true;
        end;
    procedure pushdown(k:longint);
        begin
            if rev[k]=true then begin
                fz(t[k].l); fz(t[k].r); rev[k]:=false;
            end;
        end;
    procedure zig(k:longint);
        var
            f:longint;
            bo:boolean;
        begin
            f:=t[k].father; pushdown(f); pushdown(k);
            if t[t[f].father].l=f then t[t[f].father].l:=k else if t[t[f].father].r=f then t[t[f].father].r:=k;
            t[k].father:=t[f].father; t[f].l:=t[k].r; t[t[f].l].father:=f; t[k].r:=f; t[f].father:=k;
        end;
    procedure zag(k:longint);
        var
            f:longint;
            bo:boolean;
        begin
            f:=t[k].father; pushdown(f); pushdown(k);
            if t[t[f].father].l=f then t[t[f].father].l:=k else if t[t[f].father].r=f then t[t[f].father].r:=k;
            t[k].father:=t[f].father; t[f].r:=t[k].l; t[t[f].r].father:=f; t[k].l:=f; t[f].father:=k;
        end;
    procedure splay(k:longint);
        begin
            pushdown(k);
            while splay_root(k)=true do
                if k=t[t[k].father].l then zig(k) else zag(k);
        end;
    function access(k:longint):longint;
        var
            now:longint;
        begin
            now:=0;
            while k<>0 do begin
                splay(k);
                t[k].r:=now;
                now:=k;
                k:=t[k].father;
            end;
            exit(now);
        end;
    procedure makeroot(k:longint);
        var
            f:longint;
        begin
            f:=access(k);
            fz(f); splay(k);
        end;
    procedure link(k1,k2:longint);  
        var
            k:longint;
        begin
            makeroot(k1); t[k1].father:=k2; k:=access(k1); 
        end;
    procedure cut(k1,k2:longint);
        var
            k:longint;
        begin
            makeroot(k1); k:=access(k2); splay(k2); t[t[k2].l].father:=0; t[k2].l:=0;
        end;
    function findleft(k:longint):longint;
        begin
            pushdown(k);
            if t[k].l=0 then exit(k) else exit(findleft(t[k].l));
        end;
    begin
        readln(n,m);
        fillchar(rev,sizeof(rev),false);
        fillchar(t,sizeof(t),0);
        for i:=1 to m do begin
            read(ch);
            {for j:=1 to n do if rev[j]=true then writeln(true);}
            if ch='C' then begin
                for j:=1 to 6 do read(ch); readln(k1,k2);
                link(k1,k2);
            end else if ch='D' then begin
                for j:=1 to 6 do read(ch); readln(k1,k2);
                cut(k1,k2);
            end else begin
                for j:=1 to 4 do read(ch); readln(k1,k2);
                k3:=findleft(access(k1)); k4:=findleft(access(k2));
                if k3=k4 then writeln('Yes') else writeln('No');
            end;
        end;
    end.

【BZOJ2243】【SDOI2011】染色

LCT，需要一个区间覆盖的标记。

program p2243;
    type
        tree=record
            l,r,left,right,w,ans,father:longint;
        end;
    var
        t:array[0..110000] of tree;
        rev:array[0..110000] of boolean;
        color:array[0..110000] of longint;
        n,m,i,j,k1,k2,k3:longint;
        ch:char;
    procedure changecolor(k1,k2:longint);
        begin
            if k1=0 then exit;
            color[k1]:=k2; t[k1].w:=k2; t[k1].left:=k2; t[k1].right:=k2; t[k1].ans:=1;
        end;
    function splay_root(k:longint):boolean;
        begin
            exit((t[k].father<>0) and ((t[t[k].father].l=k) or (t[t[k].father].r=k)));
        end;
    procedure swap(var k1,k2:longint);
        var
            k:longint;
        begin
            k:=k1; k1:=k2; k2:=k;
        end;
    procedure fz(k:longint);
        begin
            if k=0 then exit;
            swap(t[k].l,t[k].r); swap(t[k].left,t[k].right); rev[k]:=rev[k] xor true; 
        end;
    procedure pushdown(k:longint);
        begin
            if k=0 then exit;
            if rev[k]=true then begin
                fz(t[k].l); fz(t[k].r); rev[k]:=false;
            end;
            if color[k]<>-1 then begin
                changecolor(t[k].l,color[k]); changecolor(t[k].r,color[k]); color[k]:=-1;
            end;
        end;
    procedure change(k:longint);
        begin
            pushdown(t[k].l); pushdown(t[k].r);
            t[k].left:=t[t[k].l].left; t[k].right:=t[t[k].r].right;
            if t[k].left=-1 then t[k].left:=t[k].w;
            if t[k].right=-1 then t[k].right:=t[k].w;
            t[k].ans:=t[t[k].l].ans+t[t[k].r].ans+1;
            if t[k].w=t[t[k].l].right then dec(t[k].ans);
            if t[k].w=t[t[k].r].left then dec(t[k].ans);
        end;
    procedure zig(k:longint);
        var
            f:longint;
        begin
            f:=t[k].father; pushdown(f); pushdown(k); 
            if t[t[f].father].l=f then t[t[f].father].l:=k else if t[t[f].father].r=f then t[t[f].father].r:=k;
            t[k].father:=t[f].father; t[f].l:=t[k].r; t[t[f].l].father:=f; t[k].r:=f; t[f].father:=k;
            change(f); {change(k);}
        end;
    procedure zag(k:longint);
        var
            f:longint;
        begin
            f:=t[k].father; pushdown(f); pushdown(k); 
            if t[t[f].father].l=f then t[t[f].father].l:=k else if t[t[f].father].r=f then t[t[f].father].r:=k;
            t[k].father:=t[f].father; t[f].r:=t[k].l; t[t[f].r].father:=f; t[k].l:=f; t[f].father:=k;
            change(f); {change(k);}
        end;
    procedure splay(k:longint);
        begin
            pushdown(k);
            while splay_root(k)=true do
                if k=t[t[k].father].l then zig(k) else zag(k);
            change(k);
        end;
    function access(k:longint):longint;
        var
            now:longint;
        begin
            now:=0;
            while k<>0 do begin
                splay(k); t[k].r:=now; change(k); now:=k; k:=t[k].father;
            end;
            exit(now);
        end;
    procedure makeroot(k:longint);
        var
            f:longint;
        begin
            f:=access(k); fz(f); splay(k);
        end;
    procedure link(k1,k2:longint);
        var
            f:longint;
        begin
            makeroot(k1); t[k1].father:=k2; f:=access(k1);
        end;
    procedure cut(k1,k2:longint);
        var
            f:longint;
        begin
            makeroot(k1); access(k2); splay(k2); t[t[k2].l].father:=0; t[k2].l:=0; change(k2);
        end;
    function findanswer(k1,k2:longint):longint;
        var
            f:longint;
        begin
            makeroot(k1); exit(t[access(k2)].ans);
        end;
    procedure rebuild(k1,k2,k3:longint);
        var
            k:longint;
        begin
            makeroot(k1); k:=access(k2); changecolor(k,k3);
        end;
    begin
        readln(n,m);
        fillchar(t,sizeof(t),0);
        fillchar(rev,sizeof(rev),false);
        fillchar(color,sizeof(color),-1);
        for i:=1 to n do begin
            read(t[i].w); t[i].left:=t[i].w; t[i].right:=t[i].w;
        end; readln;
        t[0].w:=-1; t[0].left:=-1; t[0].right:=-1;
        for i:=1 to n-1 do begin
            readln(k1,k2); link(k1,k2);
        end;
        for i:=1 to m do begin
            read(ch);
            if ch='Q' then begin
                readln(k1,k2); writeln(findanswer(k1,k2));
            end else begin
                readln(k1,k2,k3); rebuild(k1,k2,k3);
            end;
        end;
    end.

【BZOJ2631】tree(伍一鸣)

双标记的LCT，PASCAL由于常熟原因T了一点。

program p2631;
    const
        modd=51061;
    type
        tree=record
            father,l,r,size:longint;
            w,ans:int64;
        end;
    var
        t:array[0..210000] of tree;
        x,y:array[0..210000] of int64;
        rev:array[0..210000] of boolean;
        i,j,n,m,k1,k2,k3:longint;
        ch:char;
    procedure chen(k1,k2:longint);
        begin
            if k1=0 then exit;
            x[k1]:=x[k1]*k2 mod modd; y[k1]:=y[k1]*k2 mod modd;
            t[k1].w:=t[k1].w*k2 mod modd; t[k1].ans:=t[k1].ans*k2 mod modd;
        end;
    procedure jia(k1,k2:longint);
        begin
            if k1=0 then exit;
         {   if y[k1]<>1 then begin
                chen(t[k1].l,y[k1]); chen(t[k1].r,y[k1]); y[k1]:=1;
            end;}
            x[k1]:=x[k1]+k2; t[k1].w:=t[k1].w+k2;  t[k1].ans:=t[k1].ans+k2*t[k1].size;
        end;
    procedure fz(k:longint);
        begin
            if k=0 then exit;
            t[k].l:=t[k].l xor t[k].r;
            t[k].r:=t[k].r xor t[k].l;
            t[k].l:=t[k].l xor t[k].r;
            rev[k]:=rev[k] xor true;
        end;
    procedure pushdown(k:longint);
        begin
            if k=0 then exit;
            if rev[k]=true then begin
                fz(t[k].l); fz(t[k].r); rev[k]:=false;
            end;
            if y[k]<>1 then begin
                chen(t[k].l,y[k]); chen(t[k].r,y[k]); y[k]:=1;
            end;
            if x[k]<>0 then begin
                jia(t[k].l,x[k]); jia(t[k].r,x[k]); x[k]:=0;
            end;
        end;
    procedure change(k:longint);
        begin
            if k=0 then exit;
            t[k].ans:=(t[t[k].l].ans+t[t[k].r].ans+t[k].w) mod modd;
            t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
        end;
    procedure zig(k:longint);
        var
            f:longint;
        begin
            f:=t[k].father; pushdown(f); pushdown(k);
            if t[t[f].father].l=f then t[t[f].father].l:=k else if t[t[f].father].r=f then t[t[f].father].r:=k;
            t[k].father:=t[f].father; t[f].l:=t[k].r; t[t[f].l].father:=f; t[k].r:=f; t[f].father:=k;
            change(f); 
        end;
    procedure zag(k:longint);
        var
            f:longint;
        begin
            f:=t[k].father; pushdown(f); pushdown(k);
            if t[t[f].father].l=f then t[t[f].father].l:=k else if t[t[f].father].r=f then t[t[f].father].r:=k;
            t[k].father:=t[f].father; t[f].r:=t[k].l; t[t[f].r].father:=f; t[k].l:=f; t[f].father:=k;
            change(f); 
        end;
    function splay_root(k:longint):boolean;
        begin
            exit((t[k].father<>0) and ((t[t[k].father].l=k) or (t[t[k].father].r=k)));
        end;
    procedure splay(k:longint);
        var
            f1,f2:longint;
        begin
            pushdown(k);
            while (splay_root(k)=true) do begin
                f1:=t[k].father; f2:=t[f1].father;
                if splay_root(f1)=false then begin
                    if k=t[t[k].father].l then zig(k) else zag(k);
                    break;
                end;
                pushdown(f2);
                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;
            end;
            change(k);
        end;
    function access(k:longint):longint;
        var
            now:longint;
        begin
            now:=0;
            while k<>0 do begin
                splay(k); t[k].r:=now; change(k); now:=k; k:=t[k].father;
            end;
            exit(now);
        end;
    procedure makeroot(k:longint);
        begin
            fz(access(k)); splay(k);
        end;
    procedure link(k1,k2:longint);
        var
            k:longint;
        begin
            makeroot(k1); t[k1].father:=k2; k:=access(k1);
        end;
    procedure cut(k1,k2:longint);
        var
            k:longint;
        begin
            makeroot(k1); k:=access(k2); splay(k2); t[t[k2].l].father:=0; t[k2].l:=0; change(k2);
        end;
    procedure add1(k1,k2,k3:longint);
        begin
            makeroot(k1); jia(access(k2),k3);
        end;
    procedure add2(k1,k2,k3:longint);
        begin
            makeroot(k1); chen(access(k2),k3);
        end;
    function findanswer(k1,k2:longint):longint;
        begin
            makeroot(k1); exit(t[access(k2)].ans);
        end;
    begin
        readln(n,m);
        fillchar(t,sizeof(t),0);
        fillchar(x,sizeof(x),0);
        fillchar(rev,sizeof(rev),false);
        for i:=1 to n do begin
            y[i]:=1; t[i].size:=1; t[i].w:=1; t[i].ans:=1;
        end;
        for i:=1 to n-1 do begin
            readln(k1,k2);
            link(k1,k2);
        end;
        for i:=1 to m do begin
            read(ch);
            if ch='+' then begin
                readln(k1,k2,k3);
                add1(k1,k2,k3);
            end else if ch='/' then begin
                readln(k1,k2);
                writeln(findanswer(k1,k2));
            end else if ch='-' then begin
                read(k1,k2); cut(k1,k2);
                readln(k1,k2); link(k1,k2);
            end else begin
                readln(k1,k2,k3);
                add2(k1,k2,k3);
            end;
        end;
    end.

好久没来这儿了，忙了好久的数据库结构，现在来除个草吧。

【BZOJ3223】【TYVJ1729】文艺平衡树

只需要一个翻转标记。华丽的nlogn复杂度。

program p3223;
    type
        tree=record
            rev:boolean;
            l,r,w,size,father:longint;
        end;
    var
        t:array[0..110000] of tree;
        i,j,n,len,k1,k2,m,k3:longint;
    procedure change(k:longint);
        begin
            if k=0 then exit;
            t[t[k].l].father:=k; t[t[k].r].father:=k;
            t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
        end;
    procedure reversal(k:longint);
        var
            i:longint;
        begin
            if k=0 then exit;
            i:=t[k].l; t[k].l:=t[k].r; t[k].r:=i;
            t[k].rev:=not t[k].rev;
        end;
    procedure pushdown(k:longint);
        begin
            if k=0 then exit;
            if t[k].rev then begin 
                reversal(t[k].l); reversal(t[k].r); t[k].rev:=false;
            end;
        end;
    procedure zig(k:longint);
        var
            i:tree;
            f:longint;
        begin
            f:=t[k].father;
            pushdown(f); pushdown(k);
            i:=t[f]; t[f]:=t[k]; t[k]:=i;
            t[k].l:=t[f].r; t[f].r:=k; t[f].father:=t[k].father; t[k].father:=f;
            change(k); change(f);
        end;
    procedure zag(k:longint);
        var
            i:tree;
            f:longint;
        begin
            f:=t[k].father;
            pushdown(f); pushdown(k);
            i:=t[f]; t[f]:=t[k]; t[k]:=i;
            t[k].r:=t[f].l; t[f].l:=k; t[f].father:=t[k].father; t[k].father:=f;
            change(k); change(f);
        end;
    procedure build(now,l,r:longint);
        var
            mid:longint;
        begin
            t[now].rev:=false; 
            mid:=(l+r) shr 1;  t[now].w:=mid;
            if mid>l then begin
                t[now].l:=len+1; inc(len); build(len,l,mid-1);
            end;
            if mid<r then begin
                t[now].r:=len+1; inc(len); build(len,mid+1,r);
            end;
            change(now);
        end;
    function find(now,k:longint):longint;
        var
            l,r:longint;
        begin
            pushdown(now);
            l:=t[now].l; r:=t[now].r;
            if t[l].size=k-1 then exit(now);
            if t[l].size<k-1 then exit(find(r,k-t[l].size-1));
            exit(find(l,k));
        end;
    procedure up(k1,k2:longint);
        var
            i,j:longint;
        begin
            if k1=k2 then exit;
            if t[k1].father=k2 then begin
                if t[k2].l=k1 then zig(k1) else zag(k1);
                exit;
            end;
            i:=t[k1].father; j:=t[i].father;
            if k1=t[i].l then begin
                if i=t[j].l then begin zig(i); zig(k1); end else begin zig(k1); zag(i); end;
            end else
                if i=t[j].l then begin zag(k1); zig(i); end else begin zag(i); zag(k1); end;
            up(j,k2);
        end;
    begin
        readln(n,m);
        len:=1;
        t[0].size:=0;
        build(1,0,n+1);
        for i:=1 to m do begin
            readln(k1,k2);
            k3:=find(1,k1);
            up(k3,1);
            t[0].size:=0;
            k3:=find(1,k2+2);
            up(k3,t[1].r);
            t[0].size:=0;
            reversal(t[t[1].r].l);
        end;
        for i:=1 to n do begin
            k3:=find(1,i+1);
            write(t[k3].w);
            if i<>n then write(' ');
        end; 
    end.

首先我不得不吐槽一下BZOJ，出这么一道pascal无解的题目有什么意思呢？我就算优化到极限pascal还是TLE，而C++一个复杂度比我没有花之前的程序居然11S就A了，C++秀优越也用不着这样啊。

先搞个DFS序，这样的话就可以用树状数组来维护了。最终的答案就是add_up(s[k1]) xor add_up(s[k2]) xor w[closefather(k1,k2)]，s是dfs序中最先出现的位置，w是权值。最近公共祖先就用LCA搞掉。就如题目所说，这道题目要用手工栈，不然会在爆栈OJ爆栈。接下来是我无比惨烈的解题截图。（不要怪我没节操的贴了代码）

program p2819;
    type   
        bian=record
            next,point:longint;
        end;
    var
        y:array[1..500000,1..4] of longint;
        x:array[1..1000010] of longint;
        d,w,p,s,e:array[1..500010] of longint;
        f:array[1..500010,0..20] of longint;
        b:array[1..1000010] of bian;
        q,len,i,j,n,k1,k2:longint;
        ch:char;
        bo:boolean;
    function getchar:char;
        var
            ch:char;
        begin
            read(ch);
            while (ch<>'Q') and (ch<>'C') do
                read(ch);
            exit(ch);
        end;
    procedure ade(k1,k2:longint);
        begin
            inc(len);
            b[len].point:=k2;
            b[len].next:=p[k1];
            p[k1]:=len;
        end;
    procedure add(k1,k2:longint);
        begin
            ade(k1,k2);
            ade(k2,k1);
        end;
    procedure bfs;
        var
            i,j,head,now:longint;
        begin
            head:=1; now:=1; y[1,1]:=1; y[1,2]:=p[1]; y[1,3]:=0; y[1,4]:=1;
            d[1]:=1; f[1,0]:=0; s[1]:=1;
            while now>0 do begin
                i:=y[now,2];
                if (i<>0) and (b[i].point=y[now,3]) then i:=b[i].next;
                if (i=0) then begin
                    inc(head); e[y[now,1]]:=head;
                    dec(now);
                    continue;
                end;
                inc(now); y[now,1]:=b[i].point; y[now,2]:=p[y[now,1]]; y[now,3]:=y[now-1,1]; y[now,4]:=y[now-1,4]+1;
                inc(head); f[y[now,1],0]:=y[now,3]; s[y[now,1]]:=head; d[y[now,1]]:=y[now,4];
                y[now-1,2]:=b[i].next;
            end;
        end;
    function lowbit(k:longint):longint;
        begin
            exit(k and (-k));
        end;
    procedure add_in(k1,k2:longint);
        var
            i,j:longint;
        begin
            i:=k1;
            while i<=1000010 do begin
                x[i]:=x[i] xor k2;
                i:=i+lowbit(i);
            end;
        end;
    function add_up(k:longint):longint;
        var
            i,num:longint;
        begin
            i:=k; num:=0;
            while i>0 do begin
                num:=num xor x[i];
                i:=i-lowbit(i);
            end;
            exit(num);
        end;
    function go_up(k1,k2:longint):longint;
        var
            i,j,k:longint;
        begin
            for k:=0 to 20 do
                if 1 shl k>k2 then break;
            dec(k); if k<0 then exit(k1);
            j:=k1;
            for i:=0 to k do
                if k2 and (1 shl i)>0 then
                    j:=f[j,i];
            exit(j);
        end;
    function find(k1,k2:longint):longint;
        var
            i,j,k:longint;
        begin
            if d[k1]>d[k2] then begin
                i:=k1; k1:=k2; k2:=i;
            end;
            k2:=go_up(k2,d[k2]-d[k1]);
            if k1=k2 then exit(k1);
            for k:=1 to 20 do
                if 1 shl k>=d[k1] then break;
            dec(k);
            for i:=k downto 0 do
                if f[k1,i]<>f[k2,i] then begin
                    k1:=f[k1,i]; k2:=f[k2,i];
                end;
            exit(f[k1,0]);
        end;
    begin
        readln(n);
        for i:=1 to n do
            read(w[i]);
        len:=0;
        fillchar(p,sizeof(p),0);
        fillchar(b,sizeof(b),0);
        for i:=1 to n-1 do begin
            readln(k1,k2);
            add(k1,k2);
        end;
        fillchar(d,sizeof(d),0);
        len:=0;
        bfs;
        fillchar(x,sizeof(x),0);
        for i:=1 to n do begin
            add_in(s[i],w[i]);
            add_in(e[i],w[i]);
        end;
        for i:=1 to 20 do begin
            bo:=false;
            for j:=1 to n do
                if (1 shl i)<d[j] then begin
                    bo:=true; 
                    f[j,i]:=f[f[j,i-1],i-1];
                end;
            if bo=false then break;
        end;
        readln(q);
        for i:=1 to q do begin
            ch:=getchar;
            if ch='Q' then begin
                readln(k1,k2);
                j:=add_up(s[k1]) xor add_up(s[k2]) xor w[find(k1,k2)];
                if j=0 then writeln('No') else writeln('Yes');
            end else begin
                readln(k1,k2);
                add_in(s[k1],w[k1]); add_in(e[k1],w[k1]);
                add_in(s[k1],k2); add_in(e[k1],k2);
                w[k1]:=k2;
            end;
        end;
    end.

这道题是对pascal赤果果的鄙视。。。pascal在tyvj上AC了在BZ上WA。要来数据在CENA上AC了再BZ上接着WA。网上抄来PASCAL标程还TM的WA。最后怒了贴个C++结果A了。。。QAQ

二维树状数组的矩形修改和查找。令D[X,Y]表示在矩形(X,Y)(N,M)上加上D[X,Y]。则点(X,Y)的权值就是SIGMA(D(I,J))。然后就瞎搞搞，维护D[X,Y]，D[X,Y]*X，D[X,Y]*Y，D[X,Y]*X*Y。然后就可以了。

代码依然PASCAL。我是P党我骄傲！

program p3132;
    type
        arr=array[0..2050,0..2050] of longint;
    var
        i,j,n,m,k1,k2,k3,k4,k5:longint;
        a,b,c,d:arr;
        ch:char;
    procedure getchar(var k:char);
        begin
            read(k);
            while ((k<'A') or (k>'Z')) and ((k<'a') or (k>'z'))do
                read(k);
        end;
    function lowbit(k:longint):longint;
        begin
            exit(k and (-k));
        end;
    procedure add(var x:arr;k1,k2,k3:longint);
        var
            i,j:longint;
        begin
            i:=k1; 
            while i<=n do begin
                j:=k2;
                while j<=m do begin
                    x[i,j]:=x[i,j]+k3;
                    j:=j+lowbit(j);
                end;
                i:=i+lowbit(i);
            end;
        end;
    function find(var x:arr;k1,k2:longint):longint;
        var
            i,j,num:longint;
        begin
            i:=k1; num:=0;
            while i>0 do begin
                j:=k2;
                while j>0 do begin
                    num:=num+x[i,j];
                    j:=j-lowbit(j);
                end;
                i:=i-lowbit(i);
            end;
            exit(num);
        end;
    function findtotal(k1,k2:longint):longint;
        begin
            exit((k1+1)*(k2+1)*find(a,k1,k2) - (k1+1)*find(b,k1,k2) - (k2+1)*find(c,k1,k2) + find(d,k1,k2));
        end;
    procedure addtotal(k1,k2,k3,k4,k5:longint); 
        begin
            add(a,k1,k4,k5); add(a,k1,k2+1,-k5); add(a,k3+1,k4,-k5); add(a,k3+1,k2+1,k5);
            add(b,k1,k4,k5*k4); add(b,k1,k2+1,-k5*(k2+1)); add(b,k3+1,k4,-k5*k4); add(b,k3+1,k2+1,k5*(k2+1));
            add(c,k1,k4,k5*k1); add(c,k1,k2+1,-k5*k1); add(c,k3+1,k4,-k5*(k3+1)); add(c,k3+1,k2+1,k5*(k3+1));
            add(d,k1,k4,k5*k1*k4); add(d,k1,k2+1,-k5*k1*(k2+1)); add(d,k3+1,k4,-k5*(k3+1)*k4); add(d,k3+1,k2+1,k5*(k3+1)*(k2+1));
        end;
    begin
        getchar(ch);
        readln(n,m);
        fillchar(a,sizeof(a),0);
        fillchar(b,sizeof(b),0);
        fillchar(c,sizeof(c),0);
        fillchar(d,sizeof(d),0);
        while not eof do begin
            getchar(ch);
            if ch='L' then begin
                readln(k1,k2,k3,k4,k5);
                addtotal(k1,k4,k3,k2,k5);
            end else if ch='k' then begin
                readln(k1,k2,k3,k4);
                writeln(findtotal(k3,k4)+findtotal(k1-1,k2-1)-findtotal(k1-1,k4)-findtotal(k3,k2-1));
            end;
        end;
    end.

猥琐的树状数组，快排了三次，还要离散化。。代码又臭又长。原题等价于求所有水平数值线段的交点数目，把所有线段搞出来，分成水平的和竖直的，从上往下扫一遍，扫到横的就找一找它的左到右竖着的线段数。扫到竖着的上界就把它的横坐标插入，扫到下界就删掉。pascal党敲得翔都出来了，QAQ。

program p1818;
	type
		arr=array[0..1000000] of longint;
		line=record
			a,b:longint;
		end;
		point=record
			x,y,numx,numy:longint;
		end;
		point2=record
			y,a,b:longint;
		end;
	var
		p:array[1..1000000] of point;
		l:array[0..1000000] of point2;
		c:array[1..1000000] of longint;
		h,s:arr;
		x,y:array[0..1000000] of line;
		tot,len1,len2,i,j,n,len:longint;
	procedure sort1(first,en:longint);
		var
			i,j,t:longint;
		begin
			i:=first; j:=en; h[0]:=h[(i+j) div 2];
			while i<=j do begin
				while ((p[h[j]].x>p[h[0]].x) or ((p[h[j]].x=p[h[0]].x) and (p[h[j]].y>p[h[0]].y))) do dec(j);
				while ((p[h[i]].x<p[h[0]].x) or ((p[h[i]].x=p[h[0]].x) and (p[h[i]].y<p[h[0]].y))) do inc(i);
				if i<=j then begin
					t:=h[j]; h[j]:=h[i]; h[i]:=t;
					inc(i); dec(j);
				end;
			end;
			if j>first then sort1(first,j);
			if i<en then sort1(i,en);
		end;
	procedure sort2(first,en:longint);
		var
			i,j,t:longint;
		begin
			i:=first; j:=en; s[0]:=s[(i+j) div 2];
			while i<=j do begin
				while ((p[s[j]].y>p[s[0]].y) or ((p[s[j]].y=p[s[0]].y) and (p[s[j]].x>p[s[0]].x))) do dec(j);
				while ((p[s[i]].y<p[s[0]].y) or ((p[s[i]].y=p[s[0]].y) and (p[s[i]].x<p[s[0]].x))) do inc(i);
				if i<=j then begin
					t:=s[j]; s[j]:=s[i]; s[i]:=t;
					inc(i); dec(j);
				end;
			end;
			if j>first then sort2(first,j);
			if i<en then sort2(i,en);
		end;	
	procedure sort(first,en:longint);
		var
			i,j:longint;
			t:point2;
		begin
			i:=first; j:=en; l[0]:=l[(i+j) div 2];
			while i<=j do begin	
				while (l[j].y>l[0].y) do dec(j);
				while (l[i].y<l[0].y) do inc(i);
				if i<=j then begin 
					t:=l[j]; l[j]:=l[i]; l[i]:=t;
					inc(i); dec(j);
				end;
			end;
			if j>first then sort(first,j);
			if i<en then sort(i,en);
		end;
	function lowbit(k:longint):longint;
		begin
			exit(k and (-k));
		end;
	function find(k:longint):longint;
		var
			num,i:longint;
		begin
			num:=0;
			i:=k;
			while i>0 do begin
				num:=num+c[i];
				i:=i-lowbit(i);
			end;
			exit(num);
		end;
	procedure add(k1,k2:longint);
		var
			i:longint;
		begin
			i:=k1;
			while i<=n do begin
				inc(c[i],k2);
				i:=i+lowbit(i);
			end;
		end;
	begin
		readln(n);
		for i:=1 to n do
			readln(p[i].x,p[i].y);
		for i:=1 to n do begin
			h[i]:=i; s[i]:=i;
		end;
		sort1(1,n);
		sort2(1,n);
		j:=1; p[h[1]].numx:=1; len1:=0;
		for i:=2 to n do
			if p[h[i]].x=p[h[i-1]].x then begin
				p[h[i]].numx:=j;
				inc(len1);
				y[len1].a:=h[i-1]; y[len1].b:=h[i];
			end else begin
				inc(j);
				p[h[i]].numx:=j;
			end;
		j:=1; p[s[1]].numy:=1; len2:=0;
		for i:=2 to n do
			if p[s[i]].y=p[s[i-1]].y then begin
				p[s[i]].numy:=j;
				inc(len2);
				x[len2].a:=s[i-1]; x[len2].b:=s[i];
			end else begin
				inc(j);		
				p[s[i]].numy:=j;
			end;
		len:=0;
		for i:=1 to len2 do begin
			inc(len);
			l[len].y:=p[x[i].a].numy;
			l[len].a:=i;
			l[len].b:=1;
		end;
		for i:=1 to len1 do begin
			inc(len);
			l[len].y:=p[y[i].a].numy;
			l[len].a:=i;
			l[len].b:=2;
			inc(len);
			l[len].y:=p[y[i].b].numy;
			l[len].a:=i;
			l[len].b:=3;
		end;
		sort(1,len);
		tot:=0;
		fillchar(c,sizeof(c),0);
		for i:=1 to len do
			if l[i].b=1 then
				tot:=tot+find(p[x[l[i].a].b].numx-1)-find(p[x[l[i].a].a].numx)
			else if l[i].b=2 then 
				add(p[y[l[i].a].a].numx,1)
			else add(p[y[l[i].a].a].numx,-1);
		writeln(tot+n);
	end.

第一次发现线段树可以写得那么高端洋气上档次。旋转和翻转忽略掉，对于每个询问把位置变为原来的位置即可。然后在线段树中记录区间的左界右界，合并的时候如果相等则减一（要注意在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.

大水题一只，开100个二维树状数组表示，每一种颜色就可以了，查询的复杂度只有logm*logn，非常快。由于最近手残的严重，我还是喜闻乐见的WA了一次。

program p1452;
	var
		x:array[1..305,1..305,1..105] of longint;
		f:array[1..305,1..305] of longint;
		i,j,n,m,q,k1,k2,k3,k4,k5,k6:longint;
	function lowbit(k:longint):longint;
		begin
			exit(k and (-k));
		end;
	procedure add(k1,k2,k3,k4:longint);
		var
			i,j:longint;
		begin
			i:=k1;
			while i<=n do begin
				j:=k2;
				while j<=m do begin
					inc(x[i,j,k3],k4);
					j:=j+lowbit(j);
				end;
				i:=i+lowbit(i);
			end;
		end;
	function find(k1,k2,k3:longint):longint;
		var
			i,j,num:longint;
		begin
			i:=k1; num:=0;
			while i>0 do begin
				j:=k2;
				while j>0 do begin
					inc(num,x[i,j,k3]);
					j:=j-lowbit(j);
				end;
				i:=i-lowbit(i);
			end;
			exit(num);
		end;
	begin
		readln(n,m);
		fillchar(x,sizeof(x),0);
		for i:=1 to n do
			for j:=1 to m do begin
				read(f[i,j]);
				add(i,j,f[i,j],1);
			end;
		read(q);
		for i:=1 to q do begin
			read(k1);
			if k1=1 then begin
				readln(k2,k3,k4);
				add(k2,k3,f[k2,k3],-1);
				add(k2,k3,k4,1);
				f[k2,k3]:=k4;
			end else begin
				readln(k2,k4,k3,k5,k6);
				writeln(find(k4,k5,k6)+find(k2-1,k3-1,k6)-find(k2-1,k5,k6)-find(k4,k3-1,k6));
			end;
		end;
	end.

开始一直在想在线的查询，然后就被坑里面了。后来想想既然查询只有20W次步入全部记下来，然后以右界为关键字升序sort一下。然后从1到n扫一遍。利用树状数组，保证同一时刻树状数组中每种贝壳最多只存在一次，且其位置是当前这种贝壳位置的最右端。要达成这样只需要每次加入一个贝壳时把原来在树状数组中这个种类的贝壳删掉。当扫到某个区间的右界的时候就记下这个区间的答案，即为find(b)-find(a-1)。最后再按照原来的顺序把答案打出。要注意的是贝壳的编号可以为0，我就是被这个坑了然后W了一次，QAQ。运行时间依然有pascal特色，慢得出翔~

program p1787;
	type
		qj=record
			a,b:longint;
		end;
	var
		x,y:array[0..200000] of longint;
		num:array[0..1010000] of longint;
		q:array[1..400000] of qj;
		z,answer:array[0..400000] of longint;
		n,m,i,j:longint;
	function lowbit(k:longint):longint;
		begin
			exit(k and (-k));
		end;
	procedure add(k1,k2:longint);
		var
			i,j:longint;
		begin
			i:=k1;
			while i<=n do begin
				inc(x[i],k2);
				i:=i+lowbit(i);
			end;
		end;
	function find(k:longint):longint;
		var
			i,j:longint;
		begin
			i:=k; j:=0;
			while i>0 do begin
				j:=j+x[i];
				i:=i-lowbit(i);
			end;
			exit(j);
		end;
	procedure quick(first,en:longint);
		var
			i,j:longint;
		begin
			i:=first; j:=en; z[0]:=z[i];
			while i<j do begin
				while (i<j) and (q[z[0]].b<=q[z[j]].b) do dec(j);
				if i<j then z[i]:=z[j];
				while (i<j) and (q[z[0]].b>q[z[i]].b) do inc(i);
				if i<j then z[j]:=z[i];
			end;
			z[i]:=z[0];
			if i>first+1 then quick(first,i-1);
			if i<en-1 then quick(i+1,en);
		end;
	begin
		readln(n);
		for i:=1 to n do
			read(y[i]);
		readln(m);
		for i:=1 to m do begin
			readln(q[i].a,q[i].b);
			z[i]:=i;
		end;
		quick(1,m);
		j:=1;
		fillchar(x,sizeof(x),0);
		fillchar(num,sizeof(num),0);
		for i:=1 to n do begin
			add(i,1);
			if num[y[i]]<>0 then add(num[y[i]],-1);
			num[y[i]]:=i;
			while (j<=m) and (q[z[j]].b=i) do begin
				answer[z[j]]:=find(q[z[j]].b)-find(q[z[j]].a-1);
				inc(j);
			end;
			if j>m then break;
		end;
		for i:=1 to m do
			writeln(answer[i]);
	end.

为了求矩形中的点的数量，首先可以想到的就是二维线段树或者二维树状数组，但是这道题的数据范围比较大，即使离散化之后还有200万多的点，会超空间。所以只能用一维的树状数组，可以先把所有点（包括查询矩形的四个顶点）按照第一关键字Y轴升序排序，第二关键字X轴升序排序。然后离散化，然后再扫一遍，如果是点就插入到树状数组中，如果是查询就求和，其值为右上角为改点，左下角为原点的矩形内的点，每个查询可以通过四个顶点的加减来考虑。有两点要考虑：1.要考虑边界，可以通过给点设值来排序。2.对N=0的情况要特判。

program p1935;
	const
		p:array[0..4] of longint=(4,1,3,5,2);
	type
		tree=record
			x,y:longint;
		end;
		num=record
			x,y,sx,pd,ls:longint;
		end;
		question=record
			x1,x2,y1,y2:longint;
			w:array[0..4] of longint;
		end;
		hzb=record	
			x,sx:longint;
		end;
	var
		t:array[1..500000] of tree;
		q:array[1..500000] of question;
		x:array[0..3000000] of num;
		h:array[0..3000000] of longint;
		c:array[1..3000000] of longint;
		len,n,m,i,j:longint;
	procedure add(k1,k2,k3,k4:longint);
		begin
			inc(len);
			x[len].x:=k1;
			x[len].y:=k2;
			x[len].sx:=k4;
			x[len].pd:=k3;
		end;
	function bo(k1,k2:longint):boolean;
		begin
			if x[k1].y<x[k2].y then exit(true);
			if x[k1].y>x[k2].y then exit(false);
			if x[k1].pd<=1 then exit(true);
			if x[k2].pd<=1 then exit(false);
			if x[k1].x<x[k2].x then exit(true);
			if x[k1].x>x[k2].x then exit(false);
			if x[k1].pd<=x[k2].pd then exit(true);
			exit(false);
		end;
	procedure quick(first,en:longint);
		var
			i,j:longint;
		begin
			{writeln(first,' ',en);}
			i:=first; j:=en; x[0]:=x[first];
			while i<j do begin
				{writeln(x[i].x,' ',x[i].y,' ',x[i].pd);
				writeln(x[j].x,' ',x[j].y,' ',x[j].pd);
				writeln(x[0].x,' ',x[0].y,' ',x[0].pd);}
				while (i<j) and (bo(0,j)=true) do dec(j);
				if i<j then x[i]:=x[j];
				while (i<j) and (bo(i,0)=true) do inc(i);
				if i<j then x[j]:=x[i];
			end;
			x[i]:=x[0];
			if i>first+1 then quick(first,i-1);
			if i<en-1 then quick(i+1,en);
		end;
	procedure sort(first,en:longint);
		var
			i,j:longint;
		begin
			i:=first; j:=en; h[0]:=h[i];
			while i<j do begin
				while (i<j) and ((x[h[j]].x>x[h[0]].x) or ((x[h[j]].x=x[h[0]].x)) and (p[x[h[j]].pd]>=p[x[h[0]].pd])) do dec(j);
				if i<j then h[i]:=h[j];
				while (i<j) and ((x[h[i]].x<x[h[0]].x) or ((x[h[i]].x=x[h[0]].x)) and (p[x[h[i]].pd]<p[x[h[0]].pd])) do inc(i);
				if i<j then h[j]:=h[i];
			end;
			h[i]:=h[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 add(k:longint);
		var
			i,j:longint;
		begin
			i:=k;
			while i<=len do begin
				inc(c[i]);
				i:=i+lowbit(i);
			end;
		end;
	function total(k:longint):longint;
		var
			i,j,num:longint;
		begin
			i:=k; num:=0;
			while i>0 do begin
				num:=num+c[i];
				i:=i-lowbit(i);
			end;
			exit(num);
		end;
	begin
		readln(n,m); len:=0;
		fillchar(x,sizeof(x),0);
		for i:=1 to n do begin
			readln(t[i].x,t[i].y);
			add(t[i].x,t[i].y,2,i);
		end;
		if n=0 then begin
			for i:=1 to m do
				writeln(0);
			exit;
		end;
		for i:=1 to m do begin
			readln(q[i].x1,q[i].y1,q[i].x2,q[i].y2);
			add(q[i].x1,q[i].y1,1,i);
			add(q[i].x2,q[i].y2,3,i);
			add(q[i].x1,q[i].y2,4,i);
			add(q[i].x2,q[i].y1,0,i);
		end;
		quick(1,len);
		fillchar(c,sizeof(c),0);
		for i:=1 to len do
			h[i]:=i;
		sort(1,len);
		for i:=1 to len do
			x[h[i]].ls:=i;
		for i:=1 to len do
			if x[i].pd=2 then 
				add(x[i].ls)
			else 
				q[x[i].sx].w[x[i].pd]:=total(x[i].ls);
		for i:=1 to m do begin
			writeln(q[i].w[3]+q[i].w[1]-q[i].w[0]-q[i].w[4]);
		end;
	end.