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();
}

Download