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

Download