DQUERY - D-query
Tác giả: flashmt
Ngôn ngữ: C++
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#define mn 30030
#define mq 200020
#define fr(a,b,c) for (a=b;a<=c;a++)
#define frr(a,b,c) for (a=b;a>=c;a--)
using namespace std;
int n,q,i,a[mn],d[1000010],b[mn],p[mn],f[mn],g[mq],h[mq],e[mq],re[mq];
void sort(int l,int r)
{
int i=l,j=r,x=b[(i+j)/2],t;
do
{
while (b[i]>x) i++;
while (b[j]<x) j--;
if (i<=j)
{
t=b[i]; b[i]=b[j]; b[j]=t;
t=p[i]; p[i]=p[j]; p[j]=t;
i++; j--;
}
} while (i<=j);
if (i<r) sort(i,r);
if (l<j) sort(l,j);
}
void sortt(int l,int r)
{
int i=l,j=r,x=h[(i+j)/2],t;
do
{
while (h[i]>x) i++;
while (h[j]<x) j--;
if (i<=j)
{
t=g[i]; g[i]=g[j]; g[j]=t;
t=h[i]; h[i]=h[j]; h[j]=t;
t=e[i]; e[i]=e[j]; e[j]=t;
i++; j--;
}
} while (i<=j);
if (i<r) sortt(i,r);
if (l<j) sortt(l,j);
}
void add(int x)
{
while (x<=n)
{
f[x]++;
x+=(x&-x);
}
}
int calc(int x)
{
int r=0;
while (x)
{
r+=f[x];
x-=(x&-x);
}
return r;
}
int main()
{
int cur=1;
cin >> n;
fr(i,1,n) scanf("%d",&a[i]);
frr(i,n,1)
{
if (!d[a[i]]) b[i]=n+1;
else b[i]=d[a[i]];
d[a[i]]=i;
p[i]=i;
}
cin >> q;
fr(i,1,q)
{
scanf("%d%d",&g[i],&h[i]);
e[i]=i;
}
sort(1,n);
sortt(1,q);
fr(i,1,q)
{
while (cur<=n && h[i]<b[cur])
{
add(p[cur]);
cur++;
}
re[e[i]]=calc(h[i])-calc(g[i]-1);
}
fr(i,1,q) printf("%d\n",re[i]);
return 0;
}