(luogu2486)染色(SDOI2011)

发表于 | 分类于 ， ，

这题就有点难度了…

树链剖分笔记索引

思路:

还是树链剖分+线段树…

这题难一点的地方就在于线段树的处理

我们可以记录下区间内的颜色段个数, 然后维护它

但有个问题, 合并两个区间时中间的颜色段可能跨了左右两个区间, 所以不能简单地将颜色段个数加起来

我们还需要记录区间两端的颜色来判断合并区间时是否有颜色段也合并了, 如果是则合并时颜色段个数需减1

还有一个细节需要注意, 在沿路径爬的时候, 也有可能颜色段会合并, 这时也需要将答案减1

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;
const int Mn(100005);
void qrd(int& x)
{
    x=0; char c(getchar());
    while(!isdigit(c)) c=getchar();
    while(isdigit(c))
    { x=x*10+c-'0'; c=getchar(); }
}
int n,m;
struct edge
{
    int e,nt;
}ed[Mn*2];
int vs[Mn],ec(0);
void adde(int s,int e)
{
    ed[++ec].e=e; ed[ec].nt=vs[s];
    vs[s] = ec;
}
int col[Mn];
int dp[Mn],sz[Mn],hs[Mn],pa[Mn];
/*----树链剖分----*/
void dfs1(int x)
{
    sz[x] = 1;
    for(int e(vs[x]);e;e=ed[e].nt)
    {
        int& ntn(ed[e].e);
        if(!dp[ntn])
        {
            dp[ntn] = dp[x]+1;
            pa[ntn] = x;
            dfs1(ntn);
            sz[x] += sz[ntn];
            if(sz[ntn]>sz[hs[x]])   hs[x] = ntn;
        }
    }
}
int tp[Mn],vp[Mn],cd[Mn],dc(0);
void dfs2(int x)
{
    cd[++dc] = x;
    vp[x] = dc;
    //printf("%d: %d\n",x,vp[x]);
    if(hs[x])
    {
        tp[hs[x]] = tp[x];
        dfs2(hs[x]);
    }
    for(int e(vs[x]);e;e=ed[e].nt)
    {
        int& ntn(ed[e].e);
        if(dp[ntn]>dp[x] && ntn!=hs[x])
        {
            tp[ntn] = ntn;
            dfs2(ntn);
        }
    }
}
/*----线段树----*/
struct sn
{
    int l,r,lc,rc,cn,t;
    //左右端点,左右颜色,颜色段数,懒标记
}t[Mn<<2];
void ud(int rt)	//合并区间
{
    sn &nd(t[rt]),&ls(t[rt<<1]),&rs(t[rt<<1|1]);
    nd.lc=ls.lc, nd.rc=rs.rc;
    int ans(ls.cn+rs.cn);
    if(ls.rc==rs.lc)    --ans;
    //左区间右端颜色和右区间左端颜色相同,说明颜色段合并
    nd.cn = ans;
}
void pd(int rt)	//下放标记
{
    sn &nd(t[rt]),&ls(t[rt<<1]),&rs(t[rt<<1|1]);
    if(nd.t)
    {
        ls.lc=ls.rc=rs.lc=rs.rc=nd.t;
        ls.cn=rs.cn=1;
        ls.t=rs.t=nd.t;
        nd.t=0;
    }
}
void bud(int l,int r,int rt=1)	//建树
{
    sn &nd(t[rt]),&ls(t[rt<<1]),&rs(t[rt<<1|1]);
    if(l==r)
    {
        nd.l=nd.r=l;
        nd.lc=nd.rc=col[cd[l]];
        nd.cn = 1;
        return;
    }
    int mid((l+r)>>1);
    bud(l,mid,rt<<1);
    bud(mid+1,r,rt<<1|1);
    nd.l=l, nd.r=r;
    ud(rt);
}
void mdf(int ml,int mr,int cl,int rt=1)	//修改
{
    sn &nd(t[rt]),&ls(t[rt<<1]),&rs(t[rt<<1|1]);
    if(nd.l>=ml && nd.r<=mr)
    {
        nd.lc=nd.rc=cl;
        nd.cn=1;
        nd.t=cl;
        return;
    }
    pd(rt);
    if(ml<=ls.r)    mdf(ml,mr,cl,rt<<1);
    if(mr>=rs.l)    mdf(ml,mr,cl,rt<<1|1);
    ud(rt);
}
int qry(int ql,int qr,int& LC,int& RC,int rt=1)	//查询
{
    sn &nd(t[rt]),&ls(t[rt<<1]),&rs(t[rt<<1|1]);
    if(nd.l==ql)    LC=nd.lc;
    if(nd.r==qr)    RC=nd.rc;
    if(nd.l>=ql && nd.r<=qr)
        return nd.cn;
    int ret(0),vls(false),vrs(false);
    pd(rt);
    if(ql<=ls.r)    vls=true, ret += qry(ql,qr,LC,RC,rt<<1);
    if(qr>=rs.l)    vrs=true, ret += qry(ql,qr,LC,RC,rt<<1|1);
    if(vls && vrs && ls.rc==rs.lc)    --ret;
    return ret;
}
int main()
{
    cin >> n >> m;
    for(int i(1);i<=n;++i)
        qrd(col[i]);
    for(int i(1);i<n;++i)
    {
        int x,y;
        qrd(x), qrd(y);
        adde(x,y), adde(y,x);
    }
    dp[1]=1,pa[1]=1; dfs1(1);
    tp[1]=1; dfs2(1);
    bud(1,n);
    int lx,rx;
    while(m--)
    {
        char c;
        int a,b;
        cin >> c;
        qrd(a),qrd(b);
        if(c=='Q')
        {
            int lac(0),lbc(0),lc(0),rc(0),ans(0);
            //两边上次的上端点颜色,上下端点颜色,答案
            while(tp[a]!=tp[b])
            {
                if(dp[tp[a]]<dp[tp[b]])
                    a^=b^=a^=b, lac^=lbc^=lac^=lbc;
                ans += qry(vp[tp[a]],vp[a],lc,rc);
                a = pa[tp[a]];
                if(rc==lac) --ans;
                //本次下端点颜色与上次上端点颜色相同,颜色段合并
                lac = lc;
            }
            if(dp[a]<dp[b])
                a^=b^=a^=b, lac^=lbc^=lac^=lbc;
            ans += qry(vp[b],vp[a],lc,rc);
            if(rc==lac) --ans;
            if(lc==lbc) --ans;
            printf("%d\n",ans);
        }
        if(c=='C')
        {
            int c; qrd(c);
            while(tp[a]!=tp[b])
            {
                if(dp[tp[a]]<dp[tp[b]])
                    a^=b^=a^=b;
                mdf(vp[tp[a]],vp[a],c);
                a = pa[tp[a]];
            }
            if(dp[a]<dp[b])
                a^=b^=a^=b;
            mdf(vp[b],vp[a],c);
        }
    }
    return 0;
}