P2146 [NOI2015] 软件包管理器

每天一道树剖，防止抑郁。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 1e5 + 5, M = 1e5 + 5;;
int n;

class SegmentTree {
#define MID int mid = (l + r) >> 1
#define lson l, mid, x << 1
#define rson mid + 1, r, x << 1 | 1
public :
    static const int N = ::N;
    int sum[N << 2], ass[N << 2];

    SegmentTree() {
        ms(sum); 
        memset(ass, -1, sizeof ass);
    }

    void push_up(int x) {
        sum[x] = sum[x << 1] + sum[x << 1 | 1];
    }

    void push_down(int l, int r, int x) {
        if(ass[x] == -1) return ;
        MID;
        sum[x << 1] = (mid - l + 1) * ass[x];
        sum[x << 1 | 1] = (r - mid) * ass[x];
        ass[x << 1] = ass[x];
        ass[x << 1 | 1] = ass[x];
        ass[x] = -1;
    }

    void modify_assign(int l, int r, int x, int p, int q, int v) {
        if(p <= l && r <= q) {
            sum[x] = (r - l + 1) * v;
            ass[x] = v;
            return ;
        }
        MID; push_down(l, r, x);
        if(p <= mid) modify_assign(lson, p, q, v);
        if(q > mid) modify_assign(rson, p, q, v);
        push_up(x);
    }

    int query(int l, int r, int x, int p, int q) {
        if(p <= l && r <= q) {
            return sum[x];
        }
        MID; push_down(l, r, x);
        int res = 0;
        if(p <= mid) res += query(lson, p, q);
        if(q > mid) res += query(rson, p, q);
        return res;
    }
} st;

struct Edge {
    int to, nxt;
} Edge[M << 1];

int head[N], cnt;

void addEdge(int u, int v) {
    Edge[++cnt].to = v;
    Edge[cnt].nxt = head[u];
    head[u] = cnt;
}

int dep[N], id[N], top[N], sz[N], fa[N], hs[N], idx;

void dfs1(int u, int d, int depth) {
    dep[u] = depth; sz[u] = 1; fa[u] = d; int mx = 0;
    for(int i = head[u]; ~i; i = Edge[i].nxt) {
        const int v = Edge[i].to;
        if(v == d) continue;
        dfs1(v, u, depth + 1);
        sz[u] += sz[v];
        if(sz[v] > mx) mx = sz[v], hs[u] = v;
    }
}

void dfs2(int u, int tf) {
    id[u] = ++idx; top[u] = tf;
    if(sz[u] == 1) return ;
    dfs2(hs[u], tf);
    for(int i = head[u]; ~i; i = Edge[i].nxt) {
        const int v = Edge[i].to; 
        if(v == hs[u] || v == fa[u]) continue;
        dfs2(v, v);
    }
}

int qRange(int x) {
    int res = 0;
    while(top[x] != 0) {
        res += st.query(1, n, 1, id[top[x]], id[x]);
        x = fa[top[x]];
    }
    return res + st.query(1, n, 1, 1, id[x]);
}

void uRange(int x, int v) {
    while(top[x] != 0) {
        st.modify_assign(1, n, 1, id[top[x]], id[x], v);
        x = fa[top[x]];
    }
    st.modify_assign(1, n, 1, 1, id[x], v);
}

signed main() {
#ifdef LOCAL
    file();
#endif
    memset(head, -1, sizeof head);
    n = rd();
    for(int i = 1; i < n; i++) {
        int v = rd();
        addEdge(i, v); addEdge(v, i);
    }

    dfs1(0, 0, 1);
    dfs2(0, 0);

    int m = rd();
    for(int i = 1; i <= m; i++) {
        char opt[13];
        scanf("%s", opt + 1);
        int x = rd();
        if(opt[1] == 'i') {
            if(st.query(1, n, 1, id[x], id[x]) == 1) {
                puts("0");
            } else {
                printf("%d\n",dep[x] - qRange(x));
                uRange(x, 1);
            }
        } else if(opt[1] == 'u') {
            if(st.query(1, n, 1, id[x], id[x]) == 0) {
                puts("0");
            } else {
                printf("%d\n", st.query(1, n, 1, id[x], id[x] + sz[x] - 1));
                st.modify_assign(1, n, 1, id[x], id[x] + sz[x] - 1, 0);
            }
        }
    }

    return 0;
}

P3372 【模板】线段树 1

ver. 标记永久化

若一个区间能被完美覆盖则 add[x] += v

若不能被完美覆盖则 sum[x] += (min(r, q) - max(l, p) + 1) * v

统计时若完美覆盖则返回该区间被完美覆盖和非完美覆盖之和 return sum[x] + (r - l + 1) * add[x]

若不完美覆盖则在加上该区间被完美覆盖的值并递归查询 res += (min(r, q) - max(l, p) + 1) * add[x]

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define dd(x) cerr << #x << endl
#define ms(x) memset(x, 0, sizeof x)
#define int long long
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

class SegmentTree {
#define MID int mid = (l + r) >> 1
#define lson l, mid, x << 1
#define rson mid + 1, r, x << 1 | 1
public:
    static const int N = 1e5 + 5;
    int sum[N << 2], add[N << 2];

    SegmentTree() {
        ms(sum);
        ms(add);
    }

    void build(int l, int r, int x) {
        if(l == r) {
            sum[x] = rd();
            return ;
        }
        MID; 
        build(lson); build(rson);
        sum[x] = sum[x << 1] + sum[x << 1 | 1];
    }

    void modify_add(int l, int r, int x, int p, int q, int v) {
        if(p <= l && r <= q) {
            add[x] += v;
            return ;
        }
        MID;
        sum[x] += (min(r, q) - max(l, p) + 1) * v;
        if(p <= mid) modify_add(lson, p, q, v);
        if(q > mid) modify_add(rson, p, q, v);
    }

    int query(int l, int r, int x, int p, int q) {
        if(p <= l && r <= q) {
            return sum[x] + add[x] * (r - l + 1);
        }
        MID; 
        int res = (min(r, q) - max(l, p) + 1) * add[x];
        if(p <= mid) res += query(lson, p, q);
        if(q > mid) res += query(rson, p, q);
        return res;
    }
} st;

signed main() {
    int n, m; cin >> n >> m;
    st.build(1, n, 1);
    for(int i = 1; i <= m; i++) {
        int opt; cin >> opt;
        if(opt == 1) {
            int x, y, k; cin >> x >> y >> k;
            st.modify_add(1, n, 1, x, y, k);
        } else {
            int x, y; cin >> x >> y;
            cout << st.query(1, n, 1, x, y) << '\n';
        }
    }
    return 0;
}

HDU4348 To The Moon

区间加主席树，标记永久化实现。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
typedef long long ll;
ll rd() {
    ll f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("generated.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 1e5 + 5;

class SegmentTree {
#define MID int mid = (l + r) >> 1
#define lson l, mid, node[x].ls
#define rson mid + 1, r, node[x].rs
public :
    struct Node {
        int ls, rs; 
        ll sum, add;
    } node[N * 25];

    int root[N], cnt, now;

    SegmentTree() : cnt(0), now(0) { }

    void clear() {
        ms(node);
        cnt = 0, now = 0;
        ms(root);
    }

    int build(int l, int r) {
        int x = ++cnt;
        if(l == r) {
            node[x].sum = rd();
            return x;
        }
        MID;
        node[x].ls = build(l, mid);
        node[x].rs = build(mid + 1, r);
        node[x].sum = node[node[x].ls].sum + node[node[x].rs].sum;
        return x;
    }

    int clone(int x) {
        node[++cnt] = node[x];
        return cnt;
    }

    void modify_add(int l, int r, int &x, int p, int q, int v) {
        x = clone(x);
        if(p <= l && r <= q) {
            node[x].add += v;
            return ;
        }
        MID; 
        node[x].sum += 1LL * (min(r, q) - max(l, p) + 1) * v;
        if(p <= mid) modify_add(lson, p, q, v);
        if(q > mid) modify_add(rson, p, q, v);
    }

    ll query(int l, int r, int x, int p, int q) {
        if(p <= l && r <= q) {
            return 1LL * node[x].sum + 1LL * node[x].add * (r - l + 1);
        }
        MID; ll res = 1LL * (min(r, q) - max(l, p) + 1) * node[x].add;
        if(p <= mid) res += query(lson, p, q);
        if(q > mid) res += query(rson, p, q);
        return res;
    }

} st;

signed main() {
#ifdef LOCAL
    file();
#endif
    int n, m;
while(~scanf("%d%d", &n, &m)) {
    st.clear();
    st.root[0] = st.build(1, n);
    for(int i = 1; i <= m; i++) {
        char ch[4];
        scanf("%s", ch + 1);
        if(ch[1] == 'C') {
            int l = rd(), r = rd(), v = rd();
            ++st.now;
            st.root[st.now] = st.root[st.now - 1];
            st.modify_add(1, n, st.root[st.now], l, r, v);
        } else if(ch[1] == 'Q') {
            int l = rd(), r = rd();
            printf("%lld\n", st.query(1, n, st.root[st.now], l, r));
        } else if(ch[1] == 'H') {
            int l = rd(), r = rd(), t = rd();
            printf("%lld\n", st.query(1, n, st.root[t], l, r)); 
        } else if(ch[1] == 'B') {
            int t = rd();
            st.now = t;
        }
    }
}

    return 0;
}

P4781 【模板】拉格朗日插值

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
#define int long long
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int mod = 998244353, N = 1e5 + 5;

int qpow(int a, int b) {
    int base = a, res = 1;
    while(b) {
        if(b & 1) res = res * base % mod;
        base = base * base % mod; b >>= 1;
    }
    return res;
}

int inv(int t) {
    return qpow(t, mod - 2);
}

int positive(int x) {
    return (x % mod + mod) % mod;
}

int x[N], y[N];

signed main() {
#ifdef LOCAL
    file();
#endif
    int n = rd(), k = rd();
    for(int i = 1; i <= n; i++) {
        x[i] = rd(), y[i] = rd();
    }

    int ans = 0;
    for(int i = 1; i <= n; i++) {
        int fz = 1, fm = 1;
        for(int j = 1; j <= n; j++) {
            if(i == j) continue;
            fz = fz * positive(k - x[j]) % mod;
            fm = fm * positive(x[i] - x[j]) % mod;
        }
        fz = fz * inv(fm) % mod;
        ans += y[i] * fz % mod;
        ans %= mod;
    }

    cout << ans << endl;

    return 0;
}
最后修改：2021 年 01 月 23 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏