DQUERY - D-query
Tác giả: skyvn97
Ngôn ngữ: C++
#include<stdio.h>
#include<algorithm>
#define MAXN 30303
#define MAXQ 200200
#define MAXV 1010101
#define x first
#define y second
using namespace std;
typedef pair<int,int> ii;
typedef pair<ii,int> pii;
pii a[MAXN];
pii q[MAXQ];
int v[MAXV];
int p[MAXN];
int b[MAXN];
int r[MAXQ];
int m,n;
bool cmpa(const pii &a,const pii &b) {
if (a.y>b.y) return (true);
if (a.y<b.y) return (false);
return (a.x<b.x);
}
bool cmpq(const pii &a,const pii &b) {
if (a.x.x>b.x.x) return (true);
if (a.x.x<b.x.x) return (false);
if (a.x.y>b.x.y) return (true);
if (a.x.y<b.x.y) return (false);
return (a.y<b.y);
}
void init(void) {
int i,u,t;
for (i=0;i<MAXV;i=i+1) v[i]=-1;
scanf("%d",&n);
for (i=1;i<=n;i=i+1) {
scanf("%d",&u);
a[i]=pii(ii(u,i),v[u]);
v[u]=i;
}
scanf("%d",&m);
for (i=1;i<=m;i=i+1) {
scanf("%d",&u);
scanf("%d",&t);
q[i]=pii(ii(u,t),i);
}
sort(&a[1],&a[n+1],cmpa);
sort(&q[1],&q[m+1],cmpq);
for (i=1;i<=n;i=i+1) {
b[i]=0;
p[i]=i+(i&(-i));
}
}
void update(int x) {
while ((x>0) && (x<n+1)) {
b[x]=b[x]+1;
x=p[x];
}
}
int sum(int x) {
int s=0;
while ((x>0) && (x<n+1)) {
s=s+b[x];
x=x&(x-1);
}
return (s);
}
void process(void) {
int i,j;
j=1;
for (i=1;i<=m;i=i+1) {
while ((j<=n) && (a[j].y>=q[i].x.x)) {
update(a[j].x.y);
j=j+1;
}
r[q[i].y]=(q[i].x.y-q[i].x.x+1)-(sum(q[i].x.y)-sum(q[i].x.x-1));
}
for (i=1;i<=m;i=i+1) printf("%d\n",r[i]);
}
int main(void) {
init();
process();
return 0;
}