Hướng dẫn giải của Tách từ
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 fi=''; maxn=50010; var n,m,k:longint; a:array[1..maxn] of boolean; s:array[1..maxn shl 2] of longint; f:array[1..maxn shl 2] of longint; procedure put(node,l,r,x,y:longint;val:byte); var mid:longint; begin if (l=x) and (r=y) then begin f[node]:=val; if val=2 then s[node]:=r-l+1 else s[node]:=0; end else begin mid:=(l+r) shr 1; if f[node]>0 then begin f[node shl 1]:=f[node]; f[node shl 1+1]:=f[node]; if f[node]=2 then begin s[node shl 1]:=mid+1-l; s[node shl 1+1]:=r-mid; end else begin s[node shl 1]:=0; s[node shl 1+1]:=0; end; f[node]:=0; end; if x<=mid then put(node shl 1,l,mid,x,min(y,mid),val); if y>mid then put(node shl 1+1,mid+1,r,max(x,mid+1),y,val); s[node]:=s[node shl 1]+s[node shl 1+1]; end; end; procedure init; var i,x,j:longint; begin read(k,m); for i:=1 to k do begin read(x); for j:=n+1 to n+x-1 do a[j]:=true; n:=n+x; end; dec(n); for i:=1 to n do put(1,1,n,i,i,ord(not a[i])+1); readln; end; procedure pr; var i,x,y:longint; c:char; begin for i:=1 to m do begin read(c); if c='C' then writeln(s[1]+1) else begin read(x,y); if c='J' then put(1,1,n,x,y-1,1) else put(1,1,n,x,y-1,2); end; readln; end; end; begin assign(input,fi); reset(input); init; pr; close(input); end.
Code mẫu của ladpro98
#include <bits/stdc++.h> #define endl '\n' const int N = 50050; using namespace std; int it[4 * N], lazy[4 * N], a[N]; int k, q, n; struct node { int l, r, id; void diffuse() { if (lazy[id] == 2) return; it[id] = lazy[id] * (r - l + 1); if (l != r) lazy[id + id] = lazy[id + id + 1] = lazy[id]; lazy[id] = 2; } node(int _l, int _r, int _id) {l = _l; r = _r; id = _id; diffuse();} node left() {return node(l, l + r >> 1, id + id);} node right() {return node((l + r >> 1) + 1, r, id + id + 1);} void Upd(int i, int j, int v) { if (l > r || r < i || j < l) return; if (i <= l && r <= j) {lazy[id] = v; diffuse(); return;} left().Upd(i, j, v); right().Upd(i, j, v); it[id] = it[id + id] + it[id + id + 1]; } int Get(int i, int j) { if (l > r || r < i || j < l) return 0; if (i <= l && r <= j) return it[id]; return left().Get(i, j) + right().Get(i, j); } }; int main() { ios :: sync_with_stdio(0); cin >> k >> q; for(int i = 1; i <= k; i++) {cin >> a[i]; a[i] += a[i - 1];} n = a[k] - 1; for(int i = 1; i <= 4 * n; i++) lazy[i] = 2; node(1, n, 1).Upd(1, n, 1); for(int i = 0; i < k; i++) node(1, n, 1).Upd(a[i] + 1, a[i + 1] - 1, 0); char c; int l, r; for(int i = 1; i <= q; i++) { cin >> c; if (c == 'J') { cin >> l >> r; node(1, n, 1).Upd(l, r - 1, 0); } else if (c == 'D') { cin >> l >> r; node(1, n, 1).Upd(l, r - 1, 1); } else cout << it[1] + 1 << endl; } return 0; }
Code mẫu của RR
//Wishing myself a happy lunar new year with a lot of accept solutions //Written by Nguyen Thanh Trung {$R+,Q+} uses math; const FINP=''; FOUT=''; MAXN=50001; snode=131072; var f1,f2:text; n,q,k:longint; bufin,bufout:array[1..10000] of byte; a:array[1..MAXN] of longint; left,right,all:array[1..snode] of longint; sl:array[1..snode] of longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); setTextBuf(f1,bufin); setTextBuf(f2,bufout); end; procedure closeF; begin close(f1); close(f2); end; procedure inp; var i:longint; begin readln(f1,k,q); for i:=1 to k do read(f1,a[i]); readln(f1); end; procedure build(i,l,r:longint); var mid:longint; begin if l=r then begin sl[i]:=1; exit; end; mid:=(l+r)>>1; build(i<<1,l,mid); build(i<<1+1,mid+1,r); sl[i]:=r-l+1; end; procedure join(u,v:longint); procedure visit(i,l,r:longint); var mid:longint; begin if l>r then exit; if (v<l) or (r<u) then exit; if (u<=l) and (r<=v) then begin if u<l then left[i]:=1; if r<v then right[i]:=1; all[i]:=1; sl[i]:=1; exit; end; if all[i]=1 then begin sl[i]:=1; if u<l then left[i]:=1; if r<v then right[i]:=1; exit; end; mid:=(l+r)>>1; if all[i]=0 then begin all[i<<1]:=0; left[i<<1]:=left[i]; right[i<<1]:=0; sl[i<<1]:=mid-l+1; all[i<<1+1]:=0; left[i<<1+1]:=0; right[i<<1+1]:=right[i]; sl[i<<1+1]:=r-mid; end; visit(i<<1,l,mid); visit(i<<1+1,mid+1,r); left[i]:=left[i<<1]; right[i]:=right[i<<1+1]; sl[i]:=sl[i<<1]+sl[i<<1+1]; if all[i<<1]<>all[i<<1+1] then all[i]:=-1 else if all[i<<1]=0 then all[i]:=0 else if (all[i<<1]=1) and (right[i<<1]=1) then all[i]:=1 else all[i]:=-1; if (right[i<<1]=1) and (left[i<<1+1]=1) then dec(sl[i]); end; begin visit(1,1,n); end; procedure disjoin(u,v:longint); procedure visit(i,l,r:longint); var mid:longint; begin if l>r then exit; if (v<l) or (r<u) then exit; if (u<=l) and (r<=v) then begin if u<l then left[i]:=0; if r<v then right[i]:=0; all[i]:=0; sl[i]:=r-l+1; exit; end; if all[i]=0 then begin if u<l then left[i]:=0; if r<v then right[i]:=0; exit; end; mid:=(l+r)>>1; if all[i]=1 then begin all[i<<1]:=1; left[i<<1]:=left[i]; right[i<<1]:=1; sl[i<<1]:=1; all[i<<1+1]:=1; left[i<<1+1]:=1; right[i<<1+1]:=right[i]; sl[i<<1+1]:=1; end; visit(i<<1,l,mid); visit(i<<1+1,mid+1,r); left[i]:=left[i<<1]; right[i]:=right[i<<1+1]; sl[i]:=sl[i<<1]+sl[i<<1+1]; if all[i<<1]<>all[i<<1+1] then all[i]:=-1 else if (all[i<<1]=0) and (right[i<<1]=0) then all[i]:=0 else if (all[i<<1]=1) and (right[i<<1]=1) then all[i]:=1 else all[i]:=-1; if (right[i<<1]=1) and (left[i<<1+1]=1) then dec(sl[i]); end; begin visit(1,1,n); end; procedure solve; var i,u:longint; begin n:=0; for i:=1 to k do inc(n,a[i]); u:=0; build(1,1,n); for i:=1 to k do begin join(u+1,u+a[i]); u:=u+a[i]; end; end; procedure ans; var ch:char; i,u,v:longint; begin for i:=1 to q do begin read(f1,ch); if ch='J' then begin readln(f1,u,v); if u<>v then join(u,v); end else if ch='D' then begin readln(f1,u,v); if u<>v then disjoin(u,v); end else if ch='C' then begin readln(f1); writeln(f2,sl[1]); end; end; end; begin openF; inp; solve; ans; closeF; end.
Code mẫu của hieult
#pragma comment(linker, "/STACK:16777216") #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 50004 #define oo 1111111111 #define modunlo 111539786 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) #define ull unsigned long long double const PI=4*atan(1); using namespace std; typedef pair<int, int> II; typedef vector<int> VI; typedef vector<II> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; int test; int f[maxn * 4] = {0}, n, a[maxn],k , m, run, x, y; char s[11]; void update(int u, int v, int gt, int i, int l, int r){ if(v < l || u > r) return; if(u <= l && v >= r){ f[i] = (r - l + 1) * gt; return; } int mid = (r + l) >> 1; if(f[i] == 0){ f[i << 1] = 0; f[(i << 1) | 1] = 0; } if(f[i] == r - l + 1){ f[i << 1] = mid - l + 1; f[(i << 1) | 1] = r - mid; } update(u, v, gt, i << 1, l, mid); update(u, v, gt, (i << 1) | 1, mid + 1, r); f[i] = f[i << 1] + f[(i << 1) | 1]; } int main(){ // freopen("input.in","r",stdin); // freopen("output.out","w",stdout); scanf("%d %d",&k,&m); n = -1; for(int i = 1; i <= k; i++){ scanf("%d", &a[i]); n += a[i]; } run = 1; for(int i = 1; i <= k; i++){ if(a[i] > 1) update(run, run + a[i] - 2, 1, 1, 1, n); run += a[i]; } for(int i = 1; i <= m; i++){ scanf("%s",s); if(s[0] == 'C') printf("%d\n", n - f[1] + 1); else if(s[0] == 'J'){ scanf("%d %d",&x,&y); update(x, y - 1, 1, 1, 1, n); } else{ scanf("%d %d",&x,&y); update(x, y - 1, 0, 1, 1, n); } } }
Code mẫu của ll931110
{$MODE DELPHI} program WS; const input = ''; output = ''; maxn = 50000; var fi,fo: text; a: array[1..maxn] of integer; stat,res: array[1..8 * maxn] of integer; n,m,k: integer; u,v: integer; procedure openfile; begin assign(fi, input); reset(fi); assign(fo, output); rewrite(fo); end; procedure init; var i: integer; begin readln(fi, k, m); n := 0; for i := 1 to k do begin read(fi, a[i]); n := n + a[i]; end; dec(n); readln(fi); end; procedure update(i,low,high,val: integer); var mid: integer; begin if low >= high then begin if (low = high) and (u <= low) and (low <= v) then begin stat[i] := val; if val = -1 then res[i] := high - low + 1 else res[i] := 0; end; exit; end; if (v < low) or (high < u) then exit; if (u <= low) and (high <= v) then begin stat[i] := val; if val = -1 then res[i] := high - low + 1 else res[i] := 0; exit; end; mid := (low + high) div 2; if stat[i] <> 0 then begin if stat[i] = -1 then res[i] := high - low + 1 else res[i] := 0; stat[2 * i] := stat[i]; if stat[i] = -1 then res[2 * i] := mid - low + 1 else res[2 * i] := 0; stat[2 * i + 1] := stat[i]; if stat[i] = -1 then res[2 * i + 1] := high - mid else res[2 * i + 1] := 0; stat[i] := 0; end; update(2 * i,low,mid,val); update(2 * i + 1,mid + 1,high,val); res[i] := res[2 * i] + res[2 * i + 1]; end; procedure solve; var i,sum: integer; ch: char; begin u := 1; v := n; update(1,1,n,-1); sum := 1; for i := 1 to k do begin u := sum; v := sum + a[i] - 2; if u <= v then update(1,1,n,1); sum := sum + a[i]; end; for i := 1 to m do begin read(fi, ch); if ch = 'C' then begin readln(fi); writeln(fo, res[1] + 1); end else begin readln(fi, u, v); dec(v); if u <= v then begin if ch = 'J' then update(1,1,n,1) else update(1,1,n,-1); end; end; end; end; procedure closefile; begin close(fo); close(fi); end; begin openfile; init; solve; closefile; end.
Code mẫu của khuc_tuan
#include <cstdio> using namespace std; int a[50050 * 4], s[50050 * 4]; void update(int n, int l, int r, int x, int y, int v, int v2) { if(x<=l && r<=y) { a[n] = v; s[n] = v * (r-l+1); return; } if(a[n]!=-1 && v2==-1) v2 = a[n]; a[n] = -1; int m = (l+r) / 2; if(x<=m) update( 2 * n, l, m, x, y, v, v2); else if(v2!=-1) { a[2*n] = v2; s[2*n] = v2 * (m-l+1); } if(m<y) update( 2 * n + 1, m+1, r, x, y, v, v2); else if(v2!=-1) { a[2*n+1] = v2; s[2*n+1] = v2 * (r-m); } s[n] = s[2*n] + s[2*n+1]; } int main() { int x, m, n=0; scanf("%d%d", &x, &m); for(int i=0, st=0;i<x;++i) { int l; scanf("%d", &l); if(l>=2) update( 1, 0, 50000, st, st + l - 2, 1, -1); st += l; n += l; } char buff[10]; for(int i=0;i<m;++i) { gets(buff); char code; scanf("%c", &code); if(code=='C') printf("%d\n", n - s[1]); else { int u, v; scanf("%d%d", &u, &v); --u; --v; if(u<v) { if(code=='D') update( 1, 0, 50000, u, v-1, 0, -1); else update( 1, 0, 50000, u, v-1, 1, -1); } } } return 0; }
Bình luận