Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

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

Code mẫu của happyboy99x

#include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;

const int N = 30007, Q = 200007, MAX = 1000007;

int n, q, ans[Q], last[MAX], bit[N];
struct query {
    int u, v, id;
    bool operator < (const query &q) const {
        return u < q.u;
    }
} qry[Q];
pair<int, int> a[N];

void enter() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        int x; scanf("%d", &x);
        a[i] = make_pair(last[x], i);
        last[x] = i;
    }
    scanf("%d", &q);
    for(int i = 1; i <= q; ++i) {
        scanf("%d%d", &qry[i].u, &qry[i].v);
        qry[i].id = i;
    }
}

void increase(int v) {
    for(; v <= n; v += v & -v) ++bit[v];
}

int sum(int v) {
    int res = 0;
    for(; v != 0; v -= v & -v) res += bit[v];
    return res;
}

void solve() {
    sort(qry+1, qry+q+1);
    sort(a+1, a+n+1); int p = n;
    for(int i = q; i >= 1; --i) {
        query &Q = qry[i];
        while(a[p].first >= Q.u) increase(a[p--].second);
        ans[Q.id] = (Q.v - Q.u + 1) - (sum(Q.v) - sum(Q.u));
    }
}

void print() {
    for(int i = 1; i <= q; ++i)
        printf("%d\n", ans[i]);
}

int main() {
    enter();
    solve();
    print();
    return 0;
}

Code mẫu của ladpro98

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 30003;

struct Node {
    int l, r;
    int sum;
    Node *L, *R;

    Node(int l, int r) {
        this->l = l; this->r = r;
        sum = 0;
        L = R = nullptr;
    }

    Node* update(int i) {
        Node* cur = new Node(l, r);
        if (l == r) {
            cur->sum = sum + 1;
        } else {
            if (i <= (l + r >> 1)) {
                cur->L = L->update(i);
                cur->R = R;
            } else {
                cur->R = R->update(i);
                cur->L = L;
            }
            cur->sum = cur->L->sum + cur->R->sum;
        }
        return cur;
    }

    int getPrefixSum(int i) {
        if (i < l) return 0;
        if (r <= i) return sum;
        return L->getPrefixSum(i) + R->getPrefixSum(i);
    }
};

Node* build(int i, int j) {
    Node* cur = new Node(i, j);
    if (i != j) {
        cur->L = build(i, i + j >> 1);
        cur->R = build((i + j >> 1) + 1, j);
    }
    return cur;
}

void compress(int a[], int n) {
    vector<int> b (a + 1, a + 1 + n);
    sort(begin(b), end(b));
    b.resize(unique(begin(b), end(b)) - begin(b));
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(begin(b), end(b), a[i]) - begin(b) + 1;
}


int a[N];
int last[N];
Node* root[N];

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);

    int n; cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    compress(a, n);

    for (int i = 1; i <= n; ++i) last[a[i]] = n + 1;
    root[n + 1] = build(1, n + 1);
    for (int i = n; i >= 1; --i) {
        root[i] = root[i + 1]->update(last[a[i]]);
        last[a[i]] = i;
    }

    int q; cin >> q;
    while (q--) {
        int i, j; cin >> i >> j;
        cout << (j - i + 1) - root[i]->getPrefixSum(j) << '\n';
    }
    return 0;
}

Code mẫu của RR

{$R+,Q+}
const
  FINP='';
  FOUT='';
  MAXN=30011;
  MAXQ=200011;
var
  n,q:longint;
  ind,a,pre,count:array[0..MAXN] of longint;
  now:array[1..1000000] of longint;
  inq,kq,x,y:array[0..MAXQ] of longint;
procedure inp;
var
  f:text;
  i:longint;
begin
  assign(f,FINP); reset(f);
  read(f,n);
  for i:=1 to n do read(f,a[i]);
  read(f,q);
  for i:=1 to q do read(f,x[i],y[i]);
  close(f);
end;
procedure ans;
var
  f:text;
  i:longint;
begin
  assign(f,FOUT); rewrite(f);
  for i:=1 to q do
    writeln(f,kq[i]);
  close(f);
end;
procedure swap(var a,b:longint); inline;
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
var mid,mid2:longint;
procedure sortQ(l,r:longint); inline;
var
  i,j:longint;
begin
  i:=l; j:=r;
  mid:=x[l+random(r-l+1)];
  repeat
    while x[i]<mid do inc(i);
    while x[j]>mid do dec(j);
    if i<=j then
      begin
        swap(x[i],x[j]);
        swap(y[i],y[j]);
        swap(inq[i],inq[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sortQ(i,r);
  if l<j then sortQ(l,j);
end;
procedure sortD(l,r:longint); inline;
var
  i,j:longint;
begin
  i:=l; j:=r; mid:=pre[l+random(r-l+1)];
  repeat
    while pre[i]<mid do inc(i);
    while pre[j]>mid do dec(j);
    if i<=j then
      begin
        swap(pre[i],pre[j]);
        swap(ind[i],ind[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sortD(i,r);
  if l<j then sortD(l,j);
end;
procedure update(u:longint); inline;
var
  v:longint;
begin
  inc(count[u]);
  v:=u+u and (-u);
  if v<=n then update(v);
end;
function get(u:longint):longint; inline;
var
  v,kq:longint;
begin
  if u=0 then exit(0);
  kq:=count[u];
  v:=u-u and (-u);
  if v>0 then inc(kq,get(v));
  get:=kq;
end;
procedure solve;
var
  i,luu:longint;
begin
  for i:=1 to q do inq[i]:=i;
  sortQ(1,q);
  now[a[1]]:=1;
  for i:=2 to n do
    begin
      pre[i]:=now[a[i]];
      now[a[i]]:=i;
    end;
  for i:=1 to n do ind[i]:=i;
  sortD(1,n);

  luu:=1; pre[n+1]:=MAXN+1;
  for i:=1 to q do
    begin
      while (pre[luu]<x[i]) do
        begin
          update(ind[luu]);
          inc(luu);
        end;
      kq[inq[i]]:=get(y[i])-get(x[i]-1);
    end;
end;
begin
  inp;
  solve;
  ans;
end.

Code mẫu của hieult

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

Code mẫu của ll931110

{$MODE DELPHI}
program DQUERY;
const
  input  = '';
  output = '';
  maxn = 30010;
  maxk = 200010;
  maxv = 1000000;
type
  pnode = ^tnode;
  tnode = record
    val: integer;
    next: pnode;
  end;
var
  p,res: array[1..2 * maxk] of integer;
  v: array[1..maxv] of integer;
  a,t: array[1..maxn] of integer;
  link: array[1..maxn] of pnode;
  n,k: integer;
  fi,fo: text;

// Analyze: Create new array {s} satisfying
// s[i] = max j | (j < i) and (s[j] = s[i]). s[i] = 0 if there doesn't exist j
// Using KQUERY: query(i,j) equals to the number of integers in the subsequence [i,j] which is less than i

procedure openfile;
begin
  assign(fi, input);
    reset(fi);

  assign(fo, output);
    rewrite(fo);
end;

procedure add(i,x: integer);
var
  q: pnode;
begin
  if i = 0 then exit;
  new(q);
  q^.val := x;
  q^.next := link[i];
  link[i] := q;
end;

procedure init;
var
  i,num: integer;
begin
  readln(fi, n);
  fillchar(v, sizeof(v), 0);
  for i := 1 to n do
    begin
      read(fi, num);
      a[i] := v[num];
      v[num] := i;
    end;

  readln(fi, k);
  for i := 1 to k do
    begin
      read(fi, p[2 * i]);
      add(p[2 * i] - 1,2 * i);

      read(fi, p[2 * i + 1]);
      add(p[2 * i + 1],2 * i + 1);

      v[i] := p[2 * i];
    end;

end;

// BIT operations

procedure update(x: integer);
begin
  while x <= maxn do
    begin
      inc(t[x]);
      x := x + (x and -x);
    end;
end;

function calc(x: integer): integer;
var
  r: integer;
begin
  r := 0;
  while x > 0 do
    begin
      r := r + t[x];
      x := x - (x and -x);
    end;
  calc := r;
end;

// End of BIT operations

procedure solve;
var
  i,tmp: integer;
  s: pnode;
begin
  fillchar(t, sizeof(t), 0);
  fillchar(res, sizeof(res), 0);

  for i := 1 to n do
    begin
      update(a[i] + 1);
      s := link[i];
      while s <> nil do
        begin
          tmp := s^.val;
          res[tmp] := calc(v[tmp div 2]);
          s := s^.next;
        end;
    end;

  for i := 1 to k do writeln(fo, res[2 * i + 1] - res[2 * i]);
end;

procedure closefile;
begin
  close(fo);
  close(fi);
end;

begin
  openfile;
  init;
  solve;
  closefile;
end.

Code mẫu của skyvn97

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

Code mẫu của khuc_tuan

//{$APPTYPE CONSOLE}
{$mode delphi}

type
  integer = longint;

var
  n : integer;
  ind, value, a : array[1..30000] of integer;
  pos : array[1..1000000] of integer;

  q : integer;
  oo, aind, ai, aj, ak : array[1..200000] of integer;

  bit : array[1..30000] of integer;

procedure sort1(l,r : integer);
var
  x, t : integer;
  i, j : integer;
begin
    if l>=r then exit;
    i := l;
    j := r;
    x := ind[(l+r) div 2];
    repeat
      while a[ind[i]] > a[x] do inc(i);
      while a[ind[j]] < a[x] do dec(j);
      if i<=j then
      begin
          t := ind[i];
          ind[i] := ind[j];
          ind[j] := t;
          inc(i);
          dec(j);
      end;
    until i>j;
    sort1(i,r);
    sort1(l,j);
end;

procedure sort2(l,r : integer);
var
  i, j : integer;
  x, t : integer;
begin
  if l>r then exit;
  i := l;
  j := r;
  x := ak[(l+r) div 2];
  repeat
    while ak[i]>x do inc(i);
    while ak[j]<x do dec(j);
    if i<=j then
    begin
      t := ak[i]; ak[i] := ak[j]; ak[j] := t;
      t := ai[i]; ai[i] := ai[j]; ai[j] := t;
      t := aj[i]; aj[i] := aj[j]; aj[j] := t;
      t := aind[i]; aind[i] := aind[j]; aind[j] := t;
      inc(i);
      dec(j);
    end;
  until i>j;
  sort2(i,r);
  sort2(l,j);
end;

function getsum(i : integer) : integer;
var
  r : integer;
begin
    r := 0;
    while i>0 do
    begin
        inc(r, bit[i]);
        i := i and (i-1);
    end;
    getsum := r;
end;

var
  st, i, j : integer;

begin
  read(n);
  for i:=1 to n do
  begin
    read(value[i]);
    ind[i] := i;
  end;

  for i:=1 to 1000000 do pos[i] := n + 1;
  for i:=n downto 1 do
  begin
       a[i] := pos[value[i]];
       pos[value[i]] := i; 
  end;

  read(q);
  for i:=1 to q do
  begin
      read(ai[i], aj[i]);
      ak[i] := aj[i];
      aind[i] := i;
  end;

  sort1(1,n);

  sort2(1,q);

  st := 1;
  for i:=1 to q do
  begin
    while (st<=n) and (a[ind[st]]>ak[i]) do
    begin
        // update ind[st]
        j := ind[st];
        while j<=n do
        begin
             inc(bit[j]);
             inc(j, j and (-j));
        end;
        inc(st);
    end;

    oo[aind[i]] := getsum(aj[i]) - getsum(ai[i]-1);

  end;

  for i:=1 to q do writeln(oo[i]);

  // readln; readln; readln;
end.