【洛谷P1972】HH的项链 离线+树状数组

时间:2021-09-02 01:33:34

题目大意:静态查询序列区间颜色数。

题解:对于一个查询区间 [l , r] ,若有两个相同颜色的点在这个区间中,则总是取下标靠近端点 r 的颜色计入答案贡献。对于每个下标,记录下在这个下标之前,且距离当前下标最近的,且与这个下标对应的颜色相同的下标是多少,即:\(min\{j,j<i\&\&cor[j]=cor[i] \}\)。由于每个序列右端点结束后即可统计答案,因此对所有询问的右端点进行从小到大排序,并从左到右扫一遍序列,用树状数组维护当前序列中对 [1 , idx] 颜色有贡献的点的下标,每次扫描到一个点 idx 时,根据最开始提到的操作,用这个点的颜色替换离这个点最近的相同颜色的点,最后统计答案即可。可知在扫描的过程中 i 和 j 一共迭代了 n+m 次,因此时间复杂度为 \(O((n+m)logn)\)。

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+10; inline int read(){
int x=0,f=1;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));
do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));
return f*x;
} int n,m,pre[maxn],h[maxn<<1],t[maxn],ans[maxn];
struct rec{int l,r,id;}q[maxn];
bool cmp(const rec &x,const rec &y){return x.r<y.r;}
inline int lowbit(int x){return x&-x;}
void modify(int pos,int val){
if(!pos)return;
for(int i=pos;i<=n;i+=lowbit(i))t[i]+=val;
}
int query(int pos){
int res=0;
for(int i=pos;i;i-=lowbit(i))res+=t[i];
return res;
} void read_and_parse(){
n=read();
for(int i=1,x;i<=n;i++){
x=read();
pre[i]=h[x],h[x]=i;
}
m=read();
for(int i=1;i<=m;i++)q[i].l=read(),q[i].r=read(),q[i].id=i;
sort(q+1,q+m+1,cmp);
} void solve(){
int j=1;
for(int i=1;i<=m;i++){
for(;j<=q[i].r;j++)modify(pre[j],-1),modify(j,1);
ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
}
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
} int main(){
read_and_parse();
solve();
return 0;
}