Hướng dẫn giải của Bật đèn
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
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; }
Bình luận