P5168 xtq玩魔塔

传送门

其实就是板子……只要会克鲁斯卡尔重构树和带修莫队就可以了

这么想着的我就调了将近一个下午……

思路其实比较清晰，然而码量很大，细节贼多……

不难看出只在最小生成树上走最优，于是建出克鲁斯卡尔重构树，\(2\)操作直接倍增跳，\(1\)操作和\(3\)操作离线，把克鲁斯卡尔重构树用\(dfs\)序转化为序列之后用带修莫队做

然后……注意细节……这是我的肺腑之言……

//minamoto

#include<bits/stdc++.h>

#define R register

#define inf 0x3f3f3f3f

#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}

template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}

using namespace std;

char buf[1<<21],*p1=buf,*p2=buf;

inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

int read(){

    R int res,f=1;R char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

char sr[1<<21],z[20];int C=-1,Z=0;

inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}

void print(R int x){

    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;

    while(z[++Z]=x%10+48,x/=10);

    while(sr[++C]=z[Z],--Z);sr[++C]='\n';

}

const int N=5e5+5,M=3e5+5;

struct eg{int u,v,w;}E[M];

struct ee{int v,nx;}e[N<<1];

int head[N],tot;

inline bool cmp(const eg &a,const eg &b){return a.w<b.w;}

inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}

int fa[N],val[N],f[N][20],bin[25],ls[N],rs[N],rt[N],ans[N],dep[N],rk[N],a[N],col[N],b[N];

int cnt,n,m,q,tim,Time,t,op,x,y,S,p,now,l,r,T,lim;

struct query{

    int l,r,t,id,op;

    inline bool operator <(const query &b)const{

        return rt[l]!=rt[b.l]?l<b.l:rt[r]!=rt[b.r]?r<b.r:t<b.t;

    }

}qaq[N];

struct change{int pos,now,las;}c[N];

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

inline void mission(int u){for(R int i=1;bin[i]<=n;++i)f[u][i]=f[f[u][i-1]][i-1];}

void dfs(int u){

//	puts("QAQ");

    mission(u);

    if(u<=n)return (void)(ls[u]=rs[u]=++tim,rk[tim]=u);

    ls[u]=inf,rs[u]=0;

    go(u)dep[v]=dep[u]+1,dfs(v),cmin(ls[u],ls[v]),cmax(rs[u],rs[v]);

}

int get(int x,int y){

//	printf("%d %d\n",f[x][0],f[y][0]);

    if(dep[y]>dep[x])swap(x,y);

    fd(i,18,0)if(dep[f[x][i]]>=dep[y])x=f[x][i];

    if(x==y)return val[x];

    fd(i,18,0)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];

    return val[f[x][0]];

}

int ck(int x,int y){

    fd(i,18,0)if(f[x][i]&&val[f[x][i]]<=y)x=f[x][i];

    return x;

}

inline void revise(R int x,R int d){col[x]+=d;d>0?(now+=col[x]==1):(now-=col[x]==0);}

inline void going(R int x,R int d){if(x>=l&&x<=r)revise(d,1),revise(a[x],-1);a[x]=d;}

int main(){

//	freopen("testdata.in","r",stdin);

    cnt=n=read(),m=read(),q=read(),S=pow(n,0.666);

    if(S==0)S=1;

    bin[0]=1;fp(i,1,20)bin[i]=bin[i-1]<<1;

    fp(i,1,(n<<1))fa[i]=i;

    fp(i,1,n)b[++lim]=val[i]=read(),rt[i]=(i-1)/S+1;

    fp(i,1,m)E[i].u=read(),E[i].v=read(),E[i].w=read();

//	fp(i,1,m)printf("%d %d %d\n",E[i].u,E[i].v,E[i].w);

    sort(E+1,E+1+m,cmp);

    fp(i,1,m){

        int u=find(E[i].u),v=find(E[i].v);

        if(u!=v){

            val[++cnt]=E[i].w,fa[u]=fa[v]=cnt;

            add(cnt,u),add(cnt,v),f[u][0]=f[v][0]=cnt;

            if(cnt-n==n-1)break;

        }

    }dfs(cnt);

    fp(i,1,n)a[i]=val[rk[i]];

//	fp(i,1,n)printf("%d %d\n",i,ls[i]);

    fp(i,1,q){

        op=read(),x=read(),y=read();

//		printf("%d %d %d %d\n",i,op,x,y);

        switch(op){

            case 1:c[++Time]={ls[x],y,val[x]},b[++lim]=y,val[x]=y;break;

            case 2:ans[++t]=x==y?0:get(x,y);break;

            case 3:{

                p=ck(x,y);

                ++t,qaq[t]={ls[p],rs[p],Time,t,1};

                break;

            }

        }

    }sort(qaq+1,qaq+1+t);

    sort(b+1,b+1+lim),lim=unique(b+1,b+1+lim)-b-1;

    fp(i,1,n)a[i]=lower_bound(b+1,b+1+lim,a[i])-b;

    fp(i,1,Time){

    	c[i].las=lower_bound(b+1,b+1+lim,c[i].las)-b;

    	c[i].now=lower_bound(b+1,b+1+lim,c[i].now)-b;

    }

    l=1,r=0,T=0;

    fp(i,1,t)if(qaq[i].op==1){

        while(T<qaq[i].t)++T,going(c[T].pos,c[T].now);

        while(T>qaq[i].t)going(c[T].pos,c[T].las),--T;

        while(l>qaq[i].l)revise(a[--l],1);

        while(r<qaq[i].r)revise(a[++r],1);

        while(r>qaq[i].r)revise(a[r--],-1);

        while(l<qaq[i].l)revise(a[l++],-1);

//		printf("%d %d %d %d\n",qaq[i].id,qaq[i].l,qaq[i].r,qaq[i].t);

        ans[qaq[i].id]=now;

    }fp(i,1,t)print(ans[i]);

    return Ot(),0;

}

巴特西

P5168 xtq玩魔塔

最新文章

热门文章