题解 P5168 【xtq玩魔塔】
随机数据也太毒了吧，假算法放过去一大堆，这题明明有一个有本事数据范围加个0
首先考虑第二个询问，这个询问和 [NOI2018] 归程类似，可以使用克鲁斯卡尔重构树解决。
然后考虑第三个询问，把它放在重构树上，就是一个子树数颜色问题。由于有修改操作，所以就是个带修子树数颜色问题。
这个是可以一个不知道为什么要放带修莫队和树套树过去而且还跑那么快
显然可以用树状数组维护子树信息（dfs序连续）。
我们考虑每加入一个节点
我们可以找到这种颜色的一个其他节点
用差分的思想，在树状数组上，
而这样的set维护一下即可。
然后查询颜色就直接查询树状数组上这棵子树即可。
这样就做到一个
于是总时间复杂度
Code：
#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;
}