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

Download