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.

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

Please read the guidelines before commenting.


There are no comments at the moment.