首页 > 代码库 > 模板复习【updating】

模板复习【updating】

马上就要noi了……可能滚粗已经稳了……但是还是要复习模板啊

LCT: bzoj2049 1A 7min

技术分享
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 5e5 + 10;
const int mod = 1e9+7;

struct LCT {
    int ch[M][2], fa[M], sz[M]; bool rev[M];
    # define ls ch[x][0]
    # define rs ch[x][1]
    inline void up(int x) {
        if(!x) return ;
        sz[x] = 1 + sz[ls] + sz[rs];
    }
    inline void pushrev(int x) {
        if(!x) return ;
        rev[x] ^= 1;
        swap(ch[x][0], ch[x][1]);
    }
    inline void down(int x) {
        if(!x) return ;
        if(rev[x]) {
            pushrev(ls);
            pushrev(rs);
            rev[x] = 0;
        }
    }
    # undef ls 
    # undef rs
    inline bool isrt(int x) {
        return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
    }
    inline void rotate(int x) {
        int y = fa[x], z = fa[y], ls = ch[y][1] == x, rs = ls^1;
        if(!isrt(y)) ch[z][ch[z][1] == y] = x;
        fa[ch[x][rs]] = y; fa[y] = x, fa[x] = z;
        ch[y][ls] = ch[x][rs]; ch[x][rs] = y;
        up(y); up(x);
    }
    int st[M];
    inline void splay(int x) {
        int stn = 0, tx = x;
        while(!isrt(tx)) st[++stn] = tx, tx = fa[tx];
        st[++stn] = tx;
        for (int i=stn; i; --i) down(st[i]);
        while(!isrt(x)) {
            int y = fa[x], z = fa[y];
            if(!isrt(y)) {
                if((ch[z][0] == y) ^ (ch[y][0] == x)) rotate(x);
                else rotate(y);
            }
            rotate(x);
        }
    }
    inline int access(int x) {
        int t = 0;
        for (; x; t=x, x=fa[x]) {
            splay(x);
            ch[x][1] = t;
            up(x);
        }
        return t;
    }
    inline void makeroot(int x) {
        access(x); splay(x); pushrev(x);
    }
    inline int find(int x) {
        access(x); splay(x);
        while(ch[x][0]) x = ch[x][0];
        return x;
    }
    inline void link(int x, int y) {
        makeroot(x); fa[x] = y;
    }
    inline void cut(int x, int y) {
        makeroot(x); access(y); splay(y); ch[y][0] = fa[x] = 0; up(y);
    }
}T;

int n, Q, x, y;

int main() {
    static char op[23];
    cin >> n >> Q;
    for (int i=1; i<=n; ++i) {
        T.ch[i][0] = T.ch[i][1] = T.fa[i] = 0;
        T.sz[i] = 1; T.rev[i] = 0;
    }
    while(Q--) {
        scanf("%s%d%d", op, &x, &y);
        if(op[0] == C) T.link(x, y);
        else if(op[0] == D) T.cut(x, y);
        else puts(T.find(x) == T.find(y) ? "Yes" : "No");
    }
    return 0;
}
View Code

dsu on tree: bzoj4756 1A 10min

技术分享
# include <vector>
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = 1e5 + 10;
const int mod = 1e9+7;

int n, a[N];
vector<int> ps;
int head[N], nxt[N], to[N], tot = 0;
inline void add(int u, int v) {
    ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v;
}

struct BIT {
    int n, c[N];
    # define lb(x) (x & (-x))
    inline void set(int _n) {
        n = _n;
        memset(c, 0, sizeof c);
    }
    inline void edt(int x, int d) {
        for (; x<=n; x+=lb(x)) c[x] += d;
    }
    inline int sum(int x) {
        int ret = 0;
        for (; x; x-=lb(x)) ret += c[x];
        return ret;
    }
    inline int sum(int x, int y) {
        if(x > y) return 0;
        return sum(y) - sum(x-1);
    }
    # undef lb
}T;

int sz[N], mx[N];
inline void dfs(int x) {
    sz[x] = 1; mx[x] = 0;
    for (int i=head[x]; i; i=nxt[i]) {
        dfs(to[i]);
        sz[x] += sz[to[i]];
        if(mx[x] == 0 || sz[to[i]] > sz[mx[x]]) mx[x] = to[i];
    }
}

int ans[N], big[N];

inline void count(int x, int p) {
    T.edt(a[x], p);
    for (int i=head[x]; i; i=nxt[i]) 
        if(!big[to[i]]) count(to[i], p);
}

inline void dsu(int x, bool kep = 0) {
    int son = mx[x];
    for (int i=head[x]; i; i=nxt[i]) 
        if(to[i] != son) dsu(to[i], 0);
    if(son) big[son] = 1, dsu(son, 1);
    count(x, 1);    
    ans[x] = T.sum(a[x] + 1, n);
    if(son) big[son] = 0;
    if(!kep) count(x, -1);
}

int main() {
    cin >> n; T.set(n);
    for (int i=1; i<=n; ++i) {
        scanf("%d", a+i);
        ps.push_back(a[i]);
    }
    sort(ps.begin(), ps.end());
    ps.erase(unique(ps.begin(), ps.end()), ps.end());
    for (int i=1; i<=n; ++i) a[i] = lower_bound(ps.begin(), ps.end(), a[i]) - ps.begin() + 1;
    for (int i=2, par; i<=n; ++i) {
        scanf("%d", &par);
        add(par, i);
    }
    dfs(1);
    dsu(1);
    for (int i=1; i<=n; ++i) printf("%d\n", ans[i]);
    return 0;
}

      
View Code

线段树合并: bzoj4756 2A 13min

warning: 需要注意节点数量为$O(nlogn)$。

技术分享
# include <vector>
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = 1e5 + 10, SN = 262144 * 20 + 5;
const int mod = 1e9+7;

int n, a[N];
vector<int> ps;
int head[N], nxt[N], to[N], tot = 0;
inline void add(int u, int v) {
    ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v;
}

int rt[N];
struct SMT {
    int siz;
    int s[SN], ch[SN][2];
    # define ls ch[x][0]
    # define rs ch[x][1]
    inline void set() {
        siz = 0;
        memset(ch, 0, sizeof ch);
        memset(s, 0, sizeof s);
    }
    inline void up(int x) {
        if(!x) return;
        s[x] = s[ls] + s[rs];
    }
    inline void edt(int &x, int l, int r, int ps, int d) {
        if(!x) x = ++siz;
        if(l == r) {
            s[x] = 1;
            return;
        }
        int mid = l+r>>1;
        if(ps <= mid) edt(ls, l, mid, ps, d);
        else edt(rs, mid+1, r, ps, d);
        up(x);
    }
    inline int sum(int x, int l, int r, int L, int R) {
        if(!x || L>R) return 0;
        if(L <= l && r <= R) return s[x];
        int mid = l+r>>1, ret = 0;
        if(L <= mid) ret += sum(ls, l, mid, L, R);
        if(R > mid) ret += sum(rs, mid+1, r, L, R);
        return ret;
    }
    inline int merge(int x, int y, int l, int r) {
        if(!x || !y) return x+y;
        if(l == r) {
            s[x] += s[y];
            return x;
        }
        int mid = l+r>>1;
        ls = merge(ch[x][0], ch[y][0], l, mid);
        rs = merge(ch[x][1], ch[y][1], mid+1, r);
        up(x);
        return x;
    }
}T;

int ans[N];
inline void dfs(int x) {
    for (int i=head[x]; i; i=nxt[i]) {
        dfs(to[i]);
        rt[x] = T.merge(rt[x], rt[to[i]], 1, n);
    }
    ans[x] = T.sum(rt[x], 1, n, a[x] + 1, n);
}

int main() {
    cin >> n; T.set();
    for (int i=1; i<=n; ++i) {
        scanf("%d", a+i);
        ps.push_back(a[i]);
    }
    sort(ps.begin(), ps.end());
    ps.erase(unique(ps.begin(), ps.end()), ps.end());
    for (int i=1; i<=n; ++i) a[i] = lower_bound(ps.begin(), ps.end(), a[i]) - ps.begin() + 1;
    for (int i=2, par; i<=n; ++i) {
        scanf("%d", &par);
        add(par, i);
    }
    for (int i=1; i<=n; ++i) T.edt(rt[i], 1, n, a[i], 1);
    
    dfs(1);
    
    for (int i=1; i<=n; ++i) printf("%d\n", ans[i]);
    return 0;
}



      
View Code

线段树:codevs4927 2A 8min

warning: 区间覆盖后线清空tag标记,然后再传下来的tag标记是在cov之后的,所以要先传cov再传tag

技术分享
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h>

# ifdef WIN32
# define LLD "%I64d"
# else
# define LLD "%lld"
# endif

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = 1e5 + 10, SN = 262144 + 5;
const int mod = 1e9+7;

int n, m;
ll a[N];

struct SMT {
    ll s[SN], mx[SN], mi[SN], tag[SN], cov[SN]; bool hc[SN];
    # define ls (x<<1)
    # define rs (x<<1|1)
    inline void up(int x) {
        s[x] = s[ls] + s[rs];
        mx[x] = max(mx[ls], mx[rs]);
        mi[x] = min(mi[ls], mi[rs]);
    }
    inline void pushtag(int x, int l, int r, ll tg) {
        tag[x] += tg; s[x] += tg*(r-l+1);
        mx[x] += tg, mi[x] += tg;
    }
    inline void pushcov(int x, int l, int r, ll tg) {
        tag[x] = 0; hc[x] = 1; cov[x] = tg;
        mx[x] = mi[x] = tg; s[x] = tg * (r-l+1);
    }
    inline void down(int x, int l, int r) {
        int mid = l+r>>1;
        if(hc[x]) {
            pushcov(ls, l, mid, cov[x]);
            pushcov(rs, mid+1, r, cov[x]);
            cov[x] = hc[x] = 0;
        }
        if(tag[x]) {
            pushtag(ls, l, mid, tag[x]);
            pushtag(rs, mid+1, r, tag[x]);
            tag[x] = 0;
        }
    }
    inline void build(int x, int l, int r) {
        tag[x] = cov[x] = hc[x] = 0;
        if(l == r) {
            mx[x] = mi[x] = s[x] = a[l];
            return ;
        }
        int mid = l+r>>1;
        build(ls, l, mid); build(rs, mid+1, r);
        up(x);
    }
    inline void edt(int x, int l, int r, int L, int R, ll p) {
        if(L <= l && r <= R) {
            pushtag(x, l, r, p);
            return ;
        }
        down(x, l, r);
        int mid = l+r>>1;
        if(L <= mid) edt(ls, l, mid, L, R, p);
        if(R > mid) edt(rs, mid+1, r, L, R, p);
        up(x);
    }
    inline void cover(int x, int l, int r, int L, int R, ll p) {
        if(L <= l && r <= R) {
            pushcov(x, l, r, p);
            return ;
        }
        down(x, l, r);
        int mid = l+r>>1;
        if(L <= mid) cover(ls, l, mid, L, R, p);
        if(R > mid) cover(rs, mid+1, r, L, R, p);
        up(x);
    }
    inline ll sum(int x, int l, int r, int L, int R) {
        if(L <= l && r <= R) return s[x];
        down(x, l, r);
        int mid = l+r>>1; ll ret = 0;
        if(L <= mid) ret += sum(ls, l, mid, L, R);
        if(R > mid) ret += sum(rs, mid+1, r, L, R);
        return ret;
    }    
    inline ll gmax(int x, int l, int r, int L, int R) {
        if(L <= l && r <= R) return mx[x];
        down(x, l, r);
        int mid = l+r>>1;
        if(R <= mid) return gmax(ls, l, mid, L, R);
        else if(L > mid) return gmax(rs, mid+1, r, L, R);
        else return max(gmax(ls, l, mid, L, R), gmax(rs, mid+1, r, L, R));
    }    
    inline ll gmin(int x, int l, int r, int L, int R) {
        if(L <= l && r <= R) return mi[x];
        down(x, l, r);
        int mid = l+r>>1;
        if(R <= mid) return gmin(ls, l, mid, L, R);
        else if(L > mid) return gmin(rs, mid+1, r, L, R);
        else return min(gmin(ls, l, mid, L, R), gmin(rs, mid+1, r, L, R));
    }    
}T;

int main() {
    register int Q, x, y, z;
    register char op[23];
    cin >> n >> Q;
    for (int i=1; i<=n; ++i) scanf(LLD, a+i);
    T.build(1, 1, n);
    while(Q--) {
        scanf("%s%d%d", op, &x, &y);
        if(op[1] == d) {
            scanf(LLD, &z);
            T.edt(1, 1, n, x, y, z);
        }
        else if(op[1] == e) {
            scanf(LLD, &z);
            T.cover(1, 1, n, x, y, z);
        }
        else if(op[1] == u) printf(LLD "\n", T.sum(1, 1, n, x, y));
        else if(op[1] == a) printf(LLD "\n", T.gmax(1, 1, n, x, y));
        else printf(LLD "\n", T.gmin(1, 1, n, x, y));
    }
    return 0;
}
View Code

 

模板复习【updating】