## 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
for i:=1 to n do
begin
end;
for i:=1 to q do
begin
d[i]:=i;
end;
sort(1,n);
sortt(1,q);
end;

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


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);
for i:=1 to n do
begin
a[i].p:=i;
end;
for i:=1 to qq do
begin
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
{$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
for i:=1 to n do
begin
ind[i] := i;
end;

for i:=1 to q do
begin
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]);