LOJ10141染色

SDOI 2011 染色

给定一棵有 n 个节点的无根树和 m 个操作，操作共两类。

将节点 a 到节点 b 路径上的所有节点都染上颜色；

询问节点 a 到节点 b 路径上的颜色段数量，连续相同颜色的认为是同一段，例如 112221 由三段组成：11 、 222、1。

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

输入格式
第一行包括两个整数 n,m，表示节点数和操作数；

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

接下来若干行包含两个整数 x 和 y，表示 x 和 y 之间有一条无向边；

接下来若干行每行描述一个操作：

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

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

输出格式
对于每个询问操作，输出一行询问结果。

样例
样例输入
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
样例输出
3
1
2
数据范围与提示
对于 100% 的数据，N,M≤10^5，所有颜色 C 为整数且在 [0,10^9] 之间。

_____________________________________________________________________________________

树链剖分，需要维护

sum[]：表示段内的色段数

lc[]：表示左侧点的颜色

rc[]：表示右侧点的颜色

所以，

sum[cur]=sum[cur<<1]+sum[cur<<1|1]-(rc[cur<<1]==lc[cur<<1|1])

lc[cur]=lc[cur<<1]

rc[cur]=rc[cur<<1|1]

需要注意，树链之间两点的颜色是否相同。

———————————————————————————————————————————————

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3 const int maxn=1e5+10;

  4 int n,m;

  5 struct edge

  6 {

  7     int u,v,nxt;

  8 }e[maxn<<1];

  9 int head[maxn],js;

 10 void addage(int u,int v)

 11 {

 12     e[++js].u=u;e[js].v=v;

 13     e[js].nxt=head[u];head[u]=js;

 14 }

 15 int w[maxn];

 16 int dep[maxn],fat[maxn],son[maxn],siz[maxn];

 17 void dfs(int u,int fa)

 18 {

 19     dep[u]=dep[fa]+1;

 20     fat[u]=fa;

 21     siz[u]=1;

 22     for(int i=head[u];i;i=e[i].nxt)

 23     {

 24         int v=e[i].v;

 25         if(v==fa)continue;

 26         dfs(v,u);

 27         siz[u]+=siz[v];

 28         if(!son[u] || siz[son[u]]<siz[v])son[u]=v;

 29     }

 30 }

 31 int pos[maxn],fos[maxn],top[maxn],p;

 32 void getpos(int u,int fa)

 33 {

 34     pos[u]=++p;

 35     fos[p]=u;

 36     top[u]=fa;

 37     if(!son[u])return;

 38     getpos(son[u],fa);

 39     for(int i=head[u];i;i=e[i].nxt)

 40     {

 41         int v=e[i].v;

 42         if(v!=fat[u] && v!=son[u])getpos(v,v);

 43     }

 44 }

 45 int sum[maxn<<2],lc[maxn<<2],rc[maxn<<2],delt[maxn<<2];

 46 void update(int cur)

 47 {

 48     lc[cur]=lc[cur<<1];

 49     rc[cur]=rc[cur<<1|1];

 50     sum[cur]=sum[cur<<1]+sum[cur<<1|1]-(rc[cur<<1]==lc[cur<<1|1]);

 51 }

 52 void build(int cur,int l,int r)

 53 {

 54     if(l==r)

 55     {

 56         lc[cur]=rc[cur]=w[fos[l]];

 57         sum[cur]=1;

 58         return;

 59     }

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

 61     build(cur<<1,l,mid);

 62     build(cur<<1|1,mid+1,r);

 63     update(cur);

 64 }

 65 void down(int cur)

 66 {

 67     sum[cur<<1]=sum[cur<<1|1]=1;

 68     delt[cur<<1]=delt[cur<<1|1]=lc[cur<<1]=rc[cur<<1]=lc[cur<<1|1]=rc[cur<<1|1]=delt[cur];

 69     delt[cur]=-1;

 70 }

 71 void modi(int cur,int l,int r,int ql,int qr,int x)

 72 {

 73     if(ql<=l && r<=qr)

 74     {

 75         sum[cur]=1;

 76         delt[cur]=lc[cur]=rc[cur]=x;

 77         return ;

 78     }

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

 80     if(delt[cur]!=-1)down(cur);

 81     if(ql<=mid)modi(cur<<1,l,mid,ql,qr,x);

 82     if(mid<qr)modi(cur<<1|1,mid+1,r,ql,qr,x);

 83     update(cur);

 84 }

 85 void change(int u,int v,int x)

 86 {

 87     int tpu=top[u],tpv=top[v];

 88     while(tpu!=tpv)

 89     {

 90         if(dep[tpu]<dep[tpv])

 91         {

 92             swap(u,v);swap(tpu,tpv);

 93         }

 94         modi(1,1,n,pos[tpu],pos[u],x);

 95         u=fat[tpu];tpu=top[u];

 96     }

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

 98     modi(1,1,n,pos[u],pos[v],x);

 99 }

100 int query_c(int cur,int l,int r,int p)

101 {

102     if(l==r)return lc[cur];

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

104     if(delt[cur]!=-1)down(cur);

105     if(p<=mid)return query_c(cur<<1,l,mid,p);

106     else return query_c(cur<<1|1,mid+1,r,p);

107 }

108 int query(int cur,int l,int r,int ql,int qr)

109 {

110     if(ql<=l && r<=qr)return sum[cur];

111     int mid=(l+r)>>1,ans=0;

112     if(delt[cur]!=-1)down(cur);

113     if(ql<=mid)ans+=query(cur<<1,l,mid,ql,qr);

114     if(qr>mid)ans+=query(cur<<1|1,mid+1,r,ql,qr);

115     if(ql<=mid && mid<qr)ans-=rc[cur<<1]==lc[cur<<1|1];

116     return ans;

117 }

118 int ask(int u,int v)

119 {

120     int ans=0;

121     int clt,clp;

122     int tpu=top[u],tpv=top[v];

123     while(tpu!=tpv)

124     {

125             if(dep[tpu]<dep[tpv])

126             {

127                 swap(u,v);swap(tpu,tpv);

128             }

129             clt=query_c(1,1,n,pos[tpu]);

130             clp=query_c(1,1,n,pos[fat[tpu]]);

131             ans+=query(1,1,n,pos[tpu],pos[u])-(clt==clp);

132             u=fat[tpu];tpu=top[u];

133     }

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

135     ans+=query(1,1,n,pos[u],pos[v]);

136     return ans;

137 }

138 int main()

139 {

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

141     for(int i=1;i<=n;++i)scanf("%d",w+i);

142     for(int u,v,i=1;i<n;++i)

143     {

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

145         addage(u,v);addage(v,u);

146     }

147     dfs(1,0);

148     getpos(1,1);

149     memset(delt,-1,sizeof(delt));

150     build(1,1,n);

151     char s[3];

152     int a,b,c;

153     while(m--)

154     {

155         scanf("%s",s);

156         if(s[0]=='C')

157         {

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

159             change(a,b,c);

160         }

161         else

162         {

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

164             printf("%d\n",ask(a,b));

165         }

166     }

167     return 0;

168 }

巴特西

LOJ10141染色

最新文章

热门文章