POJ 3237 /// 树链剖分线段树区间修改（*-1）

题目大意：

给定树的N个结点编号为1到N 给定N-1条边的边权。

三种操作：

CHANGE k w：将第 k 条边的权值改成 w。

NEGATE x y：将x到y的路径上所有边的权值乘 -1。

QUERY x y：找出x到y的路径上所有边的最大权值。

单点更新区间更新区间查询

由于第二个操作是乘 -1 所以需要同时维护最大值和最小值

所以 lazy用来标记是否乘-1 0表示不乘-1 1表示乘-1

http://www.cnblogs.com/HDUjackyan/p/9279777.html

#include <stdio.h>

#include <algorithm>

#include <cstring>

using namespace std;

#define INF 0x3f3f3f3f

#define mem(i,j) memset(i,j,sizeof(i))

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define root 1,n,1

const int maxn=1e4+;

int n;

struct IntervalTree {

    struct EDGE { int to,ne; }e[maxn<<];

    int head[maxn], tot;

    void addE(int u,int v) {

        e[tot].to=v;

        e[tot].ne=head[u];

        head[u]=tot++;

    }

    int fa[maxn], son[maxn], dep[maxn], num[maxn];

    int top[maxn], p[maxn], fp[maxn], pos;

    void init() {

        tot=; mem(head,);

        pos=; mem(son,);

    }

    struct TREE {

        int Max,Min,lazy;

    }tree[maxn<<];

// --------------------以下是线段树-------------------------

    void pushUp(int rt) {

        tree[rt].Max=max(tree[rt<<].Max,tree[rt<<|].Max);

        tree[rt].Min=min(tree[rt<<].Min,tree[rt<<|].Min);

    }

    void pushDown(int rt,int m) {

        if(m==) return;

        if(tree[rt].lazy) {

            tree[rt<<].Max*=-;

            tree[rt<<].Min*=-;

            tree[rt<<].lazy^=;

            tree[rt<<|].Max*=-;

            tree[rt<<|].Min*=-;

            tree[rt<<|].lazy^=;

            swap(tree[rt<<].Max,tree[rt<<].Min);

            swap(tree[rt<<|].Max,tree[rt<<|].Min);

            tree[rt].lazy=;

        }

    }

    void build(int l,int r,int rt) {

        if(l==r) {

            tree[rt].Max=tree[rt].Min=tree[rt].lazy=;

            return;

        }

        int m=(l+r)>>;

        build(lson), build(rson);

        pushUp(rt);

    }

    void update1(int k,int w,int l,int r,int rt) {

        if(l==r) {

            tree[rt].Max=tree[rt].Min=w;

            tree[rt].lazy=;

            return;

        }

        pushDown(rt,r-l+);

        int m=(l+r)>>;

        if(k<=m) update1(k,w,lson);

        else update1(k,w,rson);

        pushUp(rt);

    }

    void update2(int L,int R,int l,int r,int rt) {

        if(L<=l && r<=R) {

            tree[rt].Max*=-;

            tree[rt].Min*=-;

            tree[rt].lazy^=;

            swap(tree[rt].Max,tree[rt].Min);

            return ;

        }

        pushDown(rt,r-l+);

        int m=(l+r)>>;

        if(L<=m) update2(L,R,lson);

        if(R>m) update2(L,R,rson);

        pushUp(rt);

    }

    int query(int L,int R,int l,int r,int rt) {

        if(L<=l && r<=R) return tree[rt].Max;

        pushDown(rt,r-l+);

        int m=(l+r)>>, res=-INF;

        if(L<=m) res=max(res,query(L,R,lson));

        if(R>m) res=max(res,query(L,R,rson));

        pushUp(rt);

        return res;

    }

// --------------------以上是线段树-------------------------

// --------------------以下是树链剖分-------------------------

    void dfs1(int u,int pre,int d) {

        dep[u]=d; fa[u]=pre; num[u]=;

        for(int i=head[u];i;i=e[i].ne) {

            int v=e[i].to;

            if(v!=fa[u]) {

                dfs1(v,u,d+);

                num[u]+=num[v];

                if(!son[u] || num[v]>num[son[u]])

                    son[u]=v;

            }

        }

    }

    void dfs2(int u,int sp) {

        top[u]=sp; p[u]=++pos; fp[p[u]]=u;

        if(!son[u]) return;

        dfs2(son[u],sp);

        for(int i=head[u];i;i=e[i].ne) {

            int v=e[i].to;

            if(v!=son[u] && v!=fa[u])

                dfs2(v,v);

        }

    }

    int queryPath(int x,int y) {

        int fx=top[x], fy=top[y], ans=-INF;

        while(fx!=fy) {

            if(dep[fx]>dep[fy]) {

                ans=max(ans,query(p[fx],p[x],root));

                x=fa[fx];

            } else {

                ans=max(ans,query(p[fy],p[y],root));

                y=fa[fy];

            }

            fx=top[x], fy=top[y];

        }

        if(x==y) return ans;

        if(dep[x]>dep[y]) swap(x,y);

        return max(ans,query(p[son[x]],p[y],root));

    }

    void updatePath(int x,int y) {

        int fx=top[x], fy=top[y];

        while(fx!=fy) {

            if(dep[fx]>dep[fy]) {

                update2(p[fx],p[x],root);

                x=fa[fx];

            } else {

                update2(p[fy],p[y],root);

                y=fa[fy];

            }

            fx=top[x], fy=top[y];

        }

        if(x==y) return ;

        if(dep[x]>dep[y]) swap(x,y);

        update2(p[son[x]],p[y],root);

    }

// --------------------以上是树链剖分-------------------------

    void initQTree() {

        dfs1(,,), dfs2(,);

        build(root);

    }

}T;

int E[maxn][];

int main()

{

    int t; scanf("%d",&t);

    while(t--) {

        scanf("%d",&n);

        T.init();

        for(int i=;i<n;i++) {

            int u,v,w; scanf("%d%d%d",&u,&v,&w);

            E[i][]=u, E[i][]=v, E[i][]=w;

            T.addE(u,v), T.addE(v,u);

        }

        T.initQTree();

        for(int i=;i<n;i++) {

            if(T.dep[E[i][]]>T.dep[E[i][]])

                swap(E[i][],E[i][]); //puts("OK");

            T.update1(T.p[E[i][]],E[i][],root);

        }

        while() {

            char s[]; scanf("%s",s);

            if(s[]=='D') break;

            int x,y; scanf("%d%d",&x,&y);

            if(s[]=='Q')

                printf("%d\n",T.queryPath(x,y));

            else if(s[]=='C')

                T.update1(T.p[E[x][]],y,root);

            else if(s[]=='N')

                T.updatePath(x,y);

        }

    }

    return ;

}

巴特西

POJ 3237 /// 树链剖分线段树区间修改（*-1）

最新文章

热门文章

巴特西

POJ 3237 /// 树链剖分 线段树区间修改（*-1）

最新文章

热门文章

POJ 3237 /// 树链剖分线段树区间修改（*-1）