本文主要是介绍[BZOJ2743] [HEOI2012]采花，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
http://www.lydsy.com/JudgeOnline/problem.php?id=2743
题目大意
给定一个序列，多次询问区间内出现两次以上的数的数量
题解
和HH的项链是一样的,离线处理树状数组维护,唯一的差别在于HH是维护区间第一个,而这道是维护区间第二个
我们用next[I]表示i后面第一个和i颜色相同的位置
在我们把左端点i向后推的时候,我们要修改next[i]-1,next[next[i]]+1
constmaxn=1000000;
varans,x,y,next,co,fi:array[0..maxn+100]of longint;z:array[0..maxn+100,1..3]of longint;i,j,k:longint;n,m,ma,a,len:longint;
procedure sort(l,r:longint);
var i,j,a,b,c,k:longint;
begini:=l; j:=r; a:=z[(l+r) div 2,1]; c:=z[(l+r)div 2,2];repeatwhile (z[i,1]<a)or((z[i,1]=a)and(z[i,2]<c)) do inc(i);while (a<z[j,1])or((z[j,1]=a)and(z[j,2]>c)) do dec(j);if not(i>j) thenbeginfor k:=1 to 3 dobegin b:=z[i,k]; z[i,k]:=z[j,k]; z[j,k]:=b; end;inc(i); dec(j);end;until i>j;if l<j then sort(l,j);if i<r then sort(i,r);
end;function lowbit(a:longint):longint;
begin exit(a and(-a)); end;procedure update(a,b:longint);
beginwhile a<=n dobegininc(y[a],b);inc(a,lowbit(a));end;
end;function query(a:longint):longint;
var tt:longint;
begintt:=0;while a>0 dobegininc(tt,y[a]);dec(a,lowbit(a));end;exit(tt);
end;beginreadln(n,ma,m);for i:=1 to n dobegin read(a); next[co[a]]:=i; if co[a]=0 then begin inc(len); fi[len]:=i; end; co[a]:=i; end;for i:=1 to len dobeginif next[fi[i]]=0 then continue;x[next[fi[i]]]:=1; update(next[fi[i]],1);end;for i:=1 to m dobegin readln(z[i,1],z[i,2]); z[i,3]:=i; end;next[0]:=0;sort(1,m);z[0,1]:=1;for i:=1 to m dobeginif z[i,1]<>z[i-1,1] thenfor j:=z[i-1,1] to z[i,1]-1 dobeginif next[j]<>0 then update(next[j],-1);if next[next[j]]<>0 then update(next[next[j]],1);end;ans[z[i,3]]:=query(z[i,2]);end;for i:=1 to m dowriteln(ans[i]);
end.这篇关于[BZOJ2743] [HEOI2012]采花的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
