Mirror的演算法筆記

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=d767 LCA算法裸題 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using   namespace  std; using   namespace  __gnu_cxx; using   namespace  __gnu_pbds; using   ll   =   long   long ; #define   AC  ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); vector < vector <int>>  v,dou; vector < pair <int ,  int>>  ti; vector <int>  dep; int  L,cou = 1 ; void   dfs ( int   x , int   par ) {     ti[x].first  =  cou ++ ;     dou[x][ 0 ] = par;      for ( int  i = 1 ;i <= L;i ++ ) dou[x][i] = dou[dou[x][i - 1 ]][i - 1 ];      for ( auto  e:v[x]) dep[e] = dep[x] + 1 , dfs (e,x);     ti[x].second  =  cou ++ ; } bool   anc ( int   x , int   y ) {  ...

丟一個模板在這裡以免忘記 inline char readchar () { static const size_t bufsize = 65536 ; static char buf[bufsize]; static char * p = buf, * end = buf; if (p == end) end = buf + fread_unlocked (buf, 1 , bufsize, stdin), p = buf; return * p ++ ; } template < class T > void input (T & a ) { static char p; while ((p = readchar ()) < ' 0 ' ) ; a = p ^ ' 0 ' ; while ((p = readchar ()) >= ' 0 ' ) a *= 10 , a += p ^ ' 0 ' ; } 可能會用到的題目:TIOJ 1930 , ZJ c223 , TIOJ 2026

題目鏈接: https://tioj.ck.tp.edu.tw/problems/2055 裸RMQ求區間最小值 因為不會寫sparse table所以就用線段樹開碾 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using namespace std ; using namespace __gnu_cxx ; using namespace __gnu_pbds ; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); struct node { int l,r,m; } st[ 100001 << 2 ]; void pull ( int x ) { st[x].m = min (st[x << 1 ].m,st[x << 1 | 1 ].m); } void build ( int x , int l , int r ) { st[x].l = l,st[x].r = r,st[x].m = 1 e 9 ; if (l == r) cin >> st[x].m; else { int mid = (l + r) >> 1 ; build (x << 1 ,l,mid); build (x << 1 | 1 ,mid + 1 ,r); pull (x); } } int query ( int x , int l , int r ) { int L = st[x].l,R = st[x].r; if (L >= l && R <= r) return st[x].m; else { int mid = (L + R) >> 1 ,m = 1 e 9 ; if (l <= mid) m = min ...

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=d799 維護兩個樹狀數組+前綴和就能達成區間更新和區間求和 以下為code #include < bits/stdc++.h > using namespace std ; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); #define lowbit ( x ) x & ( - x) int n; ll sum[ 500001 ]; struct bit { ll c[ 500001 ]; void update ( int p , int val ) { for (;p <= n;p += lowbit (p)) c[p] += val; } ll query ( int p ) { ll r = 0 ; for (;p > 0 ;p -= lowbit (p)) r += c[p]; return r; } } c1,c2; int main () { AC cin >> n; for (ll i = 1 ;i <= n;i ++ ) { int t; cin >> t; sum[i] = sum[i - 1 ] + t; } int q; cin >> q; while (q -- ) { int v,x,y,k; cin >> v; if (v == 1 ) cin >> x >> y >> k,c1. update (x,k),c1. update (y + 1 , - k),c2. update (x,k * x),c2. update (y + 1 , - k ...

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=d799 就線段樹模板 記得存值的變數要開大一點,例如long long 因為開太小吃WA 以下為code #include < bits/stdc++.h > using namespace std ; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); struct node { unsigned int l,r; unsigned long long sum,lazy; void update ( unsigned long long x ) { sum += (r - l + 1 ) * x; lazy += x; } } st[ 500001 * 4 ]; void push_up ( unsigned int x ) { st[x].sum = st[x << 1 ].sum + st[x << 1 | 1 ].sum; } void push_down ( unsigned int x ) { unsigned int lazy = st[x].lazy; st[x << 1 ]. update (lazy),st[x << 1 | 1 ]. update (lazy); st[x].lazy = 0 ; } void build ( unsigned int x , unsigned int l , unsigned int r ) { st[x].l = l,st[x].r = r,st[x].sum = st[x].lazy = 0 ; if (l == r) cin >> st[x].sum; else { unsigned int mid = (r + l) >> 1 ; build (x << 1 ,l,mid); ...