Editorial for Bật đèn


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 maxn=100010;
      fi='';
var n,m,x,y,z,i,re:longint;
    a:array[1..maxn*5] of longint;
    b:array[1..maxn*5] of byte;

procedure add(node,l,r,x,y:longint);
var mid,t,u:longint;
begin
     if (l=x) and (r=y) then
     begin
          a[node]:=r-l+1-a[node];
          b[node]:=b[node] xor 1;
          exit;
     end;
     mid:=(l+r) shr 1;
     if x<=mid then add(node shl 1,l,mid,x,min(y,mid));
     if mid<y then add(node shl 1+1,mid+1,r,max(mid+1,x),y);
     a[node]:=a[node shl 1]+a[node shl 1+1];
     if b[node]=1 then a[node]:=r-l+1-a[node];
end;

procedure calc(node,l,r,x,y,z:longint;var re:longint);
var mid,t,u:longint;
begin
     if (l=x) and (r=y) then
     begin
          if z=0 then re:=a[node]
          else re:=r-l+1-a[node];
          exit;
     end;
     mid:=(l+r) shr 1; t:=0; u:=0;
     z:=z xor b[node];
     if x<=mid then calc(node shl 1,l,mid,x,min(y,mid),z,t);
     if mid<y then  calc(node shl 1+1,mid+1,r,max(mid+1,x),y,z,u);
     re:=t+u;
end;

begin
     assign(input,fi); reset(input);
     read(n,m);
     for i:=1 to m do
     begin
          read(z,x,y);
          if z=0 then add(1,1,n,x,y)
          else
          begin
               z:=0;
               calc(1,1,n,x,y,z,re);
               writeln(re);
          end;
     end;
     close(input);
end.

Code mẫu của happyboy99x

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5;
int tree[4*N], com[4*N], n;

void update(int x, int y, int k = 0, int l = 0, int r = n) {
    if(r <= l || r <= x || y <= l) return;
    if(x <= l && r <= y) ++com[k], tree[k] = r-l-tree[k];
    else {
        update(x, y, 2*k+1, l, (l+r)/2);
        update(x, y, 2*k+2, (l+r)/2, r);
        tree[k] = tree[2*k+1] + tree[2*k+2];
        if(com[k] % 2 == 1) tree[k] = r-l-tree[k];
    }
}

int get(int x, int y, int k = 0, int l = 0, int r = n) {
    if(r <= l || r <= x || y <= l) return 0;
    if(x <= l && r <= y) return tree[k];
    int res = get(x, y, 2*k+1, l, (l+r)/2) + get(x, y, 2*k+2, (l+r)/2, r);
    return com[k] % 2 == 0 ? res : min(r, y) - max(l, x) - res;
}

int main() {
    int q; scanf("%d%d", &n, &q);
    while(q-- > 0) {
        int t, x, y; scanf("%d%d%d", &t, &x, &y);
        if(t == 0) update(x-1, y);
        else printf("%d\n", get(x-1, y));
    }
    return 0;
}

Code mẫu của ladpro98

program lites;
uses    math;
const   maxn=100005;
        fi='';
var     it,lazy:array[1..4*maxn] of longint;
        n,m,i,p,x,y:longint;
        inp:text;

procedure update(k,l,r,i,j:longint);
var     m:longint;
begin
        if lazy[k]=1 then
        begin
                it[k]:=(r-l+1)-it[k];
                if l<>r then
                begin
                        lazy[2*k]:=lazy[2*k] xor 1;
                        lazy[2*k+1]:=lazy[2*k+1] xor 1;
                end;
                lazy[k]:=0;
        end;
        if (l>r) or (r<i) or (j<l) then exit;
        if (i<=l) and (r<=j) then
        begin
                it[k]:=(r-l+1)-it[k];
                if l<>r then
                begin
                        lazy[2*k]:=lazy[2*k] xor 1;
                        lazy[2*k+1]:=lazy[2*k+1] xor 1;
                end;
                exit;
        end;
        m:=(l+r) shr 1;
        update(2*k,l,m,i,j);
        update(2*k+1,m+1,r,i,j);
        it[k]:=it[2*k]+it[2*k+1];
end;

function get(k,l,r,i,j:longint):longint;
var     p,q,m:longint;
begin
        if (l>r) or (r<i) or (j<l) then exit(0);
        if lazy[k]=1 then
        begin
                it[k]:=(r-l+1)-it[k];
                if l<>r then
                begin
                        lazy[2*k]:=lazy[2*k] xor 1;
                        lazy[2*k+1]:=lazy[2*k+1] xor 1;
                end;
                lazy[k]:=0;
        end;
        if (i<=l) and (r<=j) then exit(it[k]);
        m:=(l+r) shr 1;
        p:=get(2*k,l,m,i,j);
        q:=get(2*k+1,m+1,r,i,j);
        exit(p+q);
end;

begin
        assign(inp,fi);reset(inp);
        readln(inp,n,m);
        for i:=1 to m do
        begin
                readln(inp,p,x,y);
                if p=0 then update(1,1,n,x,y)
                else
                writeln(get(1,1,n,x,y));
        end;
end.

Code mẫu của RR

{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=100000;
  snode=524288;
var
  bat,tat,val:array[1..snode] of longint;
  n,q:longint;
  f1,f2:text;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure swap(var a,b:longint);
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure update(u,v: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
        if val[i]=0 then swap(bat[i],tat[i])
        else val[i]:=0;
        val[i<<1]:=1-val[i<<1];
        val[i<<1+1]:=1-val[i<<1+1];
        exit;
      end;
    mid:=(l+r)>>1;
    if val[i<<1]=1 then
      begin
        val[i<<1]:=0;
        swap(bat[i<<1],tat[i<<1]);
        val[i<<2+0]:=1-val[i<<2+0];
        val[i<<2+1]:=1-val[i<<2+1];
      end;
    if val[i<<1+1]=1 then
      begin
        val[i<<1+1]:=0;
        swap(bat[i<<1+1],tat[i<<1+1]);
        val[i<<2+2]:=1-val[i<<2+2];
        val[i<<2+3]:=1-val[i<<2+3];
      end;
    visit(i<<1,l,mid);
    visit(i<<1+1,mid+1,r);
    bat[i]:=bat[i<<1]+bat[i<<1+1];
    tat[i]:=tat[i<<1]+tat[i<<1+1];
  end;
begin
  visit(1,1,n);
end;
function get(u,v:longint):longint;
var
  kq: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
        if val[i]=1 then
          begin
            val[i]:=0;
            swap(bat[i],tat[i]);
            val[i<<1]:=1-val[i<<1];
            val[i<<1+1]:=1-val[i<<1+1];
          end;
        inc(kq,bat[i]);
        exit;
      end;
    mid:=(l+r)>>1;
    if val[i]=1 then
      begin
        val[i]:=0;
        swap(bat[i],tat[i]);
        val[i<<1+0]:=1-val[i<<1+0];
        val[i<<1+1]:=1-val[i<<1+1];
      end;
    visit(i<<1,l,mid);
    visit(i<<1+1,mid+1,r);
  end;
begin
  kq:=0;
  visit(1,1,n);
  get:=kq;
end;
procedure build(i,l,r:longint);
var
  mid:longint;
begin
  if l=r then
    begin
      bat[i]:=0;
      tat[i]:=1;
      exit;
    end;
  mid:=(l+r)>>1;
  build(i<<1,l,mid);
  build(i<<1+1,mid+1,r);
  bat[i]:=bat[i<<1]+bat[i<<1+1];
  tat[i]:=tat[i<<1]+tat[i<<1+1];
end;
procedure solve;
var
  u,v,yc:longint;
begin
  for q:=1 to q do
    begin
      read(f1,yc);
      if yc=0 then
        begin
          read(f1,u,v);
          update(u,v);
        end
      else //if yc=1 then
        begin
          read(f1,u,v);
          writeln(f2,get(u,v));
        end;
    end;
end;
begin
  openF;
  read(f1,n,q);
  build(1,1,n);
  solve;
  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 100011
#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 number, change;
    tree(){};
    tree(int _number, int _change){ number = _number, change = _change;}
};

tree empty = tree(0,0);

int n, m, u, v, chiso;
tree f[maxn * 4];

void update(int l, int r, int i){

    if(u > r || v < l){
        if(f[i].change) f[i].number = r - l + 1 - f[i].number;
        f[i + i].change ^= f[i].change;
        f[i + i + 1].change ^= f[i].change;
        f[i].change = 0; 
    return;
    }
    if(u <= l && v >= r){ 
        f[i].change = 1 - f[i].change;
        if(f[i].change) f[i].number = r - l + 1 - f[i].number;
        f[i + i].change ^= f[i].change;
        f[i + i + 1].change ^= f[i].change;
        f[i].change = 0;
        return;
    }
    int mid = (l + r) / 2;
    f[i + i].change ^= f[i].change;
    f[i + i + 1].change ^= f[i].change;
    f[i].change = 0;
    update(l, mid, i + i);
    update(mid + 1, r, i + i + 1);
    f[i].number = f[i + i].number + f[i + i + 1].number;
}

int get(int l, int r,int i){
    if(u > r || v < l) return 0;
    if(u <= l && v >= r){
        if(f[i].change) return r - l + 1 - f[i].number;
        return f[i].number;
    }
    int mid = (l + r) / 2;
    f[i + i].change ^= f[i].change;
    f[i + i + 1].change ^= f[i].change;
    if(f[i].change) f[i].number = r - l + 1 - f[i].number;
    f[i].change = 0;
    return get(l, mid, i + i) + get(mid + 1, r, i + i + 1);
}

int main(){
   // freopen("input.in","r",stdin); 
   // freopen("output.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i = 1; i < 4 * n; i++) {
        f[i] = empty;
    }
    //printf("%d.......\n",f[1].length);
    for(int i = 0; i < m; i++){
      //  printf("**%d\n",i);
        scanf("%d %d %d",&chiso,&u,&v);
        if(chiso == 0){ update(1, n, 1);}
        else printf("%d\n",get(1, n, 1));
    }
     // getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
Program LITES2;
Const
  input  = '';
  output = '';
  maxn = 100000;
Type
  rec = record
    val: integer;
    swt,pre: boolean;
  end;
Var
  fi,fo: text;
  n,m,u,v: integer;
  a: array[1..8 * maxn] of rec;

Procedure openfile;
Begin
  Assign(fi, input);
    Reset(fi);

  Assign(fo, output);
    Rewrite(fo);
End;

Procedure update(i,low,high: integer);
Var
  mid,left,right: integer;
Begin
  If (v < low) or (high < u) then exit;
  If (u <= low) and (high <= v) then
    Begin
      a[i].swt:= not a[i].swt;
      exit;
    End;

  mid:= (low + high) div 2;
  update(2 * i,low,mid);
  update(2 * i + 1,mid + 1,high);

  left:= a[2 * i].val;
  If a[2 * i].swt then left:= (mid - low + 1) - left;

  right:= a[2 * i + 1].val;
  If a[2 * i + 1].swt then right:= (high - mid) - right;

  a[i].val:= left + right;
End;

Function calc(i,low,high: integer): integer;
Var
  mid: integer;
Begin
  If (v < low) or (high < u) then exit(0);
  If (u <= low) and (high <= v) then
    If not (a[i].swt xor a[i].pre) then exit(a[i].val)
                                   else exit(high - low + 1 - a[i].val);

  mid:= (low + high) div 2;
  a[2 * i].pre:= a[i].swt xor a[i].pre;
  a[2 * i + 1].pre:= a[2 * i].pre;
  calc:= calc(2 * i,low,mid) + calc(2 * i + 1,mid + 1,high);
End;

Procedure swap(var x,y: integer);
Var
  t: integer;
Begin
  t:= x;
  x:= y;
  y:= t;
End;

Procedure solve;
Var
  i,q: integer;
Begin
  For i:= 1 to 8 * maxn do
    Begin
      a[i].val:= 0;
      a[i].swt:= false;
    End;
  a[1].pre:= false;

  Readln(fi, n, m);
  For i:= 1 to m do
    Begin
      Readln(fi, q, u, v);
      If u > v then swap(u,v);
      If q = 0 then update(1,1,n) else writeln(fo, calc(1,1,n));
    End;
End;

Procedure closefile;
Begin
  Close(fo);
  Close(fi);
End;

Begin
  openfile;
  solve;
  closefile;
End.

Code mẫu của skyvn97

#include<cstdio>
#define MAX   100100
int t[5*MAX];
int c[5*MAX];
int m,n;
void init(void) {
    scanf("%d",&n);
    scanf("%d",&m); 
    int i;
    for (i=1;i<=4*n;i=i+1) {
        t[i]=0;
        c[i]=0;
    }
}
void update(int i,int l,int r,int u,int v) {
    //printf("Updating %d %d %d %d %d\n",i,l,r,u,v);
    if (l>v) return;
    if (r<u) return;
    if (l>r) return;
    if (u<=l && r<=v) {
        c[i]=1-c[i];
        t[i]=r-l+1-t[i];
        //printf("   t[%d]=%d c[%d]=%d\n",i,t[i],i,c[i]);
        return;
    }
    if (c[i]>0) c[2*i]=1-c[2*i];
    if (c[i]>0) c[2*i+1]=1-c[2*i+1];
    int m=(l+r)/2;
    if (c[i]>0) t[2*i]=m-l+1-t[2*i];
    if (c[i]>0) t[2*i+1]=r-m-t[2*i+1];  
    c[i]=0;
    //printf("   t[%d]=%d c[%d]=%d\n",2*i,t[2*i],2*i,c[2*i]);
    //printf("   t[%d]=%d c[%d]=%d\n",2*i+1,t[2*i+1],2*i+1,c[2*i+1]);
    update(2*i,l,m,u,v);
    update(2*i+1,m+1,r,u,v);
    t[i]=t[2*i]+t[2*i+1];
}
int sum(int i,int l,int r,int u,int v,int change) {
    //printf("Geting sum %d %d %d %d %d with %d\n",i,l,r,u,v,change);
    if (l>v) return (0);
    if (r<u) return (0);
    if (l>r) return (0);
    if (u<=l && r<=v) {
        if (change>0) return (r-l+1-t[i]);
        else return (t[i]);
    }
    if (c[i]>0) change=1-change;
    int m=(l+r)/2;
    int left=sum(2*i,l,m,u,v,change);
    int right=sum(2*i+1,m+1,r,u,v,change);
    return (left+right);
}
void process(void) {
    int i,s,e,T;
    //int j;
    for (i=1;i<=m;i=i+1) {
        scanf("%d",&T);
        scanf("%d",&s);
        scanf("%d",&e);
        if (T==0) {
            update(1,1,n,s,e);
            //printf("After update %d %d\n",s,e);
            //for (j=1;j<=7;j=j+1) printf("%d ",t[j]); printf("\n");
            //for (j=1;j<=7;j=j+1) printf("%d ",c[j]); printf("\n");
        }
        else printf("%d\n",sum(1,1,n,s,e,0));
    }   
}
int main(void) {
    //freopen("tmp.txt","r",stdin);
    init();
    process();
    return 0;
}

Code mẫu của khuc_tuan

#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 100040;

int sum[MAXN * 4], flip[MAXN * 4];

void update(int n, int l, int r, int x, int y) {
    if(x<=l && r<=y) {
        flip[n] ^= 1;
        sum[n] = (r-l+1) - sum[n];
        return;
    }
    int m = (l+r) / 2;
    if(x<=m) update(2*n,l,m,x,y);
    if(m<y) update(2*n+1,m+1,r,x,y);
    sum[n] = sum[2*n] + sum[2*n+1];
    if(flip[n]) sum[n] = (r-l+1) - sum[n];
}

int getsum(int n, int l, int r, int x, int y, int f) {
    if(x<=l && r<=y) {
        if(f) return (r-l+1) - sum[n];
        else return sum[n];
    }
    int m = (l+r) / 2;
    f ^= flip[n];
    int res = 0;
    if(x<=m) res += getsum(2*n,l,m,x,y,f);
    if(m<y) res += getsum(2*n+1,m+1,r,x,y,f);
    f ^= flip[n];
    return res;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=0;i<m;++i) {
        int c, u, v;
        scanf("%d%d%d", &c, &u, &v);
        if(c==0) update( 1, 1, n, u, v);
        else printf("%d\n", getsum( 1, 1, n, u, v, 0));
    }
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.