原题为莫队,然而某网站扩大数据范围。
题解:离线树状数组,存入所有询问。按r从小到大排序。然后从1到n遍历,维护动态树状数组,记录之前某一点到该点的距离。
代码:
#include<cstdio> #include<algorithm> using namespace std; #define N 500005 int n,m,a[N]; struct ND { int x; int id; }nd[N]; struct Que { int l,r,id; }q[N]; bool cmp(ND a,ND b) { return a.x<b.x; } bool vmp(Que a,Que b) { return a.r<b.r; } int ans[N],f[N],last[N]; void up(int x,int d) { if(!x)return ; while(x<=500000) { f[x]+=d; x+=(x&(-x)); } } int down(int x) { if(!x)return 0; int ret = 0; while(x) { ret+=f[x]; x-=(x&(-x)); } return ret; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&nd[i].x); nd[i].id = i; } sort(nd+1,nd+1+n,cmp); int k=0,las=-1; for(int i=1;i<=n;i++) { if(las!=nd[i].x) { las=nd[i].x; k++; } a[nd[i].id]=k; } scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d",&q[i].l,&q[i].r); q[i].id=i; } sort(q+1,q+1+m,vmp); k = 1; for(int i=1;i<=n;i++) { up(i,1); if(last[a[i]])up(last[a[i]],-1); last[a[i]]=i; while(q[k].r==i) { ans[q[k].id]=down(i)-down(q[k].l-1); k++; } } for(int i=1;i<=m;i++) { printf("%d ",ans[i]); } return 0; }