zcmimi's blog
查看原题

点击跳转

线段树分治+LCT

一个非常暴力的思路

FBI WARNING: 极有可能因为常数巨大而超时

把询问(修改)时间看成序列,每条边在这个序列上的一段区间出现

#include<bits/stdc++.h>
#define il __inline__ __attribute__ ((always_inline))
#define fur(i,x,y) for(int i(x);i<=y;++i)
namespace IO{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}void in(char &ch){if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)__=1;else ch=c;}void in(char *ch){*ch='\0';if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF){__=1;return;}*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)__=1;*ch='\0';}template<typename T>void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>void in(T &x,arr & ... y){in(x),in(y...);}const char ln='\n';static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}void out(const char* s){while(*s)pt(*s++);}void out(char* s){while(*s)pt(*s++);}void out(char c){pt(c);}template<typename T>void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>void out(T x,arr & ... y){out(x),out(y...);}}using namespace IO;
const int M=50011;
int n,m,q,tot,cnt,lst[M],pos[M],head[M<<2];
struct node{int x,y,w;}a[M<<2];
struct edge{int to,nxt;}e[M<<4];
il void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
/*--- LCT START---*/
int f[M<<2],c[2][M<<2],v[M<<2],mx[M<<2];
bool rev[M<<2];
#define ls c[0][x]
#define rs c[1][x]
il void pu(int x){
    mx[x]=x;
    if(ls&&v[mx[ls]]>v[mx[x]])mx[x]=mx[ls];
    if(rs&&v[mx[rs]]>v[mx[x]])mx[x]=mx[rs];
}
il void pd(int x){
    if(rev[x])
        rev[ls]^=1,rev[rs]^=1,
        ls^=rs,rs^=ls,ls^=rs,
        rev[x]=0;
}
il int g(int x){return c[1][f[x]]==x;}
il int nrt(int x){return c[0][f[x]]==x||c[1][f[x]]==x;}
il void rotate(int x){
    int y=f[x],z=f[y],l=g(x),r=!l,w=c[r][x];
    if(nrt(y))c[g(y)][z]=x;
    c[r][x]=y,c[l][y]=w;
    if(w)f[w]=y;
    f[x]=z,f[y]=x;
    pu(y);
}
void pda(int x){if(nrt(x))pda(f[x]);pd(x);}
il void splay(int x){
    // for(pda(x);nrt(x);rotate(x))if(nrt(f[x]))
        // rotate(g(x)^g(f[x])?x:f[x]);
    for(pda(x);nrt(x);rotate(x));//这题单旋更快
    pu(x);
}
il void access(int x){
    for(int y=0;x;x=f[y=x])
        splay(x),rs=y,pu(x);
}
il void mrt(int x){access(x),splay(x),rev[x]^=1;}
il int frt(int x){
    for(access(x),splay(x);ls;pd(x),x=ls);
    splay(x);return x;
}
/*--- LCT END ---*/
void upd(int L,int R,int v,int l,int r,int rt){
    if(L<=l&&r<=R){add(rt,v);return;}
    int m=l+r>>1;
    if(L<=m)upd(L,R,v,l,m,rt<<1);
    if(R>m)upd(L,R,v,m+1,r,rt<<1|1);
}
il void link(int x,int y){mrt(x),f[x]=y;}
il void spl(int x,int y){mrt(x),access(y),splay(y);}
il void cut(int x,int y){spl(x,y),f[x]=c[0][y]=0,pu(y);}
int st[M<<2],tp=0;
long long ans;
bool typ[M<<2];
void div(int l,int r,int rt){
    int x,y,w,bg=tp,to,m=l+r>>1;
    for(int i=head[rt];i;i=e[i].nxt){
        to=e[i].to,x=a[to].x,y=a[to].y,w=a[to].w;
        if(frt(x)==frt(y)){
            spl(x,y);
            int p=mx[y];
            if(v[p]>w){
                cut(a[p-n].x,p),cut(a[p-n].y,p),ans-=a[p-n].w;
                st[++tp]=p-n,typ[tp]=0;
            }
            else continue;
        }
        link(x,to+n),link(y,to+n),ans+=w;
        st[++tp]=to,typ[tp]=1;
    }
    if(l==r)out(ans,ln);
    else div(l,m,rt<<1),div(m+1,r,rt<<1|1);
    for(;tp^bg;--tp){
        x=st[tp];
        if(typ[tp])
            ans-=a[x].w,
            cut(a[x].x,x+n),cut(a[x].y,x+n);
        else
            ans+=a[x].w,
            link(a[x].x,x+n),link(a[x].y,x+n);
    }
}
int main(){
    in(n,m,q);tot=m;
    fur(i,1,m)in(a[i].x,a[i].y,a[i].w),lst[i]=1,pos[i]=i;
    fur(i,1,q){
        int k,d;in(k,d);
        if(lst[k]<i)upd(lst[k],i-1,pos[k],1,q,1);
        lst[k]=i;a[++tot]=a[pos[k]];a[tot].w=d;pos[k]=tot;
    }
    fur(i,1,m)upd(lst[i],q,pos[i],1,q,1);
    fur(i,1,tot)v[n+i]=a[i].w;
    div(1,q,1);
    flush();
}

cdq分治

一个非常巧妙的思路

和线段树分治一样,我们对修改时间进行分治

暴力: 当l=r的时候,就直接让修改生效,然后求一边MST(最小生成树)

图的规模是m,\mathcal{O}(nm)显然不行

要靠分治来缩小图的规模

  1. 必选边

    假设当前处理的区间为[l,r],把区间中要求改的边全部改为-\infty,跑一遍MST

    那么跑完后不是-\infty且还在MST中的边,之后也一定会留在MST

    那么可以把这些边形成的连通块缩点,把剩下的边存下来继续分治

  2. 无用边

    假设当前处理的区间为[l,r],把区间中要求改的边全部改为\infty,跑一遍MST

    那么跑完后不是\infty且不在MST中的边,之后也一定不在MST

#include<bits/stdc++.h>
#define il __inline__ __attribute__ ((always_inline))
#define fur(i,x,y) for(int i(x);i<=y;++i)
typedef long long ll;
namespace IO{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}void in(char &ch){if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)__=1;else ch=c;}void in(char *ch){*ch='\0';if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF){__=1;return;}*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)__=1;*ch='\0';}template<typename T>void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>void in(T &x,arr & ... y){in(x),in(y...);}const char ln='\n';static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}void out(const char* s){while(*s)pt(*s++);}void out(char* s){while(*s)pt(*s++);}void out(char c){pt(c);}template<typename T>void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>void out(T x,arr & ... y){out(x),out(y...);}}using namespace IO;
using std::sort;
const int N=50011,inf=1<<30;
int n,m,q,f[N],sz[N],a[N],c[N],tot[20];
struct node{
    int x,y,w,id;
    bool operator<(node t){return w<t.w;}
}e[20][N],b[N],t[N];
struct mdy{int x,y;}p[N];
int gf(int x){return x==f[x]?x:(f[x]=gf(f[x]));}
void link(int x,int y){
    x=gf(x),y=gf(y);
    if(sz[x]>sz[y])x^=y,y^=x,x^=y;
    f[x]=y,sz[y]+=sz[x];
}
void set(int T,node*a){
    fur(i,1,T)
        f[a[i].x]=a[i].x,f[a[i].y]=a[i].y,
        sz[a[i].x]=sz[a[i].y]=1;
}
void useful(int&T,ll&val){
    int tt=0;
    set(T,b);sort(b+1,b+T+1);
    fur(i,1,T)if(gf(b[i].x)^gf(b[i].y))
        link(b[i].x,b[i].y),t[++tt]=b[i];
    set(tt,t);
    fur(i,1,tt)if(t[i].w!=-inf&&gf(t[i].x)^gf(t[i].y))
        val+=t[i].w,link(t[i].x,t[i].y);
    tt=0;
    fur(i,1,T)if(gf(b[i].x)^gf(b[i].y))
        t[++tt]={f[b[i].x],f[b[i].y],b[i].w,b[i].id};
    fur(i,1,tt)c[b[i].id]=i,b[i]=t[i];
    T=tt;
}
void useless(int&T){
    int tt=0;
    set(T,b);sort(b+1,b+T+1);
    fur(i,1,T)
        if(gf(b[i].x)^gf(b[i].y))
            link(b[i].x,b[i].y),t[++tt]=b[i];
        else if(b[i].w==inf)t[++tt]=b[i];
    fur(i,1,tt)c[b[i].id]=i,b[i]=t[i];
    T=tt;
}
void div(int l,int r,int d,ll val){
    int T=tot[d],m=l+r>>1;
    if(l==r)a[p[l].x]=p[l].y;
    fur(i,1,T){
        e[d][i].w=a[e[d][i].id];
        b[i]=e[d][i],c[b[i].id]=i;
    }
    if(l==r){
        set(T,b);
        sort(b+1,b+T+1);
        fur(i,1,T)if(gf(b[i].x)^gf(b[i].y))
            link(b[i].x,b[i].y),val+=b[i].w;
        out(val,ln);return;
    }
    fur(i,l,r)b[c[p[i].x]].w=-inf;
    useful(T,val);
    fur(i,l,r)b[c[p[i].x]].w=inf;
    useless(T);
    fur(i,1,T)e[d+1][i]=b[i];
    tot[d+1]=T;
    div(l,m,d+1,val);
    div(m+1,r,d+1,val);
}
int main(){
    in(n,m,q);
    int x,y;
    fur(i,1,m)in(x,y,a[i]),e[0][i]={x,y,a[i],i};
    fur(i,1,q)in(p[i].x,p[i].y);
    tot[0]=m;div(1,q,0,0);
    flush();
}
LG 3206 [HNOI2010]城市建设
comment评论
Search
search