jiry_2's Blog

开始一直在想在线的查询，然后就被坑里面了。后来想想既然查询只有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.