jiry_2's Blog

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