洛谷P2146 [NOI2015]软件包管理器

题目

树链剖分

安装操作：

将1到x的点权统统_覆盖_为1，操作前覆盖一次，操作后覆盖一次。然后分别记录这两次1到x的路径点权和，求他们的差即是答案。

卸载操作：
输出x的子树点权值和，然后把x的子树点权统统_覆盖_为0。

覆盖操作可以用ODT，线段树，线段树的lazy数组初始值要赋为-1，因为有区间赋值为0的操作。

#include <bits/stdc++.h>
#define N 1000115
#define ls l, mid, root << 1
#define rs mid + 1, r, root << 1 | 1 
using namespace std;
int n, m, tot, cnt, lin[N], dep[N], fat[N], siz[N], son[N], top[N], dfn[N], tree[N], lazy[N];
struct edg {
    int to, nex;
}e[N];
inline void add(int f, int t)
{
    e[++cnt].nex = lin[f];
    e[cnt].to = t;
    lin[f] = cnt;
}
void dfs1(int now, int fa)
{
    dep[now] = dep[fa] + 1;
    fat[now] = fa;
    siz[now] = 1; 
    for (int i = lin[now]; i; i = e[i].nex)
    {
        int to = e[i].to;
        if (to == fa) continue;
        dfs1(to, now);
        siz[now] += siz[to];
        if (siz[to] > siz[son[now]])
            son[now] = to;
    }
}
void dfs2(int now, int tes)
{
    top[now] = tes;
    dfn[now] = ++tot;//dfn是dfs序 
    if (!son[now]) return; 
    dfs2(son[now], tes);
    for (int i = lin[now]; i; i = e[i].nex)
    {
        int to = e[i].to;
        if (to == fat[now] || to == son[now]) continue;
        dfs2(to, to);
    }
}
inline void pushup(int root)
{
    tree[root] = tree[root << 1] + tree[root << 1 | 1];
}
inline void pushdown(int l, int r, int root)
{
    if (lazy[root] != -1)
    {
        int mid = (l + r) >> 1;
    lazy[root << 1] = lazy[root]; lazy[root << 1 | 1] = lazy[root]; 
    tree[root << 1] = (mid - l + 1) * lazy[root], tree[root << 1 | 1] = (r - mid) * lazy[root];
    lazy[root] = -1;    
    }
    
}
void build(int l, int r, int root)
{
    if (l == r)
    {
        tree[root] = 0;
        lazy[root] = -1;
        return;
    }
    int mid = (l + r) >> 1;
    build(ls), build(rs);
    pushup(root);
}
void update(int ql, int qr, int add, int l, int r, int root)
{
    if (ql <= l && r <= qr)
    {
        tree[root] = (r - l + 1) * add;//此处为赋值操作 
        lazy[root] = add;
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(l, r, root);
    if (ql <= mid)
        update(ql, qr, add, ls);
    if (qr > mid)
        update(ql, qr, add, rs);
    pushup(root);
}
int query(int ql, int qr, int l, int r, int root)
{
    int res = 0;
    if (ql <= l && r <= qr)
        return tree[root];
    int mid = (l + r) >> 1;
    pushdown(l, r, root);
    if (ql <= mid) 
        res += query(ql, qr, ls);
    if (qr > mid) 
        res += query(ql, qr, rs);
    return res;
}
int Q(int a, int b)//a, b的路径 
{
    int res = 0;
    while (top[a] != top[b])
    {
        if (dep[top[a]] < dep[top[b]])
            swap(a, b);
        res += query(dfn[top[a]], dfn[a], 1, n, 1);
        a = fat[top[a]];//处理了一个链。 
    }
    if (dep[a] > dep[b]) swap(a, b);
    res += query(dfn[a], dfn[b], 1, n, 1);
    return res;
}   
void U(int a, int b)
{
    while (top[a] != top[b])
    {
        if (dep[top[a]] < dep[top[b]])
            swap(a, b);
        update(dfn[top[a]], dfn[a], 1, 1, n, 1);
        a = fat[top[a]];//处理了一个链。 
    }
    if (dep[a] > dep[b]) swap(a, b);
    update(dfn[a], dfn[b], 1, 1, n, 1);
} 
int main()
{
//in:先输出0到他的路径边权和，安装是将其路径上的所有边权变为1，
//un:求出子树得值，将他的子树全都赋为一个数，求出子树的值，将他的子树全都赋为一个数 
    scanf("%d", &n);
    for (int i = 2, a; i <= n; i++)
        scanf("%d", &a), add(a + 1, i), add(i, a + 1);//先使所有点的编号加1
    dfs1(1, 0);
    dfs2(1, 1);
    scanf("%d", &m);
    while (m--)
    {
        string s; int a;
        cin >> s; scanf("%d", &a);
        a++; 
        if (s[0] == 'i')//安装 
        {   
            int a1 = Q(1, a);//查询1到他的路径和。
            U(1, a);//更改1，a的路径和统统赋为1。
            int a2 = Q(1, a);
            printf("%d\n", a2 - a1);
        }
        else
        {
            printf("%d\n", query(dfn[a], dfn[a] + siz[a] - 1, 1, n, 1));//查询子树的和 
            update(dfn[a], dfn[a] + siz[a] - 1, 0, 1, n, 1); 
        } 
    }
    return 0;
}

洛谷P2146 [NOI2015]软件包管理器

原文：https://www.cnblogs.com/liuwenyao/p/11805886.html