8
30
2013
0

【BZOJ1878】【SDOI2009】HH的项链【树状数组】

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

 

Category: 数据结构 | Tags: | Read Count: 2841

登录 *


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