상용 코드 템 플 릿 2 - 데이터 구조

// s[]    ，p[]    ，n s   ，m p   
     Next  ：
for (int i = 2, j = 0; i <= m; i ++ ){
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

//   
for (int i = 1, j = 0; i <= n; i ++ ){
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m){
        j = ne[j];
        //         
    }
}

int son[N][26], cnt[N], idx;
// 0       ，     
// son[][]            
// cnt[]              

//        
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

//           
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

(1)     ：

    int p[N]; //          

    //   x     
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    //    ，       1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    //   a b       ：
    p[find(a)] = find(b);


(2)  size    ：

    int p[N], size[N];
    //p[]          , size[]          ，                

    //   x     
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    //    ，       1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    //   a b       ：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);


(3)             ：

    int p[N], d[N];
    //p[]          , d[x]  x p[x]   

    //   x     
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    //    ，       1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    //   a b       ：
    p[find(a)] = find(b);
    d[find(a)] = distance; //       ，   find(a)    

// h[N]      , h[1]   ，x     2x,     2x + 1
// ph[k]   k           
// hp[k]       k         
int h[N], ph[N], hp[N], size;

//      ，      
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)  
for (int i = n / 2; i; i -- ) down(i);

(1)    
    int h[N], e[N], ne[N], idx;

    //           
    void insert(int x)
    {
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }

    //               
    bool find(int x)
    {
        int k = (x % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i])
            if (e[i] == x)
                return true;

        return false;
    }

(2)      
    int h[N];

    //   x     ，  x   ；  x      ，  x       
    int find(int x)
    {
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)
        {
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }

    ：      P   ，P     131 13331，           
   ：     2^64，     unsigned long long  ，            

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]      k       , p[k]   P^k mod 2^64

//    
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

//      str[l ~ r]     
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

vector,     ，     
    size()        
    empty()        
    clear()    
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
          ，    

pair
    first,      
    second,      
          ， first      ， second      （   ）

string，   
    size()/length()         
    empty()
    clear()
    substr(    ，(    ))      
    c_str()                  

queue,   
    size()
    empty()
    push()           
    front()        
    back()        
    pop()        

priority_queue,     ，      
    push()        
    top()        
    pop()        
             ：priority_queue, greater> q;

stack,  
    size()
    empty()
    push()           
    top()        
    pop()        

deque,     
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap,        （   ），        
    size()
    empty()
    clear()
    begin()/end()
    ++, --        ，      O(logn)

    set/multiset
        insert()       
        find()       
        count()           
        erase()
            (1)       x，    x   O(k + logn)
            (2)        ，       
        lower_bound()/upper_bound()
            lower_bound(x)        x         
            upper_bound(x)      x         
    map/multimap
        insert()         pair
        erase()        pair     
        find()
        []    multimap      。        O(logn)
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap,    
         ，            O(1)
        lower_bound()/upper_bound()，     ++，--

bitset,   
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()        1

    any()           1
    none()        0

    set()        1
    set(k, v)    k   v
    reset()        0
    flip()     ~
    flip(k)   k