Editorial for Dragon Shooting
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
uses math; const fi=''; maxn=100010; oo=1000000; var n,m:longint; a,h,f,g:array[1..maxn shl 2] of longint; pos,d:array[1..maxn] of longint; procedure add(node,l,r,x,val:longint); var mid:longint; begin if (l=x) and (r=x) then begin a[node]:=val; h[node]:=x; pos[x]:=node; end else begin mid:=(l+r) shr 1; if x<=mid then add(node shl 1,l,mid,x,val) else add(node shl 1+1,mid+1,r,x,val); if val>a[node] then a[node]:=val; h[node]:=h[node shl 1]; end; end; procedure rf; var i,x:longint; begin read(n); for i:=1 to n do begin read(x); add(1,1,n,i,x); end; end; function find(node,l,r,val:longint):longint; var mid:longint; begin if l=r then find:=l else begin mid:=(l+r) shr 1; val:=val+g[node]; if h[node shl 1+1]<=val then find:=find(node shl 1+1,mid+1,r,val) else find:=find(node shl 1,l,mid,val); end; end; procedure update(node,l,r,x:longint); var mid:longint; begin end; procedure incr(node,l,r,x,y:longint); var mid:longint; begin if (l=x) and (r=y) then begin f[node]:=f[node]+1; g[node]:=g[node]+1; h[node]:=h[node]-1; end else begin mid:=(l+r) shr 1; if x<=mid then incr(node shl 1,l,mid,x,min(y,mid)); if y>mid then incr(node shl 1+1,mid+1,r,max(x,mid+1),y); f[node]:=max(f[node shl 1],f[node shl 1+1])+g[node]; end; end; procedure update(x:longint); begin while x>1 do begin x:=x shr 1; a[x]:=max(a[x shl 1],a[x shl 1+1]); h[x]:=min(h[x shl 1],h[x shl 1+1])-g[x]; end; end; function find2(node,l,r,val:longint):longint; var mid:longint; begin if (l=r) then find2:=l else begin mid:=(l+r) shr 1; val:=val-g[node]; if f[node shl 1]>=val then find2:=find2(node shl 1,l,mid,val) else find2:=find2(node shl 1+1,mid+1,r,val); end; end; procedure get(node,l,r,x,y:longint;var s:longint); var mid,t,u:longint; begin if (l=x) and (r=y) then s:=a[node] else begin mid:=(l+r) shr 1; t:=-1; u:=-1; if x<=mid then get(node shl 1,l,mid,x,min(y,mid),t); if y>mid then get(node shl 1+1,mid+1,r,max(x,mid+1),y,u); s:=max(t,u); end; end; procedure pr; var i,x,y,t,u,dem,re:longint; c:char; begin readln(m); dem:=0; for i:=1 to m do begin read(c); if c='S' then begin readln(x); y:=find(1,1,n,x); a[pos[y]]:=-1; h[pos[y]]:=oo; if y<n then incr(1,1,n,y+1,n); update(pos[y]); dem:=dem+1; end else begin re:=-1; readln(x,y); if x>dem then begin writeln('NONE'); continue; end; t:=find2(1,1,n,x); if y>=dem then u:=n else u:=find2(1,1,n,y+1)-1; get(1,1,n,t,u,re); if re=-1 then writeln('NONE') else writeln(re); end; end; end; begin assign(input,fi); reset(input); rf; pr; close(input); end.
Code mẫu của ladpro98
#include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <queue> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <climits> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> #define FOR(i, a, b) for(int i = (a); i < (b); i++) #define REP(i, a, b) for(int i = (a); i <=(b); i++) #define FORD(i, a, b) for(int i = (a); i > (b); i--) #define REPD(i, a, b) for(int i = (a); i >=(b); i--) #define SZ(a) (int((a).size())) #define ALL(a) (a).begin(), (a).end() #define PB push_back #define MP make_pair #define LL long long #define LD long double #define II pair<int, int> #define X first #define Y second #define VI vector<int> const int N = 100005; using namespace std; int MAX[4 * N], sz[4 * N], a[N]; int n, m; #define idL (id << 1) #define idR (idL | 1) struct node { int l, r, id; node (int _l, int _r, int _id): l(_l), r(_r), id(_id) {} node left() {return node(l, l + r >> 1, idL);} node right() {return node((l + r >> 1) + 1, r, idR);} void build() { if (l > r) return; if (l == r) { sz[id] = 1; MAX[id] = a[l]; return; } left().build(); right().build(); sz[id] = r - l + 1; MAX[id] = max(MAX[idL], MAX[idR]); } int erase(int i) { if (l == r) { MAX[id] = -1; sz[id] = 0; return l; } int pos; if (sz[idL] >= i) pos = left().erase(i); else pos = right().erase(i - sz[idL]); sz[id]--; MAX[id] = max(MAX[idL], MAX[idR]); return pos; } int getMax(int i, int j) { if (l > r || r < i || j < l) return -1; if (i <= l && r <= j) return MAX[id]; return max(left().getMax(i, j), right().getMax(i, j)); } }; struct fenwickTree { int bit[N]; void Upd(int i) {for(; i < N; i += i & -i) bit[i]++;} int Get(int i) { int s = 0; for(; i; i -= i & -i) s += bit[i]; return s; } } BIT; int bsL(int x) { int l = 1, r = n, k = -1; while (l <= r) { int m = l + r >> 1; if (BIT.Get(m) >= x) { k = m; r = m - 1; } else l = m + 1; } return k; } int bsR(int x) { int l = 1, r = n, k = -1; while (l <= r) { int m = l + r >> 1; if (BIT.Get(m) <= x) { k = m; l = m + 1; } else r = m - 1; } return k; } int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n; node root (1, n, 1); REP(i, 1, n) cin >> a[i]; root.build(); int ans, pos, x, y, q; char ch; cin >> q; while (q--) { cin >> ch; if (ch == 'S') { cin >> pos; pos = root.erase(pos); BIT.Upd(pos); } else { cin >> x >> y; if (x < 0) x = 0; if (y > n) y = n; x = bsL(x); y = bsR(y); if (x < 0 || y < 0) ans = -1; else ans = root.getMax(x, y); if (ans == -1) cout << "NONE\n"; else cout << ans << '\n'; } } return 0; }
Code mẫu của RR
//Written by RR {$MODE OBJFPC} uses math; const FINP = ''; FOUT = ''; MAXN = 100111; SNODE = 262144; var f1,f2 : text; n,m : longint; a : array[1..MAXN] of longint; sl,ln : array[1..snode] of longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure inp; var i:longint; begin read(f1,n); for i:=1 to n do read(f1,a[i]); end; procedure init(i,l,r:longint); inline; var mid:longint; begin if l=r then begin ln[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]); end; function kth(u,i,l,r:longint):longint; inline; var mid:longint; begin if sl[i]=0 then if u<=r-l+1 then exit(l+u-1); mid:=(l+r) shr 1; if (mid-l+1-sl[i shl 1]) >= u then exit(kth(u,i shl 1,l,mid)) else exit(kth(u-(mid-l+1-sl[i shl 1]),i shl 1+1,mid+1,r)); end; procedure erase(u,i,l,r:longint); inline; var mid:longint; begin if (u<l) or (r<u) then exit; if l=r then begin ln[i]:=-1; sl[i]:=1; exit; end; inc(sl[i]); mid:=(l+r) shr 1; erase(u,i shl 1,l,mid); erase(u,i shl 1+1,mid+1,r); ln[i]:=max(ln[i shl 1],ln[i shl 1+1]); end; function get(u,i,l,r:longint):longint; inline; var mid:longint; begin if l=r then exit(l); mid:=(l+r) shr 1; if sl[i shl 1]>=u then exit(get(u,i shl 1,l,mid)) else exit(get(u-sl[i shl 1],i shl 1+1,mid+1,r)); end; function getMax(u,v,i,l,r:longint):longint; var mid:longint; begin if (v<l) or (r<u) then exit(0); if (u<=l) and (r<=v) then exit(ln[i]); mid:=(l+r) shr 1; exit(max(getMax(u,v,i shl 1,l,mid),getMax(u,v,i shl 1+1,mid+1,r))); end; procedure solve; var i,u,v:longint; c:char; begin inc(n); erase(n,1,1,n); init(1,1,n); readln(f1,m); for i:=1 to m do begin read(f1,c); if c='Q' then begin readln(f1,u,v); u:=get(u,1,1,n); v:=get(v+1,1,1,n)-1; v:=getMax(u,v,1,1,n); if v<=0 then writeln(f2,'NONE') else writeln(f2,v); end else //c='S' begin readln(f1,u); u:=kth(u,1,1,n); erase(u,1,1,n); end; end; end; begin openF; inp; solve; closeF; end.
Comments