Editorial for K-query

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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

const fi='';
      maxn=30010;
      maxq=200010;
var n,q:longint;
    a,e,f:array[0..maxn] of longint;
    b,c,k,d,re:array[0..maxq] of longint;

procedure sort(l,r:longint);
var i,j,x,y:longint;
begin
     i:=l; j:=r; x:=a[(i+j) shr 1];
     repeat
            while a[i]>x do i:=i+1;
            while a[j]<x do j:=j-1;
            if i<=j then
            begin
                 y:=a[i]; a[i]:=a[j]; a[j]:=y;
                 y:=e[i]; e[i]:=e[j]; e[j]:=y;
                 i:=i+1; j:=j-1;
            end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

procedure sortt(l,r:longint);
var i,x,j,y:longint;
begin
     i:=l; j:=r; x:=k[(i+j) shr 1];
     repeat
           while k[i]>x do i:=i+1;
           while k[j]<x do j:=j-1;
           if i<=j then
           begin
                y:=k[i]; k[i]:=k[j]; k[j]:=y;
                y:=b[i]; b[i]:=b[j]; b[j]:=y;
                y:=c[i]; c[i]:=c[j]; c[j]:=y;
                y:=d[i]; d[i]:=d[j]; d[j]:=y;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sortt(i,r);
     if l<j then sortt(l,j);
end;

procedure rf;
var i:longint;
begin
     read(n);
     for i:=1 to n do
     begin
          read(a[i]); e[i]:=i;
     end;
     read(q);
     for i:=1 to q do
     begin
          read(b[i],c[i],k[i]);
          d[i]:=i;
     end;
     sort(1,n);
     sortt(1,q);
end;

procedure add(x:longint);
begin
     while x<=n do
     begin
          f[x]:=f[x]+1;
          x:=x+x and (-x);
     end;
end;

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

procedure pr;
var i,j:longint;
begin
     i:=1;
     for j:=1 to q do
     begin
          while (i<=n) and (a[i]>k[j]) do
          begin
               add(e[i]);
               i:=i+1;
          end;
          re[d[j]]:=calc(c[j])-calc(b[j]-1);
     end;
     for j:=1 to q do writeln(re[j]);
end;

begin
     assign(input,fi); reset(input);
     rf;
     pr;
     close(input);
end.

Code mẫu của happyboy99x

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

const int N = 30000+7, Q = 200000+7;
struct Query {
    int u, v, k, id;
    bool operator < (const Query &q) const {
        return k < q.k;
    }
};

int ans[Q], n, q, bit[N];
pair<int, int> a[N];
Query query[Q];

void enter() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i].first);
        a[i].second = i;
    }
    scanf("%d", &q);
    for(int i = 1; i <= q; ++i) {
        Query &q = query[i];
        scanf("%d%d%d", &q.u, &q.v, &q.k);
        q.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(query+1, query+q+1);
    sort(a+1, a+n+1); int pos = n;
    for(int i = q; i >= 1; --i) {
        Query &q = query[i];
        while(a[pos].first > q.k)
            increase(a[pos--].second);
        ans[q.id] = sum(q.v) - sum(q.u - 1);
    }
}

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

program kquery;
uses    math;
type    e=record
        v,p:longint;
        end;
        query=record
        i,j,k,p:longint;
        end;
const   maxn=30004;
        maxq=200005;
        fi='';
var     a:array[1..maxn] of e;
        q:array[1..maxq] of query;
        res,bit:array[1..maxq] of longint;
        n,qq:longint;

procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);reset(inp);
        readln(inp,n);
        for i:=1 to n do
        begin
                read(inp,a[i].v);
                a[i].p:=i;
        end;
        readln(inp,qq);
        for i:=1 to qq do
        begin
               readln(inp,q[i].i,q[i].j,q[i].k);
               q[i].p:=i;
        end;
        close(inp);
end;

procedure sortA(l,r:longint);
var     p,t:e;
        i,j:longint;
begin
        if l>=r then exit;
        i:=l;j:=r;
        p:=a[random(r-l+1)+l];
        repeat
                while a[i].v>p.v do inc(i);
                while a[j].v<p.v do dec(j);
                if i<=j then
                begin
                        if i<j then
                        begin
                                t:=a[i];
                                a[i]:=a[j];
                                a[j]:=t;
                        end;
                        inc(i);dec(j);
                end;
        until i>j;
        sortA(l,j);sortA(i,r);
end;

procedure sortQ(l,r:longint);
var     p,t:query;
        i,j:longint;
begin
        if l>=r then exit;
        i:=l;j:=r;
        p:=q[random(r-l+1)+l];
        repeat
                while q[i].k>p.k do inc(i);
                while q[j].k<p.k do dec(j);
                if i<=j then
                begin
                        if i<j then
                        begin
                                t:=q[i];
                                q[i]:=q[j];
                                q[j]:=t;
                        end;
                        inc(i);dec(j);
                end;
        until i>j;
        sortQ(l,j);sortQ(i,r);
end;

procedure update(i:longint);
begin
        while i<=n do
        begin
                inc(bit[i]);
                i:=i+i and (-i);
        end;
end;

function get(i:longint):longint;
var     sum:longint;
begin
        sum:=0;
        if i=0 then exit(0);
        while i>0 do
        begin
                inc(sum,bit[i]);
                i:=i-i and (-i);
        end;
        exit(sum);
end;

procedure process;
var     i,j:longint;
begin
        j:=1;//a[0].v:=high(longint);
        for i:=1 to qq do
        begin
                while (j<=n) and (a[j].v>q[i].k) do
                begin
                        update(a[j].p);
                        inc(j);
                end;
                res[q[i].p]:=get(q[i].j)-get(q[i].i-1);
        end;
end;

procedure output;
var     i:longint;
begin
        for i:=1 to qq do
        writeln(res[i]);
end;

begin
        input;
        sortA(1,n);
        sortQ(1,qq);
        process;
        output;
end.

Code mẫu của RR

//Wishing myself a happy lunar new year with a lot of accept solutions
//Written by Nguyen Thanh Trung
{$R-,Q-}
const
  FINP='';
  FOUT='';
  MAXN=30000;
  MAXQ=200000;
var
  count,ind:array[1..MAXN] of integer;
  a:array[1..MAXN] of longint;
  n,q:longint;
  inq,k:array[1..MAXQ] of longint;
  x,y,kq:array[1..MAXQ] of integer;
procedure inp; inline;
var
  f:text;
  i:longint;
begin
  assign(f,FINP); reset(f);
  read(f,n);
  for i:=1 to n do read(f,a[i]);
  for i:=1 to n do ind[i]:=i;
  read(f,q);
  for i:=1 to q do read(f,x[i],y[i],k[i]);
  for i:=1 to q do inq[i]:=i;
  close(f);
end;
procedure ans; inline;
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:integer); inline;
var
  temp:integer;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure swap2(var a,b:longint); inline;
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
var mid:longint;
procedure sortA(l,r:longint); inline;
var
  i,j:longint;
begin
  i:=l; j:=r; mid:=a[l+random(r-l+1)];
  repeat
    while a[i]<mid do inc(i);
    while a[j]>mid do dec(j);
    if i<=j then
      begin
        swap2(a[i],a[j]);
        swap(ind[i],ind[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sortA(i,r);
  if l<j then sortA(l,j);
end;
procedure sortQ(l,r:longint); inline;
var
  i,j:longint;
begin
  i:=l; j:=r; mid:=k[l+random(r-l+1)];
  repeat
    while k[i]<mid do inc(i);
    while k[j]>mid do dec(j);
    if i<=j then
      begin
        swap2(k[i],k[j]);
        swap(x[i],x[j]);
        swap(y[i],y[j]);
        swap2(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 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,now:longint;
begin
  sortA(1,n);
  sortQ(1,q);
  now:=n;
  for i:=q downto 1 do
    begin
      while (a[now]>k[i]) and (now>0) do
        begin
          update(ind[now]);
          dec(now);
        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<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>

using namespace std;

struct node{
     int gt,id;
};

struct query{
      int k,id,dau,cuoi;
};
int a[31111],n;
int f[31111];
int s[31111];
int KQ[211111];
node A[31111];
query Q[211111];

inline bool cmp(const node &a,const node &b){ return a.gt > b.gt;}
inline bool cmp2(const query &a, const query &b){ return a.id < b.id;}
inline bool cmp1(const query &a, const query &b){ return a.k > b.k;}

inline int count(int x){
     int kq = 0;
     while(x){
          kq+= a[x], x-=x&-x;
     }
     return kq;
} 

inline void update(int x,const int tang){
     while(x<=n){
          a[x]+=tang;
          x+=x&-x;
     }
}

int main(){
    // freopen("KQUERY.in","r",stdin);
     int so,a,b,c;
     scanf("%d",&n);
     for(int i = 1;i<=n;i++){
          scanf("%d",&a);
          A[i].gt = a;
          A[i].id = i;
     }
     scanf("%d",&so);
     for(int i = 1;i<=so;i++){
          scanf("%d %d %d",&a,&b,&c);
          Q[i].dau = a;
          Q[i].cuoi = b;
          Q[i].k = c;
          Q[i].id = i;
          KQ[i] = b-a+1;
     }
     sort(A+1,A+n+1,cmp);
     sort(Q+1,Q+so+1,cmp1);
     int st = 1;
     for(int i = 1;i<=so && st<=n;){
          if(st<=n && Q[i].k<A[st].gt){
                update(A[st].id,1);
                ++st;
          }
          else{
                KQ[Q[i].id] = count(Q[i].cuoi) - count(Q[i].dau-1);
                ++i;
          }
     }
     for(int i = 1;i<=so;i++) printf("%d\n",KQ[i]);
    // getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
{$inline on}
program KQUERY;
const
  input  = '';
  output = '';
  maxn = 30000;
  maxk = 200010;
type
  pnode =^tnode;
  tnode = record
    val: integer;
    next: pnode;
  end;
var
  a,b,pos,num: array[1..maxn + maxk] of integer;
  p,res: array[1..2 * maxk] of integer;
  link: array[1..maxn] of pnode;
  n,k: integer;

procedure init;inline;
var
  f: text;
  i: integer;
begin
  assign(f, input);
    reset(f);

  readln(f, n);
  for i := 1 to n do
    begin
      read(f, b[i]);
      pos[i] := i;
    end;

  readln(f, k);
  for i := 1 to k do
    begin
      read(f, p[2 * i], p[2 * i + 1], b[n + i]);
      pos[n + i] := n + i;
    end;

  close(f);
end;

procedure swap(var x,y: integer);inline;
var
  z: integer;
begin
  z := x;  x := y;  y := z;
end;

procedure swapint(i,j: integer);inline;
begin
  swap(b[i],b[j]);
  swap(pos[i],pos[j]);
end;

procedure quicksort;inline;

  procedure partition(l,h: integer);inline;
  var
    i,j,pivot: integer;
  begin
    if l >= h then exit;
    i := l;  j := h;  pivot := b[random(h - l + 1) + l];

    repeat
      while b[i] < pivot do inc(i);
      while b[j] > pivot do dec(j);

      if i <= j then
        begin
          if i < j then swapint(i,j);
          inc(i);
          dec(j);
        end;
    until i > j;

    partition(l,j);
    partition(i,h);
  end;

var
  i,c: integer;
begin
  partition(1,n + k);
  c := 1;
  a[pos[1]] := 1;

  for i := 2 to n + k do
    begin
      if b[i] > b[i - 1] then inc(c);
      a[pos[i]] := c;
    end;
end;

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

procedure process;inline;
var
  i: integer;
begin
  for i := 1 to n do link[i] := nil;
  for i := 1 to k do
    begin
      add(p[2 * i] - 1, 2 * i);
      add(p[2 * i + 1], 2 * i + 1);
    end;
end;

procedure update(x: integer);inline;
begin
  while x > 0 do
    begin
      inc(num[x]);
      x := x - (x and -x);
    end;
end;

function calc(x: integer): integer;inline;
var
  r: integer;
begin
  r := 0;
  while x <= maxn + maxk do
    begin
      r := r + num[x];
      x := x + (x and -x);
    end;
  calc := r;
end;

procedure query;inline;
var
  f: text;
  i,tmp: integer;
  q: pnode;
begin
  fillchar(num, sizeof(num), 0);
  for i := 1 to n do
    begin
      update(a[i] - 1);
      q := link[i];
      while q <> nil do
        begin
          tmp := q^.val;
          res[tmp] := calc(a[n + tmp div 2]);
          q := q^.next;
        end;
    end;

  assign(f, output);
    rewrite(f);
    for i := 1 to k do writeln(f, res[2 * i + 1] - res[2 * i]);
  close(f);
end;

begin
  init;
  quicksort;
  process;
  query;
end.

Code mẫu của skyvn97

#include<stdio.h>
#include<algorithm>
#define MAXN   30303
#define MAXQ   200200
#define x   first
#define y   second
using namespace std;
typedef pair<int,int> ii;
struct quest {
    int f,l,v,t;
};
bool cmpq(const quest &y,const quest &x) {
        if (y.v>x.v) return (true);
        if (y.v<x.v) return (false);
        if (y.t<x.t) return (true);
        if (y.t>x.t) return (false);
        if (y.f<x.f) return (true);
        if (y.f>x.f) return (false);
        return (y.l<x.l);
}
quest q[MAXQ];
ii a[MAXN];
int p[MAXN];
int b[MAXN];
int r[MAXQ];
int n,m;
void init(void) {
    scanf("%d",&n);
    int i,j;
    for (i=1;i<=n;i=i+1) {
        scanf("%d",&j);
        a[i]=ii(-j,i);
    }
    sort(&a[1],&a[n+1]);
    for (i=1;i<=n;i=i+1) {
        a[i].x=-a[i].x;
        b[i]=0;
        p[i]=i+(i&(-i));
    }
    scanf("%d",&m);
    for (i=1;i<=m;i=i+1) {
        scanf("%d",&q[i].f);
        scanf("%d",&q[i].l);
        scanf("%d",&q[i].v);
        q[i].t=i;
    }
    sort(&q[1],&q[m+1],cmpq);
}
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].x>q[i].v)) {
            update(a[j].y);
            j=j+1;
        }
        r[q[i].t]=sum(q[i].l)-sum(q[i].f-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, a : array[1..30000] 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(a[i]);
    ind[i] := i;
  end;

  read(q);
  for i:=1 to q do
  begin
      read(ai[i], aj[i], ak[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.

Comments

Please read the guidelines before commenting.