Editorial for Xếp hàng
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=''; fo=''; maxn=50000; var n,m,p,q,low,high,i:longint; a:array[1..maxn] of longint; min,max:array[1..maxn shl 2] of longint; function getmin(x,y:longint):longint; begin if x<y then getmin:=x else getmin:=y; end; function getmax(x,y:longint):longint; begin if x>y then getmax:=x else getmax:=y; end; procedure initmax(node,l,r:longint); var mid:longint; begin if l=r then max[node]:=a[l] else begin mid:=(l+r) shr 1; initmax(node shl 1,l,mid); initmax(node shl 1+1,mid+1,r); max[node]:=getmax(max[node shl 1],max[node shl 1+1]); end; end; procedure initmin(node,l,r:longint); var mid:longint; begin if l=r then min[node]:=a[l] else begin mid:=(l+r) shr 1; initmin(node shl 1,l,mid); initmin(node shl 1+1,mid+1,r); min[node]:=getmin(min[node shl 1],min[node shl 1+1]); end; end; procedure findmin(node,l,r,p,q:longint); var mid:longint; begin if (l=p) and (r=q) then low:=getmin(low,min[node]) else begin mid:=(l+r) shr 1; if p<=mid then findmin(node shl 1,l,mid,p,getmin(mid,q)); if q>mid then findmin(node shl 1+1,mid+1,r,getmax(mid+1,p),q); end; end; procedure findmax(node,l,r,p,q:longint); var mid:longint; begin if (l=p) and (r=q) then high:=getmax(high,max[node]) else begin mid:=(l+r) shr 1; if p<=mid then findmax(node shl 1,l,mid,p,getmin(mid,q)); if q>mid then findmax(node shl 1+1,mid+1,r,getmax(mid+1,p),q); end; end; begin assign(input,fi); reset(input); assign(output,fo); rewrite(output); readln(n,m); for i:=1 to n do readln(a[i]); initmin(1,1,n); initmax(1,1,n); for i:=1 to m do begin readln(p,q); low:=maxlongint; high:=-low; findmin(1,1,n,p,q); findmax(1,1,n,p,q); writeln(high-low); end; close(input); close(output); end.
Code mẫu của happyboy99x
#include <cstdio> #include <cmath> #define MAXN 50000+5 #define LOGMAXN 20 /*log 50000 ~ 16*/ int n, q; int a[MAXN]; int m[MAXN][LOGMAXN], mx[MAXN][LOGMAXN]; int min( int a, int b ) { return a < b ? a : b; } int max( int a, int b ) { return a>b?a:b; } void preprocess() { for( int i = 0; i < n; m[i][0] = mx[i][0] = i, ++i ); for( int j = 1; 1 << j <= n; ++j ) for( int i = 0; i + ( 1 << j ) - 1 < n; ++i ) { m[i][j] = a[m[i][j-1]] < a[m[i+(1<<j-1)][j-1]] ? m[i][j-1] : m[i+(1<<j-1)][j-1]; mx[i][j] = a[mx[i][j-1]] > a[mx[i+(1<<j-1)][j-1]] ? mx[i][j-1] : mx[i+(1<<(j-1))][j-1]; } } int main() { scanf( "%d%d", &n, &q ); for( int i = 0; i < n; scanf( "%d", &a[i++] ) ); preprocess(); for( int i = 0; i < q; ++i ) { int i, j, k; scanf( "%d%d", &i, &j ); --i; --j; k = (int) floor(log(j-i+1)/log(2)); printf("%d\n", max(a[mx[i][k]], a[mx[j-(1<<k)+1][k]]) - min(a[m[i][k]], a[m[j-(1<<k)+1][k]])); } return 0; }
Code mẫu của ladpro98
//http://vn.spoj.com/problems/NKLINEUP/ #include <bits/stdc++.h> #define ii pair<int, int> #define X first #define Y second #define mid (l + r >> 1) #define left k + k #define right left + 1 const int N = 50005; const int oo = 1000000000; using namespace std; int n, q; struct segment_tree { ii it[4 * N]; int n; segment_tree(int nn) {n = nn;} void Upd(int k, int l, int r, int i, int v) { if (l > r || i < l || r < i) return; if (l == r) {it[k].X = it[k].Y = v; return;} Upd(left, l, mid, i, v); Upd(right, mid + 1, r, i, v); it[k].X = max(it[left].X, it[right].X); it[k].Y = min(it[left].Y, it[right].Y); } ii Get(int k, int l, int r, int i, int j) { if (l > r || r < i || j < l) return ii(0, oo); if (i <= l && r <= j) return it[k]; ii ll = Get(left, l, mid, i, j), rr = Get(right, mid + 1, r, i, j); return ii(max(ll.X, rr.X), min(ll.Y, rr.Y)); } void Upd(int i, int v) {Upd(1, 1, n, i, v);} ii Get(int i, int j) {return Get(1, 1, n, i, j);} }; int main() { scanf("%d %d", &n, &q); int i, x, l, r; ii res; segment_tree IT (n); for(int i = 1; i <= n; i++) {scanf("%d", &x); IT.Upd(i, x);} while (q--) { scanf("%d %d", &l, &r); res = IT.Get(l, r); printf("%d\n", res.X - res.Y); } return 0; }
Code mẫu của RR
uses math; var a:array[1..50111] of longint; ln,nn:array[1..131072] of longint; n,q,i,u,v:longint; procedure init(i,l,r:longint); var mid:longint; begin if l=r then begin ln[i]:=a[l]; nn[i]:=a[l]; exit; end; mid:=(l+r) shr 1; init(i shl 1,l,mid); init(i shl 1+1,mid+1,r); ln[i]:=max(ln[i shl 1],ln[i shl 1+1]); nn[i]:=min(nn[i shl 1],nn[i shl 1+1]); end; function getMax(i,l,r,u,v:longint):longint; var mid:longint; begin if (v<l) or (r<u) then exit(-1); if (u<=l) and (r<=v) then exit(ln[i]); mid:=(l+r) shr 1; exit(max(getMax(i shl 1,l,mid,u,v), getMax(i shl 1+1,mid+1,r,u,v))); end; function getMin(i,l,r,u,v:longint):longint; var mid:longint; begin if (v<l) or (r<u) then exit(1000111); if (u<=l) and (r<=v) then exit(nn[i]); mid:=(l+r) shr 1; exit(min(getMin(i shl 1,l,mid,u,v), getMin(i shl 1+1,mid+1,r,u,v))); end; begin read(n,q); for i:=1 to n do read(a[i]); init(1,1,n); for i:=1 to q do begin read(u,v); writeln(getMax(1,1,n,u,v)-getMin(1,1,n,u,v)); end; end.
Code mẫu của hieult
#include <stdio.h> #include <algorithm> #include <cstring> //#include <conio.h> #define maxcao 1000000 using namespace std; int f[300000],g[300000],a[50001],KQ1,KQ2; void thietlap(int x,int y,int d) { if(x==y){ f[d]=a[x]; g[d]=a[x]; } else { thietlap(x,(x+y)/2,2*d); thietlap((x+y)/2+1,y,2*d+1); f[d]=max(f[2*d],f[2*d+1]); g[d]=min(g[2*d],g[2*d+1]); } } void tinhmax(int dau,int cuoi,int x,int y,int d) { if(dau>y||cuoi<x); else if(dau<=x&&cuoi>=y) KQ1=max(KQ1,f[d]); else { tinhmax(dau,cuoi,x,(x+y)/2,2*d); tinhmax(dau,cuoi,(x+y)/2+1,y,2*d+1); } } void tinhmin(int dau,int cuoi,int x,int y,int d) { if(dau>y||cuoi<x); else if(dau<=x&&cuoi>=y) KQ2=min(KQ2,g[d]); else { tinhmin(dau,cuoi,x,(x+y)/2,2*d); tinhmin(dau,cuoi,(x+y)/2+1,y,2*d+1); } } int main() { // freopen("NKLINEUP.in","r",stdin); int n,m,p,x,y,u; scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } thietlap(1,n,1); for(int i=1;i<=m;i++) { scanf("%d %d",&x,&y); KQ1 = 0;KQ2 = maxcao; tinhmax(x,y,1,n,1); tinhmin(x,y,1,n,1); printf("%d\n",KQ1-KQ2); } // getch(); }
Code mẫu của ll931110
Program NKLINEUP; Const input = ''; output = ''; Var a: array[1..50000] of longint; f1,f2,d1,d2: array[1..300000] of longint; n,q: longint; r1,r2,dau,cuoi: longint; fi,fo: text; Procedure enter; Var i: longint; Begin Assign(fi, input); Reset(fi); Readln(fi, n, q); For i:= 1 to n do readln(fi, a[i]); End; Function max(x,y: longint): longint; Begin If x > y then max:= x else max:= y; End; Function min(x,y: longint): longint; Begin If x < y then min:= x else min:= y; End; Procedure swap(x,y: longint); Var tmp: longint; Begin tmp:= x; x:= y; y:= tmp; End; Procedure build1(k, L, H: longint); Var mid: longint; Begin If L > H then exit; If L = H then Begin f1[k]:= a[L]; exit; End; mid:= (L + H) div 2; build1(2 * k, L, mid); build1(2 * k + 1, mid + 1, H); f1[k]:= max(f1[2 * k],f1[2 * k + 1]); End; Procedure build2(k, L, H: longint); Var mid: longint; Begin If L > H then exit; If L = H then Begin f2[k]:= a[L]; exit; End; mid:= (L + H) div 2; build2(2 * k, L, mid); build2(2 * k + 1, mid + 1, H); f2[k]:= min(f2[2 * k],f2[2 * k + 1]); End; Procedure visit1(k, L, H: longint); Var mid: longint; Begin If (L > cuoi) or (dau > H) then exit; If (dau <= L) and (H <= cuoi) then Begin r1:= max(r1,f1[k]); exit; End; mid:= (L + H) div 2; visit1(2 * k, L, mid); visit1(2 * k + 1, mid + 1, H); End; Procedure visit2(k, L, H: longint); Var mid: longint; Begin If (L > cuoi) or (dau > H) then exit; If (dau <= L) and (H <= cuoi) then Begin r2:= min(r2,f2[k]); exit; End; mid:= (L + H) div 2; visit2(2 * k, L, mid); visit2(2 * k + 1, mid + 1, H); End; Procedure solve; Var i,u,v,res: longint; Begin Assign(fo, output); Rewrite(fo); build1(1,1,n); build2(1,1,n); For i:= 1 to q do Begin Readln(fi, u, v); If u > v then swap(u,v); r1:= 0; r2:= maxlongint; If u = v then writeln(fo, 0) else if abs(u - v) = 1 then writeln(fo, abs(a[u] - a[v])) else Begin dau:= u; cuoi:= v; visit1(1,1,n); visit2(1,1,n); res:= r1 - r2; Writeln(fo, res); End; End; Close(fo); Close(fi); End; Begin enter; solve; End.
Code mẫu của skyvn97
#include<stdio.h> #define MAX 50505 int n,q; int a,b; int h[MAX]; int f[MAX][20]; int l[MAX][20]; int min(int x,int y) { if (x<y) return (x); else return (y); } int max(int x,int y) { if (x>y) return (x); else return (y); } void init(void) { scanf("%d",&n); scanf("%d",&q); int i; for (i=1;i<=n;i=i+1) scanf("%d",&h[i]); } void RMQ(void) { int i,j; for (i=1;i<=n;i=i+1) { f[i][0]=h[i]; l[i][0]=h[i]; } for (j=1;(1<<j)<=n;j=j+1) for (i=1;i+(1<<j)-1<=n;i=i+1) { f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); l[i][j]=min(l[i][j-1],l[i+(1<<(j-1))][j-1]); } } int res(int a,int b) { int k=0; while ((1<<k)<=b-a+1) k=k+1; k=k-1; return (max(f[a][k],f[b-(1<<k)+1][k])-min(l[a][k],l[b-(1<<k)+1][k])); } void process(void) { int i; for (i=1;i<=q;i=i+1) { scanf("%d",&a); scanf("%d",&b); printf("%d\n",res(a,b)); } } int main(void) { init(); RMQ(); process(); }
Code mẫu của khuc_tuan
uses math; type integer = longint; var i,ln, nn, u,v,n, q : integer; a : array[1..50000] of integer; ms, ml : array[1..4*50000] of integer; procedure init(node,l,r:integer); var mid : integer; begin if l=r then begin ms[node] := a[l]; ml[node] := a[l]; end else begin mid := (l+r) div 2; init(2*node,l,mid); init(2*node+1,mid+1,r); ms[node] := min( ms[2*node],ms[2*node+1]); ml[node] := max( ml[2*node],ml[2*node+1]); end; end; procedure get(node,l,r:integer); var mid : integer; begin if (u<=l) and (r<=v) then begin ln := max( ln, ml[node]); nn := min( nn, ms[node]); exit; end; mid := (l+r) div 2; if u<=mid then get(2*node,l,mid); if(mid<v) then get(2*node+1,mid+1,r); end; begin read( n, q); for i:=1 to n do read(a[i]); init(1,1,n); for i:=1 to q do begin read(u,v); ln := 0; nn := 1000000000; get( 1, 1, n); writeln( ln-nn); end; end.
Comments