「BZOJ2243」[SDOI2011] 染色

2014年4月8日9,2921

Description

给定一棵有n个节点的无根树和m个操作，操作有2类：

1、将节点a到节点b路径上所有点都染成颜色c；

2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。

请你写一个程序依次完成这m个操作。

Input

第一行包含2个整数n和m，分别表示节点数和操作数；

第二行包含n个正整数表示n个节点的初始颜色

下面行每行包含两个整数x和y，表示x和y之间有一条无向边。

下面行每行描述一个操作：

“C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c；

“Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。

Output

对于每个询问操作，输出一行答案。

Sample Input

6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5

Sample Output

3
1
2

HINT

数N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。

题解

直接树链剖分+线段树

线段树注意合并的问题

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#define N 100001
using namespace std;
int n,m,cnt,sz,head[N],deep[N],son[N],belong[N],pl[N],v[N],ft[N][18];
bool vis[N];
struct seg{int l,r,lc,rc,s,tag;}t[4*N];
struct edge{int to,next;}e[2*N];
void insert(int u,int v)
{
    e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
    e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;
}
void dfs1(int x)
{
    vis[x]=son[x]=1;
    for(int i=1;i<=17;i++)
    {
        if(deep[x]<(1<<i))break;
        ft[x][i]=ft[ft[x][i-1]][i-1];
    }
    for(int i=head[x];i;i=e[i].next)
    {
        if(vis[e[i].to])continue;
        deep[e[i].to]=deep[x]+1;
        ft[e[i].to][0]=x;
        dfs1(e[i].to);
        son[x]+=son[e[i].to];
    }
}
void dfs2(int x,int chain)
{
    pl[x]=++sz;belong[x]=chain;
    int k=0;
    for(int i=head[x];i;i=e[i].next)
        if(deep[e[i].to]>deep[x]&&son[k]<son[e[i].to])
           k=e[i].to;
    if(!k)return;
    dfs2(k,chain);
    for(int i=head[x];i;i=e[i].next)
        if(deep[e[i].to]>deep[x]&&k!=e[i].to)
           dfs2(e[i].to,e[i].to);
}
int lca(int x,int y)
{
    if(deep[x]<deep[y])swap(x,y);
    int t=deep[x]-deep[y];
    for(int i=0;i<=17;i++)
       if(t&(1<<i))x=ft[x][i];
    for(int i=17;i>=0;i--)
       if(ft[x][i]!=ft[y][i])
       {x=ft[x][i];y=ft[y][i];}
    if(x==y)return x;
    return ft[x][0];
}
void build(int k,int l,int r)
{
    t[k].l=l;t[k].r=r;t[k].s=1;t[k].tag=-1;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
void pushup(int k)
{
    t[k].lc=t[k<<1].lc;t[k].rc=t[k<<1|1].rc;
    if(t[k<<1].rc^t[k<<1|1].lc)t[k].s=t[k<<1].s+t[k<<1|1].s;
    else t[k].s=t[k<<1].s+t[k<<1|1].s-1;
}
void pushdown(int k)
{
    int tmp=t[k].tag;t[k].tag=-1;
    if(tmp==-1||t[k].l==t[k].r)return;
    t[k<<1].s=t[k<<1|1].s=1;
    t[k<<1].tag=t[k<<1|1].tag=tmp;
    t[k<<1].lc=t[k<<1].rc=tmp;
    t[k<<1|1].lc=t[k<<1|1].rc=tmp;
}
void change(int k,int x,int y,int c)
{
    pushdown(k);
    int l=t[k].l,r=t[k].r;
    if(l==x&&r==y)
    {t[k].lc=t[k].rc=c;t[k].s=1;t[k].tag=c;return;}
    int mid=(l+r)>>1;
    if(mid>=y)change(k<<1,x,y,c);
    else if(mid<x)change(k<<1|1,x,y,c);
    else
    {
        change(k<<1,x,mid,c);
        change(k<<1|1,mid+1,y,c);
    }
    pushup(k);
}
int ask(int k,int x,int y)
{
    pushdown(k);
    int l=t[k].l,r=t[k].r;
    if(l==x&&r==y)return t[k].s;
    int mid=(l+r)>>1;
    if(mid>=y)return ask(k<<1,x,y);
    else if(mid<x)return ask(k<<1|1,x,y);
    else
    {
        int tmp=1;
        if(t[k<<1].rc^t[k<<1|1].lc)tmp=0;
        return ask(k<<1,x,mid)+ask(k<<1|1,mid+1,y)-tmp;
    }
}
int getc(int k,int x)
{
    pushdown(k);
    int l=t[k].l,r=t[k].r;
    if(l==r)return t[k].lc;
    int mid=(l+r)>>1;
    if(x<=mid)return getc(k<<1,x);
    else return getc(k<<1|1,x);
}
int solvesum(int x,int f)
{
    int sum=0;
    while(belong[x]!=belong[f])
    {
        sum+=ask(1,pl[belong[x]],pl[x]);
        if(getc(1,pl[belong[x]])==getc(1,pl[ft[belong[x]][0]]))sum--;
        x=ft[belong[x]][0]; 
    }
    sum+=ask(1,pl[f],pl[x]);
    return sum;
}
void solvechange(int x,int f,int c)
{
    while(belong[x]!=belong[f])
    {
        change(1,pl[belong[x]],pl[x],c);
        x=ft[belong[x]][0]; 
    }
    change(1,pl[f],pl[x],c);
}
void solve()
{
    int a,b,c;
    dfs1(1);
    dfs2(1,1);
    build(1,1,n);
    for(int i=1;i<=n;i++)
        change(1,pl[i],pl[i],v[i]);
    for(int i=1;i<=m;i++)
    {
        char ch[10];
        scanf("%s",ch);
        if(ch[0]=='Q')
        {
            scanf("%d%d",&a,&b);
            int t=lca(a,b);
            printf("%d\n",solvesum(a,t)+solvesum(b,t)-1);
        }
        else
        {
            scanf("%d%d%d",&a,&b,&c);
            int t=lca(a,b);
            solvechange(a,t,c);solvechange(b,t,c);
        }
    }
}
void ini()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        insert(x,y);
    }
}
int main()
{
    ini();
    solve();
    return 0;
}

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

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cstring>

#define N 100001

using namespace std;

int n,m,cnt,sz,head[N],deep[N],son[N],belong[N],pl[N],v[N],ft[N][18];

bool vis[N];

struct seg{int l,r,lc,rc,s,tag;}t[4*N];

struct edge{int to,next;}e[2*N];

void insert(int u,int v)

{

e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;

e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;

}

void dfs1(int x)

{

vis[x]=son[x]=1;

for(int i=1;i<=17;i++)

{

if(deep[x]<(1<<i))break;

ft[x][i]=ft[ft[x][i-1]][i-1];

}

for(int i=head[x];i;i=e[i].next)

{

if(vis[e[i].to])continue;

deep[e[i].to]=deep[x]+1;

ft[e[i].to][0]=x;

dfs1(e[i].to);

son[x]+=son[e[i].to];

}

void dfs2(int x,int chain)

{

pl[x]=++sz;belong[x]=chain;

int k=0;

for(int i=head[x];i;i=e[i].next)

if(deep[e[i].to]>deep[x]&&son[k]<son[e[i].to])

k=e[i].to;

if(!k)return;

dfs2(k,chain);

for(int i=head[x];i;i=e[i].next)

if(deep[e[i].to]>deep[x]&&k!=e[i].to)

dfs2(e[i].to,e[i].to);

}

int lca(int x,int y)

{

if(deep[x]<deep[y])swap(x,y);

int t=deep[x]-deep[y];

for(int i=0;i<=17;i++)

if(t&(1<<i))x=ft[x][i];

for(int i=17;i>=0;i--)

if(ft[x][i]!=ft[y][i])

{x=ft[x][i];y=ft[y][i];}

if(x==y)return x;

return ft[x][0];

}

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

{

t[k].l=l;t[k].r=r;t[k].s=1;t[k].tag=-1;

if(l==r)return;

int mid=(l+r)>>1;

build(k<<1,l,mid);build(k<<1|1,mid+1,r);

}

void pushup(int k)

{

t[k].lc=t[k<<1].lc;t[k].rc=t[k<<1|1].rc;

if(t[k<<1].rc^t[k<<1|1].lc)t[k].s=t[k<<1].s+t[k<<1|1].s;

else t[k].s=t[k<<1].s+t[k<<1|1].s-1;

}

void pushdown(int k)

{

int tmp=t[k].tag;t[k].tag=-1;

if(tmp==-1||t[k].l==t[k].r)return;

t[k<<1].s=t[k<<1|1].s=1;

t[k<<1].tag=t[k<<1|1].tag=tmp;

t[k<<1].lc=t[k<<1].rc=tmp;

t[k<<1|1].lc=t[k<<1|1].rc=tmp;

}

void change(int k,int x,int y,int c)

{

pushdown(k);

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

if(l==x&&r==y)

{t[k].lc=t[k].rc=c;t[k].s=1;t[k].tag=c;return;}

int mid=(l+r)>>1;

if(mid>=y)change(k<<1,x,y,c);

else if(mid<x)change(k<<1|1,x,y,c);

else

{

change(k<<1,x,mid,c);

change(k<<1|1,mid+1,y,c);

}

pushup(k);

}

int ask(int k,int x,int y)

{

pushdown(k);

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

if(l==x&&r==y)return t[k].s;

int mid=(l+r)>>1;

if(mid>=y)return ask(k<<1,x,y);

else if(mid<x)return ask(k<<1|1,x,y);

else

{

int tmp=1;

if(t[k<<1].rc^t[k<<1|1].lc)tmp=0;

return ask(k<<1,x,mid)+ask(k<<1|1,mid+1,y)-tmp;

}

int getc(int k,int x)

{

pushdown(k);

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

if(l==r)return t[k].lc;

int mid=(l+r)>>1;

if(x<=mid)return getc(k<<1,x);

else return getc(k<<1|1,x);

}

int solvesum(int x,int f)

{

int sum=0;

while(belong[x]!=belong[f])

{

sum+=ask(1,pl[belong[x]],pl[x]);

if(getc(1,pl[belong[x]])==getc(1,pl[ft[belong[x]][0]]))sum--;

x=ft[belong[x]][0];

}

sum+=ask(1,pl[f],pl[x]);

return sum;

}

void solvechange(int x,int f,int c)

{

while(belong[x]!=belong[f])

{

change(1,pl[belong[x]],pl[x],c);

x=ft[belong[x]][0];

}

change(1,pl[f],pl[x],c);

}

void solve()

{

int a,b,c;

dfs1(1);

dfs2(1,1);

build(1,1,n);

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

change(1,pl[i],pl[i],v[i]);

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

{

char ch[10];

scanf("%s",ch);

if(ch[0]=='Q')

{

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

int t=lca(a,b);

printf("%d\n",solvesum(a,t)+solvesum(b,t)-1);

}

else

{

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

int t=lca(a,b);

solvechange(a,t,c);solvechange(b,t,c);

}

void ini()

{

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

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

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

{

int x,y;

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

insert(x,y);

}

int main()

{

ini();

solve();

return 0;

}

« 「BZOJ1036」[ZJOI2008] 树的统计Count 「zoj2112」Dynamic Rankings »

Hzwer's Fans

赞！在BZOJ挂了的时候就到你这里来看题！

hzwer.com _ Home | http://hzwer.com

「BZOJ2243」[SDOI2011] 染色

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论