DQUERY - D-query
Tác giả: hieult
Ngôn ngữ: C++
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
//#include <conio.h>
#define ep 0.00001
#define oo 1000000
double const PI=4*atan(1);
using namespace std;
struct t_query{
int order,from,to;
t_query(){};
t_query(int order1,int from1, int to1){
order = order1;
from = from1;
to = to1;
}
bool operator<(const t_query& t) const {
return to < t.to;
}
};
int n,a[311111],d,f[1111111],norm,present[1<<20],KQ[211111];
t_query q[211111];
void init_present(){
for(norm =1;norm<n;norm*=2);
}
void add(int u){
for(int i = norm+u;i;i/=2) present[i]++;
}
void remove(int u){
for(int i = norm+u;i;i/=2) present[i]--;
}
int count(int u){
int kq = 0,root = 1,size = norm;
if(u>=size) return present[1];
while(true){
if(u == 0) return kq;
if(u<size/2) root*=2;
else if(u==size/2) return kq+present[2*root];
else{
kq+=present[2*root];
u -= size/2;
root=2*root+1;
}
size/=2;
}
}
int main(){
// freopen("DQUERY.in","r",stdin);
int x,y;
scanf("%d",&n);
for(int i = 0;i<n;i++) scanf("%d",&a[i]);
scanf("%d",&d);
for(int i = 0;i<d;i++){
scanf("%d %d",&x,&y);
q[i] = t_query(i,x-1,y-1);
}
sort(q,q+d);
init_present();
x = -1;
for(int i = 0;i<d;i++){
//printf("%d\n",i);
while(x<q[i].to){
x++;
if(f[a[x]]) remove(f[a[x]]-1);
add(x);
f[a[x]] = x+1;
}
KQ[q[i].order] = present[1]-count(q[i].from);
// printf("%d %d\n",i,q[i].order);
}
for(int i = 0;i<d;i++) printf("%d\n",KQ[i]);
// getch();
}