P2486 [SDOI2011]染色（树剖）区间覆盖+区间的连续段

时间：2023-02-04 20:49:37

https://www.luogu.org/problemnew/show/P2486

值的一看https://www.cnblogs.com/Tony-Double-Sky/p/9283262.html

P2486 [SDOI2011]染色（树剖）区间覆盖+区间的连续段

分析：

树剖后，线段树要记录左端点l,右端点r，左端点的颜色lc,右端点的颜色rc,区间成段更新的标记tag,区间

有多少颜色段。区间合并的时候要注意如果左子树的右端和右子树的左端颜色相同那么数量要减一。但是存在一个问题当前剖到

的链与上一次的链在相交的边缘可能颜色相同，如果颜色相同答案需要减一。所以统计答案的时候要记录下上一次剖到的链的左端

点的颜色，与当前剖到的链右端点的颜色（因为在处理出的线段树中越靠近根的点位置越左）->（上一个链的终点与当前链的起点比较），比较这两个颜色，若相同则答案减

1。又由于有u和v两个位置在向上走，那么要记录ans1，ans2两个变量来存“上一次的左端点颜色”。有一点需要注意，当

top[u]=top[v]的时候，即已经在同一个重链上时，两边端点颜色都要考虑与对应ans比较颜色，相同答案要相应减一

#include<bits/stdc++.h>

using namespace std;

const int maxn = ;

vector<int>G[maxn];

int n , q ,cnt;

int siz[maxn] , wson[maxn],dep[maxn],fa[maxn],top[maxn],pos[maxn],ori[maxn];

void dfs1(int id , int F)

{

    siz[id]=;

    for(int i= ; i<G[id].size() ; i++)

    {

        int v=G[id][i];

        if(v==F) continue;

        dep[v] = dep[id] + ;

        fa[v] = id;

        dfs1(v,id);

        siz[id] += siz[v];

        if(siz[v] > siz[wson[id]]) wson[id] = v;

    }

}

void dfs2(int id , int TP)

{

    top[id] = TP;

    pos[id] = ++cnt;

    ori[cnt]=id;

    if(!wson[id]) return ;

    dfs2(wson[id],TP);

    for(int i= ; i<G[id].size() ; i++)

    {

        int v=G[id][i];

        if(v==fa[id] || v==wson[id]) continue;

        dfs2(v,v);

    }

}

int lc[maxn<<] , rc[maxn<<],col[maxn];

#define lson (id<<1)

#define rson (id<<1) | 1

struct no

{

    int l,r;

    int sum,c;///区间颜色总数 ， 叶子颜色

    int lazy;///儿子的颜色

}tree[maxn<<];

void build(int id , int l , int r)

{

    tree[id].l=l;

    tree[id].r=r;

    if(l==r)

    {

        tree[id].c=col[ori[l]];//赋值：叶子颜色

        lc[id]=rc[id]=col[ori[l]];//赋值：区间左颜色和区间右颜色

        tree[id].sum=;//颜色数为1

        return ;

    }

    int mid = (l+r)>>;

    build(lson , l , mid);

    build(rson , mid+ , r);

    tree[id].sum = tree[lson].sum + tree[rson].sum;

    if(rc[lson] == lc[rson]) tree[id].sum-=;

    lc[id] = lc[lson];

    rc[id] = rc[rson];

}

void pushdown(int id)

{

    if(tree[id].lazy!= && tree[id].l != tree[id].r)

    {

        int c=tree[id].lazy;

        tree[lson].lazy = tree[rson].lazy=c;

        tree[lson].c = tree[rson].c = c;

        lc[lson]=lc[rson]=rc[lson]=rc[rson]=c;

        tree[lson].sum = tree[rson].sum=;

        tree[id].lazy=;

    }

}

void update(int id ,int c , int l , int r)

{

    pushdown(id);

    if(tree[id].l == l && tree[id].r==r)

    {

        tree[id].c=c;

        tree[id].lazy=c;

        tree[id].sum=;

        lc[id]=rc[id]=c;

        return ;

    }

    int mid=tree[id].l + tree[id].r >> ;

    if(mid < l)

        update(rson,c,l,r);

    else if(mid>=r)

        update(lson,c,l,r);

    else

    {

        update(lson,c,l,mid);

        update(rson,c,mid+,r);

    }

    tree[id].sum=tree[lson].sum+tree[rson].sum;

    if(rc[lson]==lc[rson]) tree[id].sum-=;

    lc[id]=lc[lson];

    rc[id]=rc[rson];

}

int query(int id , int l , int r)

{

    pushdown(id);

    if(tree[id].l == l && tree[id].r==r)

    {

        return tree[id].sum;

    }

    int mid=(tree[id].l + tree[id].r) >>;

    if(mid < l)

        return query(rson,l,r);

    else if(mid >=r)

        return query(lson,l,r);

    else

    {

        int ret = query(lson,l,mid) + query(rson,mid+,r);

        if(rc[lson]==lc[rson]) ret-=;

        return ret;

    }

}

int Qc(int id , int l ,int r)

{

    pushdown(id);

    if(tree[id].l==l && tree[id].r==r)

    {

        return tree[id].c;

    }

    int mid=tree[id].l + tree[id].r >>;

    if(mid < l) return Qc(rson,l,r);

    else return Qc(lson,l,r);

}

void uprange(int x , int y , int c)

{

    while(top[x]!=top[y])

    {

        if(dep[top[x]] < dep[top[y]]) swap(x,y);

        update(,c,pos[top[x]],pos[x]);

        x=fa[top[x]];

    }

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

    update(,c,pos[x],pos[y]);

}

int Qsum(int x , int y)

{

    int ans=,Cson,Cfa;

    while(top[x] != top[y])

    {

        if(dep[top[x]] < dep[top[y]]) swap(x,y);

        ans+=query(,pos[top[x]],pos[x]);

        Cson=Qc(,pos[top[x]],pos[top[x]]);

        Cfa=Qc(,pos[fa[top[x]]] , pos[fa[top[x]]]);

        if(Cson==Cfa) ans-=;

        x=fa[top[x]];

    }

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

    ans+=query(,pos[x] , pos[y]);

    return ans;

}

int main()

{

    scanf("%d%d",&n,&q);

    for(int i= ; i<=n ; i++) scanf("%d",&col[i]);

    int u,v;

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

    {

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

        G[u].push_back(v);

        G[v].push_back(u);

    }

    dfs1(,-);

    dfs2(,);

    build(,,n);

    char ask;

    int c;

    while(q--)

    {

        cin>>ask;

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

        if(ask=='Q')

        {

            printf("%d\n",Qsum(u,v));

        }

        else

        {

            scanf("%d",&c);

            uprange(u,v,c);

        }

    }

}

优秀代码：

#include<bits/stdc++.h>

using namespace std;

int n,m;

const int maxn=;

struct treeno

{

    int sum,rc,lc,l,r,c;

}t[maxn<<];

int b[maxn],dep[maxn],fa[maxn],sze[maxn],son[maxn],id[maxn],w[maxn],top[maxn];

int cnt,lcol,rcol;

vector<int>L[maxn];

void pushcol(int rt , int col)

{

    t[rt].lc=t[rt].rc=col;

    t[rt].sum=;t[rt].c=col;

}

void update(int rt)

{

    t[rt].sum=t[rt<<].sum + t[rt<<|].sum;

    if(t[rt<<].rc==t[rt<<|].lc)

    t[rt].sum--;

    t[rt].lc=t[rt<<].lc;

    t[rt].rc=t[rt<<|].rc;

}

void pushdown(int rt)

{

    if(t[rt].c)

    {

        if(rt<<) pushcol(rt<<,t[rt].c);

        if(rt<<|) pushcol(rt<<|,t[rt].c);

        t[rt].c=;

    }

}

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

{

    t[rt].l=l ,t[rt].r=r;

    if(l==r)

    {

        t[rt].lc=t[rt].rc=b[l];

        t[rt].sum=;

        return ;

    }

    int mid=(l+r)>>;

    build(rt<<,l,mid);

    build(rt<<|,mid+,r);

    update(rt);

}

int query(int rt , int L , int R)

{

    int l=t[rt].l , r=t[rt].r;

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

    {

        if(l==L) lcol=t[rt].lc;

        if(r==R) rcol=t[rt].rc;

        return t[rt].sum;

    }

    pushdown(rt);

    int mid=(l+r)>>;

    if(R<=mid) return query(rt<<,L,R);

    if(L>mid) return query(rt<<|,L,R);

    int ret=query(rt<<,L,R)+query(rt<<|,L,R);

    if(t[rt<<].rc==t[rt<<|].lc) --ret;

    return ret;

}

void modify(int rt , int L , int R , int x)

{

    int l=t[rt].l , r=t[rt].r;

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

    {

        pushcol(rt,x);

        return ;

    }

    pushdown(rt);

    int mid=(l+r)>>;

    if(L<=mid) modify(rt<<,L,R,x);

    if(R>mid) modify(rt<<|,L,R,x);

    update(rt);

}

void dfs1(int x , int f , int deep)

{

    dep[x]=deep;

    fa[x]=f;

    sze[x]=;

    int maxson=-;

    int len=L[x].size();

    for(int i= ; i<len ; i++)

    {

        int v=L[x][i];

        if(v==f) continue;

        dfs1(v,x,deep+);

        sze[x]+=sze[v];

        if(maxson<sze[v]) {maxson=sze[v],son[x]=v;}

    }

}

void dfs2(int x , int topf)

{

    id[x]=++cnt;

    b[id[x]]=w[x];

    top[x]=topf;

    if(!son[x]) return ;

    dfs2(son[x],topf);

    int len=L[x].size();

    for(int i= ; i<len ; i++)

    {

        int v=L[x][i];

        if(v==fa[x]||v==son[x]) continue;

        dfs2(v,v);

    }

}

int tree_query(int u , int v)

{

    int sum=,colx=,coly=;

    ///colx,coly 都是表示靠近根的一边的颜色

    while(top[u]!=top[v])

    {

        if(dep[top[u]]<dep[top[v]]) swap(u,v),swap(colx,coly);

        sum+=query(,id[top[u]],id[u]);

        if(rcol==colx) sum--;  ///当前链的右边颜色与上一个链的左边颜色（因为靠近根的一方为左）

        colx=lcol; u=fa[top[u]];

    }

    if(id[u]>id[v]) swap(u,v),swap(colx,coly);

    sum+=query(,id[u],id[v]);

    if(lcol==colx) --sum;

    if(rcol==coly) --sum;

    return sum;

}

void tree_modify(int u , int v , int c)

{

    while(top[u]!=top[v])

    {

        if(dep[top[u]]<dep[top[v]]) swap(u,v);

        modify(,id[top[u]],id[u],c);

        u=fa[top[u]];

    }

    if(id[u]>id[v]) swap(u,v);

    modify(,id[u],id[v],c);

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i= ; i<=n ; i++) scanf("%d",&w[i]);

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

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

        L[u].push_back(v);

        L[v].push_back(u);

    }

    dfs1(,,);

    dfs2(,);

    build(,,n);

    for(int i= ; i<=m ; i++)

    {

        char c; cin>>c; int x,y;

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

        if(c=='Q')

        {

            printf("%d\n",tree_query(x,y));

        }

        else

        {

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

            tree_modify(x,y,v);

        }

    }

}

有些金典题，越看越有味道  主要是菜呜呜

http://acm.hdu.edu.cn/showproblem.php?pid=5893

Description

给出一棵nn个点的树，每条边有颜色，mm次操作，操作分两种

Change a b c:Change a b c:把从aa点到bb点路径上所有边的颜色变成cc
Query a b:Query a b:查询aa点到bb点路径上的边有几段连续颜色相同

Input

第一行两个整数n,mn,m表示点数和操作数，之后n−1n−1行每行三个整数u,v,cu,v,c表示u,vu,v之间有一条树边颜色为cc，之后mm行每行一个查询(1≤n≤40000,1≤m≤50000,1≤c≤105)(1≤n≤40000,1≤m≤50000,1≤c≤105)
Output

对于每组查询操作，输出查询结果

Sample Input

9 3
1 2 2
2 3 1
1 7 2
1 4 2
3 5 2
3 6 1
5 8 2
5 9 3
Query 1 8
Change 2 6 3
Query 1 6

Sample Output

3
2

Solution

以11为根节点对整棵树树链剖分，把边的颜色放到深度较深的点上变为点的颜色，由dfsdfs序把aa到bb的路径修改查询变成对若干线段的查询修改，进而问题转化为区间更新和区间段数查询，线段树记录区间段数，区间左右端点颜色以及区间是否全部为同一颜色即可

/*hdu 5893 (树链剖分+合并)

problem:

1.update:将a->b的边权设置为c

2.query:求a->b的连续边权的个数

222333 -> 2    22112->3

solve：

主要是查询的意思不是很懂. how many different kinds of continuous same cost

以为不同还要分长度,数值大小什么的。 于是没怎么想

结果后来发现是求区间中有多少个连续的子区间 - -. 感觉很僵

update直接用一个标记解决

query的时候, 维护区间左右端点的值以合并区间,合并的时候注意维护子区间的数量

而且树链剖分时 在合并链的时候也要进行判断什么的.

update的u == v的时候最好判断一下, 否则查询son[u] -> v会有问题

我们只有一个重链,可能有很多的轻链,query的 u == v时就是轻链合并的情况.

总体都是线段树的思路

hhh-2016-09-19 22:36:11

*/

#pragma comment(linker,"/STACK:124000000,124000000")

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <vector>

#include <map>

#define lson  i<<1

#define rson  i<<1|1

#define ll long long

#define clr(a,b) memset(a,b,sizeof(a))

#define key_val ch[ch[root][1]][0]

using namespace std;

const int maxn = ;

const int inf = 0x3f3f3f3f;

int head[maxn],tot,pos,son[maxn];

int top[maxn],fp[maxn],fa[maxn],dep[maxn],num[maxn],p[maxn];

int n;

int a[maxn];

struct Edge

{

    int to,next;

    int w;

} edge[maxn<<];

void ini()

{

    tot = ,pos = ;

    clr(head,-),clr(son,-);

    clr(a,);

}

void add_edge(int u,int v,int w)

{

    edge[tot].to = v,edge[tot].next = head[u],edge[tot].w = w,head[u] = tot++;

}

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

{

//    cout << u << " " <<pre <<" " <<d <<endl;

    dep[u] = d;

    fa[u] = pre,num[u] = ;

    for(int i = head[u]; ~i; i = edge[i].next)

    {

        int v = edge[i].to;

        if(v != pre)

        {

            a[v] = edge[i].w;

            dfs1(v,u,d+);

            num[u] += num[v];

            if(son[u] == - || num[v] > num[son[u]])

                son[u] = v;

        }

    }

}

void getpos(int u,int sp)

{

    top[u] = sp;

    p[u] = pos++;

    fp[p[u]] = u;

    if(son[u] == -)return ;

    getpos(son[u],sp);

    for(int i = head[u]; ~i ; i = edge[i].next)

    {

        int v = edge[i].to;

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

            getpos(v,v);

    }

}

struct node

{

    int l,r,mid;

    int ls,rs,same;

    ll num ;

} tree[maxn << ];

void push_up(int i)

{

    if(tree[lson].rs == tree[rson].ls )

    {

        tree[i].num = tree[lson].num + tree[rson].num -;

    }

    else

        tree[i].num =tree[lson].num + tree[rson].num;

    tree[i].ls = tree[lson].ls;

    tree[i].rs = tree[rson].rs;

}

void build(int i,int l,int r)

{

    tree[i].l = l,tree[i].r = r;

    tree[i].mid=(l+r) >>;

    tree[i].same = inf;

    tree[i].num = tree[i].ls = tree[i].rs = ;

    if(l == r)

    {

        tree[i].ls = tree[i].rs = a[fp[l]];

        tree[i].num = ;

//        cout << fp[l]  <<" " << a[fp[l]] <<endl;

        return;

    }

    build(lson,l,tree[i].mid);

    build(rson,tree[i].mid+,r);

    push_up(i);

}

void make_same(int i,int val)

{

    tree[i].same = val;

    tree[i].num = ;

    tree[i].ls = tree[i].rs = val;

}

void push_down(int i)

{

    if(tree[i].same != inf)

    {

        make_same(lson,tree[i].same);

        make_same(rson,tree[i].same);

        tree[i].same = inf;

    }

}

void update_area(int i,int l,int r,int val)

{

    if(tree[i].l >= l && tree[i].r <= r)

    {

        tree[i].same = val;

        tree[i].num = ;

        tree[i].ls = tree[i].rs = val;

        return ;

    }

    push_down(i);

    int mid = tree[i].mid;

    if(l <= mid)

        update_area(lson,l,r,val);

    if(r > mid)

        update_area(rson,l,r,val);

    push_up(i);

}

ll query(int i,int l,int r,int &tls,int &trs)

{

    if(tree[i].l >= l && tree[i].r <= r)

    {

        if(tree[i].l == l)

            tls = tree[i].ls;

        if(tree[i].r == r)

            trs = tree[i].rs;

        return tree[i].num ;

    }

    push_down(i);

    int mid = tree[i].mid ;

    ll ans = ;

    if(r <= mid)

        ans = query(lson,l,r,tls,trs);

    else if(l > mid)

        ans = query(rson,l,r,tls,trs);

    else

    {

        int tls1,tls2,trs1,trs2;

        ll t1 = query(lson,l,mid,tls1,trs1);

        ll t2 = query(rson,mid+,r,tls2,trs2);

        ans = t1 + t2;

        if(tree[lson].rs == tree[rson].ls)

        {

            ans --;

        }

        tls = tls1,trs = trs2;

    }

    push_up(i);

    return ans;

}

void update_same(int u,int v,int val)

{

    int f1 = top[u],f2 = top[v];

    while(f1 != f2)

    {

        if(dep[f1] < dep[f2])

        {

            swap(f1,f2),swap(u,v);

        }

        update_area(,p[f1],p[u],val);

        u = fa[f1],f1 = top[u];

    }

    if(u == v)

    return ;

    if(dep[u] > dep[v]) swap(u,v);

    update_area(,p[son[u]],p[v],val);

}

ll query_dif(int u,int v)

{

    int f1 = top[u],f2 = top[v];

    int ls1,rs1,ls2,rs2;

    ls1 = rs1 = ls2 = rs2 = inf;

    int tls1,trs1,tls2,trs2;

    int fi1 = ,fi2 = ;

    ll ans = ;

    while(f1 != f2)

    {

        if(dep[f1] > dep[f2])

        {

            ans += query(,p[f1],p[u],tls1,trs1);

            if(trs1 == ls1)

                ans--;

            ls1 = tls1;

            if(fi1)

            {

                rs1 = trs1;

                fi1 = ;

            }

            u = fa[f1],f1 = top[u];

        }

        else

        {

            ans += query(,p[f2],p[v],tls2,trs2);

            if(trs2 == ls2)

                ans--;

            ls2 = tls2;

            if(fi2)

            {

                rs2 = trs2;

                fi2 = ;

            }

            v = fa[f2],f2 = top[v];

        }

    }

    if(u == v)

    {

        if(tls1 == tls2)

        ans --;

        return ans;

    }

    if(dep[u] > dep[v])

    {

        ans += query(,p[son[v]],p[u],tls1,trs1);

        if(trs1 == ls1)

            ans--;

        if(tls1 == ls2)

            ans --;

    }

    else

    {

        ans += query(,p[son[u]],p[v],tls2,trs2);

        if(trs2 == ls2)

            ans--;

        if(tls2 == ls1)

            ans--;

    }

    return ans;

}

char str[];

int main()

{

//    freopen("in.txt","r",stdin);

    int a,b,c;

    int m,u,v,w;

    while(scanf("%d%d",&n,&m) != EOF)

    {

        ini();

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

        {

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

            add_edge(u,v,w);

            add_edge(v,u,w);

        }

        dfs1(,,);

        getpos(,);

        build(,,pos-);

//        cout << pos -1 <<endl;

        for(int i = ; i <= m; i++)

        {

            scanf("%s",str);

            scanf("%d%d",&a,&b);

            if(str[] == 'C')

            {

                scanf("%d",&c);

                update_same(a,b,c);

            }

            else

            {

                if(a == b)

                    printf("0\n");

                else

                    printf("%I64d\n",query_dif(a,b));

            }

        }

    }

    return ;

}

相关文章