每一项按顺序理解之后裸敲，每个代码最多15分钟，用模板题来测，超过15分钟算未理解
线段树
平衡树（ Treap , sbt , spt ）
#include <iostream> #include <cstdio> using namespace std ; const int N = 1000010 ; struct node { int lr , rr , r , v ; node(){} node( int lr , int rr , int r , int v ):lr(lr),rr(rr),r(r),v(v) {} }; struct Treap { node e[N]; int root , size ; void init() { size = 0 ; root = -1 ; } void Rot_l( int &o ) { int tmp = e[o].rr ; e[o].rr = e[tmp].lr ; e[tmp].lr = o ; o = tmp ; } void Rot_r( int &o ) { int tmp = e[o].lr ; e[o].lr = e[tmp].rr ; e[tmp].rr = o ; o = tmp ; } void insert( int &o , int v , int r ) { if( o == -1 ) { o = size++ ; e[o].lr = e[o].rr = -1 ; e[o].r = r , e[o].v = v ; } else if( v < e[o].v ) { insert( e[o].lr , v , r ) ; if( e[ e[o].lr ].r > e[o].r ) Rot_r(o) ; } else { insert( e[o].rr , v , r ); if( e[ e[o].rr ].r > e[o].r ) Rot_l(o) ; } } void remove( int &o , int x ) { if( e[o].v == x ) { if( e[o].lr == -1 ) { o = e[o].rr ; } else if( e[o].rr == -1 ) { o = e[o].lr ; } else { if( e[ e[o].lr ].r > e[ e[o].rr ].r ) { Rot_r(o); remove( e[o].rr , x ); } else { Rot_l(o); remove( e[o].lr , x ) ; } } } else if( e[o].v > x ) { remove( e[o].lr , x ) ; } else { remove( e[o].rr , x ) ; } } int Find_max( int o ) { if( o == -1 ) return -1 ; while( e[o].rr != -1 ) o = e[o].rr ; cout << e[o].r << endl ; return e[o].v ; } int Find_min( int o ) { if( o == -1 ) return -1 ; while( e[o].lr != -1 ) o = e[o].lr ; cout << e[o].r << endl ; return e[o].v ; } } T ; int Run () { int op , x , y ; T.init() ; while( cin >> op ) { if( !op ) { break ; } else if( op == 1 ) { cin >> x >> y ; T.insert( T.root , y , x ) ; } else if( op == 2 ) { x = T.Find_max( T.root ) ; if( x == -1 ) { cout << '0' << endl ; continue ; } T.remove( T.root , x ) ; } else { x = T.Find_min( T.root ) ; if( x == -1 ) { cout << '0' << endl ; continue ; } T.remove( T.root , x ) ; } } return 0 ; } int main () { ios::sync_with_stdio(0); return Run() ; }
#include <iostream> #include <cstring> #include <cstdio> using namespace std; const int N = 2000010; const int M = 10000010; int mp[M]; struct node { int lr , rr , siz , v ; node(){} node( int lr , int rr , int siz , int v ):lr(lr),rr(rr),siz(siz),v(v){} }; struct SBT { node e[N] ; int rt , tot; void init() { rt = tot = 1 ; } void Rot_l( int &o ) { int y = e[o].rr ; e[o].rr = e[y].lr; e[y].lr = o ; e[y].siz = e[o].siz ; e[o].siz = e[ e[o].lr ].siz + e[ e[o].rr ].siz + 1 ; o = y ; } void Rot_r( int &o ) { int y = e[o].lr ; e[o].lr = e[y].rr ; e[y].rr = o ; e[y].siz = e[o].siz ; e[o].siz = e[ e[o].lr ].siz + e[ e[o].rr ].siz + 1 ; o = y ; } void Maintain( int &o , bool flag ) { if( !flag ) { if( e[ e[ e[o].lr ].lr ].siz > e[ e[o].rr ].siz ) { Rot_r(o) ; } else if( e[ e[ e[o].lr ].rr ].siz > e[ e[o].rr ].siz ) { Rot_l( e[o].lr ) ; Rot_r(o); } else return ; } else { if( e[ e[ e[o].rr ].rr ].siz > e[ e[o].lr ].siz ) { Rot_l(o) ; } else if( e[ e[ e[o].rr ].lr ].siz > e[ e[o].lr ].siz ) { Rot_r( e[o].rr ) ; Rot_l(o); } else return ; } Maintain( e[o].lr , false ) ; Maintain( e[o].rr , true ) ; Maintain( o , false ) ; Maintain( o , true ) ; } void Insert( int &o , int v ) { if( !o ) { o = tot++ ; e[o] = node( 0 , 0 , 1 , v ) ; return ; } else { e[o].siz++ ; if( v < e[o].v ) { Insert( e[o].lr , v ) ; } else { Insert( e[o].rr , v ) ; } } Maintain(o, v >= e[o].v ) ; } void Delete( int &o , int v ) { if( !o ) return ; e[o].siz-- ; if( v < e[o].v ) Delete( e[o].lr , v ) ; else if( v > e[o].v ) Delete( e[o].rr , v ) ; else { if( e[o].lr == 0 ) o = e[o].rr ; else if( e[o].rr == 0 ) o = e[o].lr ; else { int y = e[o].rr ; while( e[y].lr ) y = e[y].lr ; e[o].v = e[y].v ; Delete( e[o].rr , e[y].v ) ; } } } int Find_Max( int &o ) { int y = o ; while( e[y].rr ) y = e[y].rr ; return e[y].v ; } int Find_Min( int &o ) { int y = o ; while( e[y].lr ) y = e[y].lr ; return e[y].v ; } } T ; int Run() { int op , x , y ; T.init(); while( cin >> op ) { if( op == 0 ) break ; else if( op == 1 ) { cin >> x >> y ; mp[y] = x ; T.Insert( T.rt , y ) ; } else if( op == 2 ) { if( T.e[T.rt].siz == 0 ) { cout << '0' << endl ; } else { int v = T.Find_Max( T.rt ) ; cout << mp[v] << endl ; T.Delete(T.rt,v); } } else { if( T.e[T.rt].siz == 0 ) { cout << '0' << endl ; } else { int v = T.Find_Min( T.rt ); cout << mp[v] << endl ; T.Delete(T.rt,v); } } } return 0 ; } int main() { #ifdef LOCAL freopen("in","r",stdin); #endif ios::sync_with_stdio(0); return Run(); }
二叉堆
const int N = 1000010 ; int h[N] , size ; void Modify( int p ) { if( p == 1 ) return ; if( h[p>>1] > h[p] ) swap( h[p>>1] , h[p] ) , Modify( p>>1 ) ; } void Update( int p ) { int l = p<<1 , r = p<<1|1 , f = p ; if( l <= size && h[l] < h[f] ) f = l ; if( r <= size && h[r] < h[f] ) f = r ; if( p != f ) swap( h[f] , h[p] ) , Update(f) ; } void Pop() { swap( h[1] , h[size--] ) ; Update(1) ; } void Push( int x ) { h[++size] = x ; Modify( size ) ; }
左偏树
最大优先 ~ 可合并堆
const int N = 100010 ; struct node { int lr , rr , dis , fa , val ; } T[N] ; inline int find( int k ) { return k == T[k].fa ? k : T[k].fa = find(T[k].fa) ; } int Merge( int a , int b ) { if( !a ) return b ; if( !b ) return a ; if( T[a].val < T[b].val ) swap( a , b ) ; T[a].rr = Merge( b , T[a].rr ) ; T[ T[a].rr ].fa = a ; if( T[ T[a].lr ].dis < T[ T[a].rr ].dis ) swap( T[a].lr , T[a].rr ) ; if( T[a].rr == 0 ) T[a].dis = 0 ; else T[a].dis = T[ T[a].rr ].dis + 1 ; return a ; } int Pop( int a ) { int l = T[a].lr , r = T[a].rr ; T[l].fa = l , T[r].fa = r ; T[a].lr = T[a].rr = T[a].dis = 0 ; return Merge( l , r ) ; }
最短路( Dij , Spfa )
匈牙利
HK
带花树
Dinic
const int N = 404; const int M = 30030 ; const int inf = 1e9 ; int s , t , n , m ; int eh[N] , ef[M] , et[M] , ec[M] , nxt[M] , tot ; int cur[N] , d[N] ; bool vis[N] ; void init() { memset( eh , -1 , sizeof eh ) ; tot = 0 ; } void addedge( int u , int v, int c , int f ) { et[tot] = v , ec[tot] = c , ef[tot] = f , nxt[tot] = eh[u] , eh[u] = tot++ ; et[tot] = u , ec[tot] = 0 , ef[tot] = f , nxt[tot] = eh[v] , eh[v] = tot++ ; } bool bfs() { memset( vis , false , sizeof vis ) ; queue<int>que; que.push(s); vis[s] = true ; d[s] = 0 ; while( !que.empty() ) { int u = que.front() ; que.pop() ; for( int i = eh[u] ; ~i ; i = nxt[i] ) { int v = et[i] ; if( !vis[v] && ef[i] < ec[i] ) { vis[v] = true ; d[v] = d[u] + 1 ; que.push(v); } } } return vis[t] ; } int dfs( int x , int a ) { if( x == t || a == 0 ) return a ; int flow = 0 , F ; for( int &i = cur[x] ; ~i ; i = nxt[i] ) { int v = et[i] , c = ec[i] , &f = ef[i] ; if( d[x] + 1 == d[v] && ( F = dfs( v , min( a , c - f ) ) ) > 0 ) { f += F , ef[i^1] -= F , a -= F , flow += F ; if( a == 0 ) break ; } } return flow ; } int MF() { int flow = 0 ; while( bfs() ) { memcpy( cur , eh , sizeof eh ) ; flow += dfs( s , 10000000 ); } return flow ; }
ISAP
const int N = 1020 ; const int M = 300010 ; const int INF = 0x3f3f3f3f; int n , m , s , t ; int eh[N] , et[M] , nxt[M] , ef[M] , ec[M] , tot ; void init() { memset( eh , -1 , sizeof eh ) ; tot = 0 ; } void addedge( int u , int v , int c ) { et[tot] = v ; ec[tot] = c ; ef[tot] = 0 ; nxt[tot] = eh[u] ; eh[u] = tot++; et[tot] = u ; ec[tot] = 0 ; ef[tot] = 0 ; nxt[tot] = eh[v] ; eh[v] = tot++; } int d[N] , cur[N] , pre[N] , gap[N] ; int Q[M] , S[M] ; void bfs() { memset( d , -1 , sizeof d ) ; memset( gap , 0 , sizeof gap ) ; int head = 0 , tail = 0 ; d[t] = 0 ; gap[0]++ ; Q[tail++] = t ; while( head < tail ) { int u = Q[head++] ; for( int i = eh[u] ; ~i ; i = nxt[i] ) { int v = et[i] ; if( d[v] != -1 ) continue ; Q[tail++] = v ; d[v] = d[u] + 1; gap[ d[v] ]++; } } } int Sap( int n ) { bfs(); memcpy( cur , eh , sizeof eh ) ; int top = 0 , u = s , flow = 0 ; while( d[s] < n ) { if( u == t ) { int Min = INF , inser ; for( int i = 0 ; i < top ; ++i ) { if( Min > ec[ S[i] ] - ef[ S[i] ] ) { Min = ec[ S[i] ] - ef[ S[i] ] ; inser = i ; } } for( int i = 0 ; i < top ; ++i ) { ef[ S[i] ] += Min ; ef[ S[i]^1 ] -= Min ; } flow += Min ; top = inser ; u = et[ S[top]^1 ]; continue ; } bool flag = false ; int v ; for( int i = cur[u] ; ~i ; i = nxt[i] ) { v = et[i] ; if( ec[i] > ef[i] && d[v] + 1 == d[u] ) { flag = true ; cur[u] = i ; break ; } } if( flag ) { S[top++] = cur[u] ; u = v ; continue ; } int Min = n ; for( int i = eh[u] ; ~i ; i = nxt[i] ) { if( ec[i] > ef[i] && d[ et[i] ] < Min ) { Min = d[ et[i] ] ; cur[u] = i ; } } gap[ d[u] ]-- ; if( !gap[ d[u] ] ) return flow ; d[u] = Min + 1 ; gap[ d[u] ]++ ; if( u != s ) u = et[ S[--top]^1 ] ; } return flow ; }
MCMF
const int N = 10000; const int M = 100000; const int INF = 0x3f3f3f3f; int eh[N] , ec[M] , et[M] , ef[M] , ew[M] , nxt[M] , tot ; int pre[N] , dis[N] ; bool vis[N] ; int s , t , n , m , k ; void init() { memset( eh, -1 , sizeof eh ); tot = 0 ; } void addedge( int u , int v , int cap , int cost ) { et[tot] = v ; ef[tot] = 0 ; ec[tot] = cap ; ew[tot] = cost ; nxt[tot] = eh[u] ; eh[u] = tot++ ; et[tot] = u ; ef[tot] = 0 ; ec[tot] = 0 ; ew[tot] = -cost ; nxt[tot] = eh[v] ; eh[v] = tot++ ; } bool spfa() { memset( vis, false, sizeof vis ) ; memset( dis ,0x3f , sizeof dis ) ; memset( pre , -1 ,sizeof pre ) ; queue<int>que; dis[s] = 0 ; vis[s] = true ; que.push(s) ; while( !que.empty() ) { int u = que.front() ; que.pop() ; vis[u] =false ; for( int i = eh[u] ; ~i ; i = nxt[i] ) { int v = et[i] ; if( ec[i] > ef[i] && dis[v] > dis[u] + ew[i] ) { dis[v] = dis[u] + ew[i] ; pre[v] = i ; if( !vis[v] ) { vis[v] = true ; que.push(v) ; } } } } return pre[t] != -1 ; } int MCMF( int &cost ) { int flow = 0 ; cost = 0 ; while( spfa() ) { int Min = INF ; for( int i = pre[t] ; ~i ; i = pre[ et[i^1] ] ) { if( Min > ec[i] - ef[i] ) { Min = ec[i] - ef[i] ; } } for( int i = pre[t] ; ~i ; i = pre[ et[i^1] ] ) { ef[i] += Min ; ef[i^1] -= Min ; cost += ew[i] * Min ; } flow += Min ; } return flow ; }
BCC
SCC
KMP
Manancher
AC自动机
后缀数组
后缀自动机
DXL（精确覆盖，模糊覆盖）