BZOJ 1146: [CTSC2008]网络管理 – [树套树/主席树]


题目传送门(BZOJ)
>原文链接<

题解 :

带修主席树,考虑树状数组套主席树

考虑不带修改怎么做 :

维护一棵主席树, 树上每个点的信息从父节点继承而来

这样, 在查询路径(a, b)的信息时, 查询Tree[a]+Tree[b]-Tree[LCA(a, b)]-Tree[fa[LCA(a, b)]]就行了

这是一个常见的套路, 就是简单的前缀和思想, 因为我们在这里用主席树维护的本来就是一个前缀信息

由于有了修改, 我们还要加上树状数组

考虑一个点权值改变,只会对它子树中所有点的信息产生影响,

dfn[p]odn[p],

前者是DFS序上p的标号,后者是退出p时, 当前标号记录到哪,也就是子树中dfn最大的节点的dfn

考虑一次修改 : 把p的权值从x改到y

相当于在dfn[p]\to n这段区间中减去一次权值x, 再加上一次权值y

再把oud[p]\to n这段区间加上一次权值x , 再减去一次权值y ,

因为刚刚的修改本来和这些节点无关,他们是多加/多减的

区间对主席树的修改, 就用树状数组维护即可.

代码实现还是略有复杂的, 但是思路清晰的话, 没有什么特别难以理解的地方

要把适合于什么时候做的操作放到该在的时候

代码 :

#include 
#include 
#include 
#include 
using namespace std;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)
#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)
#define rep(i, a, b) for(int i = a; i <= b; i ++ )
char buf[100000],*p1,*p2;
inline int rd() {
    int x = 0; char ch = nc();
    while(!isdigit(ch)) ch = nc();
    while(isdigit(ch)) x = (x<<1) + (x<<3) + (ch^48), ch = nc();
    return x;
}
const int N = 81000;
const int INF = 1e9;
struct Edge {
    int to;
    Edge *next;
}*h[N],e[N<<1];
int val[N], siz[N], son[N], dep[N], fa[N], top[N];
int dfn[N], odn[N], qrx[N], qry[N], qrz[N], qrw[N];
int t[N<<8], ls[N<<8], rs[N<<8], root[N], n, m;
inline void Add_Edge(int u, int v) {
    static int _;
    Edge *tmp = &e[++_];
    tmp->to = v;
    tmp->next = h[u];
    h[u] = tmp;
}
void insert(int l, int r, int &p, int x, int c) {
    static int _;
    if(!p) p = ++_;
    t[p] += c;
    if(l == r) return ;
    int mi = (l+r) >> 1;
    if(x <= mi) insert(l, mi, ls[p], x, c);
    else insert(mi+1, r, rs[p], x, c);
}
void dfs(int p) {
    dep[p] = dep[fa[p]]+1; siz[p] = 1; dfn[p] = ++*dfn;
    for(int i = dfn[p]; i <= n; i += i&-i ) insert(0, INF, root[i], val[p], 1);
    rev(i, p) {
        if(i->to != fa[p]) {
            fa[i->to] = p;
            dfs(i->to);
            if(siz[i->to] > siz[son[p]]) son[p] = i->to;
            siz[p] += siz[i->to];
        }
    }
    for(int i = *dfn+1; i <= n; i += i&-i ) insert(0, INF, root[i], val[p], -1);
    odn[p] = *dfn+1;
}
void dfs(int p, int t) {
    top[p] = t;
    if(son[p]) dfs(son[p], t);
    rev(i, p) if(i->to != son[p] && i->to != fa[p]) dfs(i->to, i->to);
}
int lca(int x, int y) {
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}
int inq(int l, int r, int k) {
    if(l == r) return l;
    int mi = (l+r) >> 1, sizl = 0;
    for(int i = 1; i <= *qrx; i ++ ) sizl += t[ls[qrx[i]]];
    for(int i = 1; i <= *qry; i ++ ) sizl += t[ls[qry[i]]];
    for(int i = 1; i <= *qrz; i ++ ) sizl -= t[ls[qrz[i]]];
    for(int i = 1; i <= *qrw; i ++ ) sizl -= t[ls[qrw[i]]];
    if(k <= sizl) {
        for(int i = 1; i <= *qrx; i ++ ) qrx[i] = ls[qrx[i]];
        for(int i = 1; i <= *qry; i ++ ) qry[i] = ls[qry[i]];
        for(int i = 1; i <= *qrz; i ++ ) qrz[i] = ls[qrz[i]];
        for(int i = 1; i <= *qrw; i ++ ) qrw[i] = ls[qrw[i]];
        return inq(l, mi, k);
    }
    else {
        for(int i = 1; i <= *qrx; i ++ ) qrx[i] = rs[qrx[i]];
        for(int i = 1; i <= *qry; i ++ ) qry[i] = rs[qry[i]];
        for(int i = 1; i <= *qrz; i ++ ) qrz[i] = rs[qrz[i]];
        for(int i = 1; i <= *qrw; i ++ ) qrw[i] = rs[qrw[i]];
        return inq(mi+1, r, k-sizl);
    }
}
int main() {
    n = rd(), m = rd();
    for(int i = 1; i <= n; i ++ ) val[i] = rd();
    for(int i = 2; i <= n; i ++ ) {
        int u = rd(), v = rd();
        Add_Edge(u, v), Add_Edge(v, u);
    }
    dfs(1), dfs(1, 1);
    while(m -- ) {
        int k = rd(), x = rd(), y = rd();
        if(!k) {
            for(int i = dfn[x]; i <= n ; i += i&-i ) insert(0, INF, root[i], val[x], -1);
            for(int i = odn[x]; i <= n ; i += i&-i ) insert(0, INF, root[i], val[x], 1);
            val[x]=y;
            for(int i = dfn[x]; i <= n ; i += i&-i ) insert(0, INF, root[i], val[x], 1);
            for(int i = odn[x]; i <= n ; i += i&-i ) insert(0, INF, root[i], val[x], -1);
        }
        else {
            *qrx = *qry = *qrz = *qrw = 0;
            int l = lca(x, y), f = fa[l];
            int len = dep[x]+dep[y]-dep[l]-dep[f];
            if(len < k) puts("invalid request!");
            else {
                k = len-k+1;
                for(int i = dfn[x]; i; i -= i&-i) qrx[++*qrx] = root[i];
                for(int i = dfn[y]; i; i -= i&-i) qry[++*qry] = root[i];
                for(int i = dfn[l]; i; i -= i&-i) qrz[++*qrz] = root[i];
          if(f) for(int i = dfn[f]; i; i -= i&-i) qrw[++*qrw] = root[i];
                printf("%d\n", inq(0, INF, k));
            }
        }
    }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注