Editorial for WHITE BLACK
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=10010; var n,m,i,x,y,z:longint; a,g,h,f:array[1..maxn shl 2] of longint; procedure put(x,val:longint); begin f[x]:=val; g[x]:=val; h[x]:=val; end; procedure add(node,l,r,x,y,z:longint); var mid:longint; begin if (l=x) and (r=y) then begin a[node]:=z; if z=1 then put(node,r-l+1) else put(node,0); end else begin mid:=(l+r) shr 1; if a[node]<>0 then begin a[node shl 1]:=a[node]; a[node shl 1+1]:=a[node]; put(node shl 1,(mid-l+1)*(2-a[node])); put(node shl 1+1,(r-mid)*(2-a[node])); a[node]:=0; end; if x<=mid then add(node shl 1,l,mid,x,min(y,mid),z); if mid<y then add(node shl 1+1,mid+1,r,max(x,mid+1),y,z); if g[node shl 1]=mid-l+1 then g[node]:=mid-l+1+g[node shl 1+1] else g[node]:=g[node shl 1]; if h[node shl 1+1]=r-mid then h[node]:=h[node shl 1]+r-mid else h[node]:=h[node shl 1+1]; f[node]:=max(f[node shl 1],f[node shl 1+1]); f[node]:=max(f[node],h[node shl 1]+g[node shl 1+1]); end; end; begin assign(input,fi); reset(input); read(n,m); add(1,1,n,1,n,1); for i:=1 to m do begin read(z); if z=3 then writeln(f[1]) else begin read(x,y); add(1,1,n,x,y,z); end; end; close(input); end.
Code mẫu của ladpro98
program lem4; uses math; type e=record l,r,ans,sum:longint; end; const maxn=10004; fi=''; var it:array[1..4*maxn] of e; lazy:array[1..4*maxn] of longint; n,m,i,x,y,p:longint; inp:text; procedure update(k,l,r,i,j,v:longint); var m:longint; begin if lazy[k]<>0 then begin if lazy[k]=1 then begin it[k].sum:=r-l+1; it[k].l:=it[k].sum; it[k].r:=it[k].sum; it[k].ans:=it[k].sum; end else begin it[k].sum:=0; it[k].l:=0; it[k].r:=0; it[k].ans:=0; end; if l<>r then begin lazy[2*k]:=lazy[k]; lazy[2*k+1]:=lazy[k]; end; lazy[k]:=0; end; if (l>r) or (r<i) or (j<l) then exit; if (i<=l) and (r<=j) then begin if v=1 then begin it[k].sum:=r-l+1; it[k].l:=it[k].sum; it[k].r:=it[k].sum; it[k].ans:=it[k].sum; end else begin it[k].sum:=0; it[k].l:=0; it[k].r:=0; it[k].ans:=0; end; if l<>r then begin lazy[2*k]:=v; lazy[2*k+1]:=v; end; exit; end; m:=(l+r) shr 1; update(2*k,l,m,i,j,v); update(2*k+1,m+1,r,i,j,v); it[k].sum:=it[2*k].sum+it[2*k+1].sum; if it[2*k].sum=(m-l+1) then it[k].l:=it[2*k].sum+it[2*k+1].l else it[k].l:=it[2*k].l; if it[2*k+1].sum=r-m then it[k].r:=it[2*k+1].sum+it[2*k].r else it[k].r:=it[2*k+1].r; it[k].ans:=max(max(it[2*k].ans,it[2*k+1].ans),it[2*k].r+it[2*k+1].l); end; function get(k,l,r,i,j:longint):e; var m:longint; t,p,q:e; begin if (l>r) or (r<i) or (j<l) then exit; if lazy[k]<>0 then begin if lazy[k]=1 then begin it[k].sum:=r-l+1; it[k].l:=it[k].sum; it[k].r:=it[k].sum; it[k].ans:=it[k].sum; end else begin it[k].sum:=0; it[k].l:=0; it[k].r:=0; it[k].ans:=0; end; if l<>r then begin lazy[2*k]:=lazy[k]; lazy[2*k+1]:=lazy[k]; end; lazy[k]:=0; end; if (i<=l) and (r<=j) then exit(it[k]); m:=(l+r) shr 1; if m>=j then exit(get(2*k,l,m,i,j)); if m<i then exit(get(2*k+1,m+1,r,i,j)); p:=get(2*k,l,m,i,j); q:=get(2*k+1,m+1,r,i,j); t.sum:=p.sum+q.sum; if p.sum=(m-l+1) then t.l:=p.sum+q.l else t.l:=p.l; if q.sum=(r-m) then t.r:=q.sum+p.r else t.r:=q.r; t.ans:=max(max(p.ans,q.ans),p.r+q.l); exit(t); end; begin assign(inp,fi);reset(inp); readln(inp,n);readln(inp,m); update(1,1,n,1,n,1); for i:=1 to m do begin read(inp,p); if p=3 then writeln(get(1,1,n,1,n).ans) else begin readln(inp,x,y); update(1,1,n,x,y,p); end; end; end.
Code mẫu của RR
{$R+,Q+} uses math; const FINP=''; FOUT=''; MAXN=10000; snode=262144; var m,n:longint; f1,f2:text; left,right,maxkq,color: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 update(u,v,k:longint); procedure visit(i,l,r:longint); var mid:longint; begin if (v<l) or (r<u) then exit; if (u<=l) and (r<=v) then begin color[i]:=k; if k=1 then begin left[i]:=r-l+1; right[i]:=r-l+1; maxkq[i]:=r-l+1; end else begin left[i]:=0; right[i]:=0; maxkq[i]:=0; end; exit; end; mid:=(l+r) shr 1; if color[i]=1 then begin color[i shl 1]:=1; left[i shl 1]:=mid-l+1; right[i shl 1]:=mid-l+1; maxkq[i shl 1]:=mid-l+1; color[i shl 1+1]:=1; left[i shl 1+1]:=r-mid; right[i shl 1+1]:=r-mid; maxkq[i shl 1+1]:=r-mid; end else if color[i]=2 then begin color[i shl 1]:=2; left[i shl 1]:=0; right[i shl 1]:=0; maxkq[i shl 1]:=0; color[i shl 1+1]:=2; left[i shl 1+1]:=0; right[i shl 1+1]:=0; maxkq[i shl 1+1]:=0; end; color[i]:=0; visit(i shl 1,l,mid); visit(i shl 1+1,mid+1,r); left[i]:=left[i shl 1]; if color[i shl 1]=1 then left[i]:=left[i]+left[i shl 1+1]; right[i]:=right[i shl 1+1]; if color[i shl 1+1]=1 then right[i]:=right[i]+right[i shl 1]; maxkq[i]:=max(max(maxkq[i shl 1],maxkq[i shl 1+1]),right[i shl 1]+left[i shl 1+1]); if (color[i shl 1]=color[i shl 1+1]) then color[i]:=color[i shl 1]; end; begin visit(1,1,n); end; procedure ans; var i,k,u,v:longint; begin for i:=1 to m do begin read(f1,k); if k=3 then writeln(f2,maxkq[1]) else begin read(f1,u,v); update(u,v,k); end; end; end; begin openF; read(f1,n,m); color[1]:=1; left[1]:=n; right[1]:=n; maxkq[1]:=n; ans; closeF; 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> #define ep 0.000001 #define maxn 10011 #define mod 1000000000 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) #define fi first #define se second double const PI=4*atan(1); double const oo = 1e19; using namespace std; typedef pair<int, int> II; typedef vector<int> VI; typedef vector<II> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; struct tree{ int maxleft, maxright, length; tree(){}; tree(int _ml, int _mr, int _l){ maxleft = _ml, maxright = _mr, length = _l; } }; tree empty = tree(0, 0, 0); int n, m, number, u, v; tree f[maxn * 4]; void update(int l, int r, int i, int so){ if(u > r || v < l) return; int t = (r - l + 1) * so; if(u <= l && v >= r){ f[i] = tree(t, t, t); return; } // if(f[i].length == t) return; int mid = (l + r) / 2; if(f[i].length == 0){ f[i + i] = empty; f[i + i + 1] = empty; } if(f[i].length == r - l + 1){ f[i + i] = tree(mid - l + 1, mid - l + 1, mid - l + 1); f[i + i + 1] = tree(r - mid, r - mid, r - mid); } update(l, mid, i + i, so); update(mid + 1, r, i + i + 1, so); f[i].length = max(f[i + i].length, max(f[i + i + 1].length, f[i + i].maxright + f[i + i + 1].maxleft)); if(f[i + i].maxleft == mid - l + 1) f[i].maxleft = f[i + i + 1].maxleft + mid - l + 1; else f[i].maxleft = f[i + i].maxleft; if(f[i + i + 1].maxright == r - mid) f[i].maxright = f[i + i].maxright + r - mid; else f[i].maxright = f[i + i + 1].maxright; } int main(){ //freopen("input.in","r",stdin); //freopen("output.out","w",stdout); scanf("%d %d",&n,&m); for(int i = 1; i <= n; i++) { u = 1, v = i; update(1, n, 1, 1); } //printf("%d.......\n",f[1].length); for(int i = 0; i < m; i++){ scanf("%d",&number); if(number == 3) printf("%d\n",f[1].length); else{ scanf("%d %d",&u,&v); number = 2 - number; update(1, n, 1, number); } } // getch(); }
Code mẫu của ll931110
{$MODE DELPHI} Program LEM4_2; Uses math; Const input = ''; output = ''; maxn = 10000; maxv = 20000; Type rec = record left,right,val,sign: integer; end; Var fi,fo: text; n,m,q,u,v: integer; a: array[1..8 * maxn] of rec; k: array[-1..1] of integer; Procedure openfile; Begin Assign(fi, input); Reset(fi); Assign(fo, output); Rewrite(fo); End; Procedure setval(i,low,high: integer); Var t: integer; Begin t:= a[i].sign; a[i].val:= (high - low + 1) * t * k[t]; a[i].left:= a[i].val; a[i].right:= a[i].val; End; Procedure update(i,low,high: integer); Var mid: integer; Begin If (v < low) or (high < u) then exit; If (u <= low) and (high <= v) then Begin If q = 1 then a[i].sign:= 1 else a[i].sign:= -1; setval(i,low,high); exit; End; mid:= (low + high) div 2; If a[i].sign <> 0 then Begin a[2 * i].sign:= a[i].sign; a[2 * i + 1].sign:= a[i].sign; a[i].sign:= 0; setval(2 * i,low,mid); setval(2 * i + 1,mid + 1,high); End; update(2 * i,low,mid); update(2 * i + 1,mid + 1,high); a[i].left:= a[2 * i].left; If (a[2 * i].left = mid - low + 1) and (a[2 * i + 1].left > 0) then a[i].left:= a[2 * i].left + a[2 * i + 1].left; a[i].right:= a[2 * i + 1].right; If (a[2 * i + 1].right = high - mid) and (a[2 * i].right > 0) then a[i].right:= a[2 * i + 1].right + a[2 * i].right; a[i].val:= max(a[2 * i].val,a[2 * i + 1].val); If a[i].val < a[2 * i].right + a[2 * i + 1].left then a[i].val:= a[2 * i].right + a[2 * i + 1].left; End; Procedure solve; Var i,t: integer; Begin Read(fi, n, m); k[-1]:= maxv; k[1]:= 1; q:= 1; u:= 1; v:= n; update(1,1,n); For i:= 1 to m do Begin Read(fi, q); If q = 3 then Begin t:= a[1].val; If t < 0 then writeln(fo, 0) else writeln(fo, t); End else Begin Readln(fi, u, v); update(1,1,n); End; End; End; Procedure closefile; Begin Close(fo); Close(fi); End; Begin openfile; solve; closefile; End.
Code mẫu của skyvn97
#include<cstdio> #include<vector> #define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1) #define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1) using namespace std; class SegmentTree { private: struct Node { int len,left,right,range; Node() { len=left=right=range=0; } Node(int col,int len) { this->len=len; left=right=range=col==1?len:0; } bool fullSeg(void) const { return (left==len && right==len); } Node operator + (const Node &x) const { Node res; res.len=len+x.len; res.left=fullSeg()?left+x.left:left; res.right=x.fullSeg()?right+x.right:x.right; res.range=max(max(range,x.range),right+x.left); return (res); } }; vector<Node> tree; vector<int> lazy; int n; void pushdown(int i,int l,int r) { if (lazy[i]<0) return; int m=(l+r)>>1; lazy[2*i]=lazy[2*i+1]=lazy[i]; tree[2*i]=Node(lazy[i],m-l+1); tree[2*i+1]=Node(lazy[i],r-m); lazy[i]=-1; } void update(int i,int l,int r,int u,int v,int c) { if (l>v || r<u || l>r || v<u) return; if (u<=l && r<=v) { tree[i]=Node(c,r-l+1); lazy[i]=c; return; } pushdown(i,l,r); int m=(l+r)>>1; update(2*i,l,m,u,v,c); update(2*i+1,m+1,r,u,v,c); tree[i]=tree[2*i]+tree[2*i+1]; } public: SegmentTree() { n=0; } SegmentTree(int n) { this->n=n; tree.assign(4*n+7,Node()); lazy.assign(4*n+7,-1); update(1,1,n,1,n,1); } void update(int l,int r,int c) { update(1,1,n,l,r,c); } int maxSeg(void) const { return (tree[1].range); } }; int n,q; void process(void) { scanf("%d%d",&n,&q); SegmentTree myit(n); REP(zz,q) { int t,l,r; scanf("%d",&t); if (t==3) printf("%d\n",myit.maxSeg()); else { scanf("%d%d",&l,&r); myit.update(l,r,t==1); } } } int main(void) { process(); return 0; }
Code mẫu của khuc_tuan
#include <iostream> using namespace std; #define maxn 10010 int N, Q; int C[maxn * 4], L[maxn * 4], R[maxn * 4], M[maxn * 4]; void init( int node, int left, int right) { L[node] = R[node] = M[node] = right - left + 1; C[node] = 0; if(left<right) { int m = (left+right)/2; init( node*2, left, m); init( node*2+1,m+1,right); } } void fill( int node, int left, int right, int x, int y, int color, int temp) { if(x<=left && right<=y) { C[node] = color; L[node] = R[node] = M[node] = (color==0) ? (right - left + 1) : 0; return; } if(temp==-1 && C[node]!=-1) temp = C[node]; int mid = (left+right)/2; C[node] = -1; if(x<=mid) fill( 2*node, left, mid, x, y, color, temp); else if(temp!=-1) fill( 2*node, left, mid, left, mid, temp, temp); if(mid<y) fill( 2*node+1, mid+1, right, x, y, color, temp); else if(temp!=-1) fill( 2*node+1, mid+1, right, mid+1, right, temp, temp); M[node] = max( max( M[2*node], M[2*node+1]), R[2*node] + L[2*node+1]); if(L[2*node]==mid-left+1) L[node] = L[2*node] + L[2*node+1]; else L[node] = L[2*node]; if(R[2*node+1]==right-mid) R[node] = R[2*node+1] + R[2*node]; else R[node] = R[2*node+1]; } int main() { scanf("%d%d", &N, &Q); init( 1, 1, N); for(int i=0;i<Q;++i) { int code, a, b; scanf("%d", &code); if(code==3) printf("%d\n", max( L[1], max( M[1], R[1]))); else { scanf("%d%d", &a, &b); fill( 1, 1, N, a, b, code-1, -1); } } return 0; }
Comments