Hướng dẫn giải của Xếp hàng
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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.
Bình luận