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.
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
cảm ơn mọi người đã chỉ ạ