[BZOJ1878] [SDOI2009]HH的项链

本文主要是介绍[BZOJ1878] [SDOI2009]HH的项链，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

http://www.lydsy.com/JudgeOnline/problem.php?id=1878

题目大意

给定一个序列，求一个区间内有多少个不同的数

题解

核心是离线处理
我们先定义next[i]表示i后面第一个与i颜色相同的位置
我们先考虑对于初始时处理询问区间[1..R]的情况,我们只对每个颜色第一个位置处赋值为1,其余赋值为0,那么答案就是区间和
当我们把左端点推进的时候,比如[2..R],其实我们只是舍掉了第一位的颜色,那么很明显把next[i]的位置赋值从0改成1即可,询问依然是区间和
这个部分我们需要支持区间查询,和单点修改即可,线段树/树状数组均可,这道题只写了线段树的版本(因为我已经不会树状数组了QAQAQ)

varz:array[0..1000006]of longint;t,x,b:array[0..50005]of longint;y:array[0..200005,1..4]of longint;w:array[0..300000,1..3]of longint;i,j,k:longint;n,m:longint;
procedure sort(l,r,tt:longint);
var i,j,a,b,c,k:longint;
begini:=l; j:=r; if tt=1 then begin a:=y[(l+r) div 2,1]; c:=y[(l+r)div 2,2]; end else a:=y[(l+r)>>1,3];repeatif tt=1 then beginwhile (y[i,1]<a)or((y[i,1]=a)and(y[i,2]<c)) do inc(i);while (a<y[j,1])or((y[j,1]=a)and(y[j,2]>c)) do dec(j);endelse beginwhile y[i,3]<a do inc(i);while y[j,3]>a do dec(j);end;if not(i>j) thenbeginfor k:=1 to 4 dobegin b:=y[i,k]; y[i,k]:=y[j,k]; y[j,k]:=b; end;inc(i); dec(j);end;until i>j;if l<j then sort(l,j,tt);if i<r then sort(i,r,tt);
end;procedure build(a,l,r:longint);
var mid:longint;
beginw[a,1]:=l; w[a,2]:=r;if l=r then begin w[a,3]:=b[l]; exit; end;mid:=(l+r)>>1;build(a<<1,l,mid); build(a<<1+1,mid+1,r);w[a,3]:=w[a<<1,3]+w[a<<1+1,3];
end;function query(a,l,r:longint):longint;
var mid:longint;
beginif (w[a,1]=l)and(w[a,2]=r) then exit(w[a,3]);mid:=(w[a,1]+w[a,2])>>1;if r<=mid then exit(query(a<<1,l,r)) elseif l>mid then exit(query(a<<1+1,l,r))else exit(query(a<<1,l,mid)+query(a<<1+1,mid+1,r));
end;procedure update(a,l:longint);
var mid:longint;
beginif (w[a,1]=w[a,2])and(w[a,1]=l) then begin b[l]:=1; w[a,3]:=1; exit; end;mid:=(w[a,1]+w[a,2])>>1;if l<=mid then update(a<<1,l) else update(a<<1+1,l);inc(w[a,3]);
end;beginreadln(n);for i:=1 to n dobegin read(x[i]); inc(x[i]); t[z[x[i]]]:=i; if z[x[i]]=0 then b[i]:=1 else b[i]:=0; z[x[i]]:=i; end;readln(m);for i:=1 to m dobegin readln(y[i,1],y[i,2]); y[i,3]:=i; end;sort(1,m,1); {y[i,1],y[i,2]}build(1,1,n);y[0,1]:=1;for i:=1 to m dobeginif y[i,1]<>y[i-1,1] thenfor j:=y[i-1,1] to y[i,1]-1 doif t[j]<>0 then update(1,t[j]);y[i,4]:=query(1,y[i,1],y[i,2]);end;sort(1,m,2); {y[i,3]}for i:=1 to m dowriteln(y[i,4]);
end.