题解 P5168 【xtq玩魔塔】
mrsrz
2019-06-27 20:25:19
随机数据也太毒了吧，假算法放过去一大堆，这题明明有一个$\log$的算法的啊……~~有本事数据范围加个0~~
首先考虑第二个询问，这个询问和[ \[NOI2018\] 归程](https://www.luogu.org/problemnew/show/P4768)类似，可以使用克鲁斯卡尔重构树解决。
然后考虑第三个询问，把它放在重构树上，就是一个子树数颜色问题。由于有修改操作，所以就是个带修子树数颜色问题。
这个是可以一个$\log$解决的。~~不知道为什么要放带修莫队和树套树过去而且还跑那么快~~
显然可以用树状数组维护子树信息（dfs序连续）。
我们考虑每加入一个节点$x$的时候，在哪些节点处能产生贡献。显然，能产生贡献的节点所在子树内原本没有这种颜色。
我们可以找到这种颜色的一个其他节点$y$，使它与$x$的$\rm LCA$的深度最深。那么$x$能在该节点到$\rm{LCA}$（不包含$\rm{LCA}$）的路径上各产生1的贡献。
用差分的思想，在树状数组上，$x$处加1，在$\rm{LCA}$处减1即可。
而这样的$y$，只可能是dfs序和$x$最相近的两个中的一个（比它小和比它大，也可能只有一个），用```set```维护一下即可。
然后查询颜色就直接查询树状数组上这棵子树即可。
这样就做到一个$\log$维护颜色信息了。
于是总时间复杂度$O((n+m+q)\log n)$。
## Code：
```cpp
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
vector<int>vec;
inline int readint(){
int c=getchar(),d=0;
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())d=d*10+(c^'0');
return d;
}
const int N=4e5+5;
int ff[N],n,m,col[N],Q;
inline int find(int x){return x==ff[x]?x:ff[x]=find(ff[x]);}
struct que{
int op,x,y;
}q[N];
namespace nt{
int to[N],nxt[N],head[N],cnt,fa[N],dw[N],rt,dep[N],F[18][N],idfn[N];
int sz[N],son[N],top[N],dfn[N],idx;
inline void addedge(int u,int v,int w){to[++cnt]=v,nxt[cnt]=head[u],head[u]=cnt,fa[v]=u,dw[u]=w;}
void dfs(int now){
sz[now]=1,son[now]=0;
for(int i=head[now];i;i=nxt[i]){
dep[to[i]]=dep[now]+1,F[0][to[i]]=now,dfs(to[i]),sz[now]+=sz[to[i]];
if(!son[now]||sz[son[now]]<sz[to[i]])son[now]=to[i];
}
}
void dfs2(int now){
idfn[dfn[now]=++idx]=now;
if(son[now])top[son[now]]=top[now],dfs2(son[now]);
for(int i=head[now];i;i=nxt[i])if(to[i]!=son[now])dfs2(top[to[i]]=to[i]);
}
inline int LCA(int x,int y){
while(top[x]!=top[y])
if(dep[top[x]]>dep[top[y]])x=fa[top[x]];else y=fa[top[y]];
return dep[x]<dep[y]?x:y;
}
void init(){
dep[rt]=1,top[rt]=rt;
dfs(rt),dfs2(rt);
for(int i=1;i<18;++i)
for(int j=1;j<=rt;++j)F[i][j]=F[i-1][F[i-1][j]];
}
int B[N];
inline void add(int i,int x){for(;i<N;i+=i&-i)B[i]+=x;}
inline int ask(int i){int x=0;for(;i;i&=i-1)x+=B[i];return x;}
struct colors{
set<int>s;
void ADD(int x){
add(x,1);
if(s.empty()){
s.insert(x);
return;
}
auto nxt=s.lower_bound(x);
if(nxt==s.begin()){
s.insert(x);
add(dfn[LCA(idfn[x],idfn[*nxt])],-1);
return;
}
auto pre=nxt;--pre;
if(nxt==s.end()){
s.insert(x);
add(dfn[LCA(idfn[x],idfn[*pre])],-1);
return;
}
int lft=LCA(idfn[x],idfn[*pre]),rgt=LCA(idfn[x],idfn[*nxt]);
int X=dep[lft]>dep[rgt]?lft:rgt;
s.insert(x);
add(dfn[X],-1);
}
void DEL(int x){
s.erase(x);
add(x,-1);
if(s.empty())return;
auto nxt=s.lower_bound(x);
if(nxt==s.begin()){
add(dfn[LCA(idfn[x],idfn[*nxt])],1);
return;
}
auto pre=nxt;--pre;
if(nxt==s.end()){
add(dfn[LCA(idfn[x],idfn[*pre])],1);
return;
}
int lft=LCA(idfn[x],idfn[*pre]),rgt=LCA(idfn[x],idfn[*nxt]);
int X=dep[lft]>dep[rgt]?lft:rgt;
add(dfn[X],1);
}
}c[N];
void work(){
for(int i=1;i<=n;++i)
c[col[i]].ADD(dfn[i]);
for(int i=1;i<=Q;++i){
switch(q[i].op){
case 1:{
if(col[q[i].x]==q[i].y)break;
c[col[q[i].x]].DEL(dfn[q[i].x]);
c[col[q[i].x]=q[i].y].ADD(dfn[q[i].x]);
break;
}
case 2:{
int p=LCA(q[i].x,q[i].y);
printf("%d\n",dw[p]);
break;
}
case 3:{
int x=q[i].x,y=q[i].y;
for(int i=17;~i;--i)
if(F[i][x]&&dw[F[i][x]]<=y)x=F[i][x];
printf("%d\n",ask(dfn[x]+sz[x]-1)-ask(dfn[x]-1));
break;
}
}
}
}
}
struct EDGE{
int u,v,w;
inline int operator<(const EDGE&r)const{return w<r.w;}
}e[N];
void kruskal(){
int tot=n;
for(int i=1;i<=m;++i){
int u=find(e[i].u),v=find(e[i].v);
if(u!=v){
++tot;
nt::addedge(tot,u,e[i].w),nt::addedge(tot,v,e[i].w);
ff[u]=ff[v]=tot;
}
}
nt::rt=tot;
}
int main(){
n=readint(),m=readint(),Q=readint();
for(int i=1;i<=n;++i)vec.push_back(col[i]=readint());
for(int i=1;i<=m;++i)e[i].u=readint(),e[i].v=readint(),e[i].w=readint();
sort(e+1,e+m+1);
for(int i=1;i<=2*n;++i)ff[i]=i;
for(int i=1;i<=Q;++i){
q[i].op=readint(),q[i].x=readint(),q[i].y=readint();
if(q[i].op==1)vec.push_back(q[i].y);
}
sort(vec.begin(),vec.end()),vec.erase(unique(vec.begin(),vec.end()),vec.end());
for(int i=1;i<=n;++i)col[i]=lower_bound(vec.begin(),vec.end(),col[i])-vec.begin();
for(int i=1;i<=Q;++i)if(q[i].op==1)q[i].y=lower_bound(vec.begin(),vec.end(),q[i].y)-vec.begin();
kruskal();
nt::init();
nt::work();
return 0;
}
```