Luogu 1972

题目分析：

将询问区间以$r$升序排序对于要查寻区间，我们利用滑动窗口思想$动态维护这一区间$

Code：

#include <bits/stdc++.h> using namespace std; #define maxn 510000 #define maxm 510000 #define mid ((l+r)>>1) #define lson l,mid,nod<<1 #define rson mid+1,r,nod<<1|1 int ans[maxm],m,n,a[maxn],vis[1000100],tr[maxn<<2],la[maxn<<2]; struct node { int l,r,id; }e[maxm]; inline void init_() { freopen("a.txt","r",stdin); } inline int read_() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=(x<<3)+(x<<1)+c-'0'; c=getchar(); } return x*f; } inline void clean_() { memset(tr,0,sizeof(tr)); memset(la,0,sizeof(la)); } bool cmp_(node aa,node bb) { if(aa.r==bb.r) return aa.l<bb.l; return aa.r<bb.r; } inline void xiugai_(int l,int r,int nod,int v) { tr[nod]+=(r-l+1)*v; la[nod]+=v; } void pushdown_(int l,int r,int nod) { if(!la[nod]) return; xiugai_(lson,la[nod]); xiugai_(rson,la[nod]); la[nod]=0; } inline void pushup_(int nod) { tr[nod]=tr[nod<<1]+tr[nod<<1|1]; } void update_(int l,int r,int nod,int LL,int RR,int v) { if(LL<=l&&RR>=r) { xiugai_(l,r,nod,v); return; } pushdown_(l,r,nod); if(LL<=mid) update_(lson,LL,RR,v); if(RR>mid) update_(rson,LL,RR,v); pushup_(nod); } int query_(int l,int r,int nod,int LL,int RR) { if(LL<=l&&RR>=r) return tr[nod]; pushdown_(l,r,nod); int sum=0; if(LL<=mid) sum+=query_(lson,LL,RR); if(RR>mid) sum+=query_(rson,LL,RR); return sum; } void readda_() { clean_(); n=read_(); for(int i=1;i<=n;++i) a[i]=read_(); m=read_(); for(int i=1;i<=m;++i) { e[i].l=read_();e[i].r=read_();e[i].id=i; } sort(e+1,e+m+1,cmp_); int last=1; for(int i=1;i<=m;++i) { for(int j=last;j<=e[i].r;++j) { if(vis[a[j]]) { update_(1,n,1,vis[a[j]],vis[a[j]],-1); } update_(1,n,1,j,j,1); vis[a[j]]=j; } last=e[i].r+1; ans[e[i].id]=query_(1,n,1,e[i].l,e[i].r); } for(int i=1;i<=m;++i) printf("%d\n",ans[i]); } int main() { init_(); readda_(); return 0; }